En matemáticas , un teorema de imposibilidad es un teorema que demuestra que un problema o un conjunto general de problemas no se pueden resolver. También se conocen como pruebas de imposibilidad , pruebas negativas o resultados negativos . Los teoremas de imposibilidad a menudo resuelven décadas o siglos de trabajo dedicado a buscar una solución al demostrar que no hay solución. Probar que algo es imposible suele ser mucho más difícil que la tarea opuesta, ya que a menudo es necesario desarrollar una prueba que funcione en general, en lugar de simplemente mostrar un ejemplo particular. [1] Los teoremas de imposibilidad suelen expresarse como proposiciones existenciales negativas o proposiciones universales en lógica.
La irracionalidad de la raíz cuadrada de 2 es una de las pruebas de imposibilidad más antiguas. Muestra que es imposible expresar la raíz cuadrada de 2 como un cociente de dos números enteros . Otra prueba consecuente de imposibilidad fue la prueba de Ferdinand von Lindemann en 1882, que mostró que el problema de la cuadratura del círculo no se puede resolver [2] porque el número π es trascendental (es decir, no algebraico), y que solo un subconjunto de los números algebraicos se puede construir con compás y regla . Otros dos problemas clásicos ( trisecar el ángulo general y duplicar el cubo ) también se demostraron imposibles en el siglo XIX, y todos estos problemas dieron lugar a la investigación de estructuras matemáticas más complicadas.
Algunas de las pruebas de imposibilidad más importantes encontradas en el siglo XX fueron las relacionadas con la indecidibilidad , que mostraban que hay problemas que no pueden ser resueltos en general por ningún algoritmo , siendo uno de los más destacados el problema de la detención . Los teoremas de incompletitud de Gödel fueron otros ejemplos que descubrieron limitaciones fundamentales en la demostrabilidad de los sistemas formales. [3]
En la teoría de la complejidad computacional , técnicas como la relativización (la adición de un oráculo ) permiten pruebas "débiles" de imposibilidad, en el sentido de que las técnicas de prueba que no se ven afectadas por la relativización no pueden resolver el problema P versus NP . [4] Otra técnica es la prueba de completitud para una clase de complejidad , que proporciona evidencia de la dificultad de los problemas al mostrar que son tan difíciles de resolver como cualquier otro problema de la clase. En particular, un problema completo es intratable si uno de los problemas de su clase lo es.
Uno de los tipos de prueba de imposibilidad más utilizados es la prueba por contradicción . En este tipo de prueba, se demuestra que si se supone que una proposición, como una solución a una clase particular de ecuaciones, es cierta, entonces, mediante la deducción, se puede demostrar que se cumplen dos cosas mutuamente contradictorias, como que un número sea par e impar o negativo y positivo. Dado que la contradicción surge de la suposición original, esto significa que la premisa supuesta debe ser imposible.
Por el contrario, una prueba no constructiva de una afirmación de imposibilidad procedería mostrando que es lógicamente contradictorio que todos los contraejemplos posibles sean inválidos: al menos uno de los elementos de una lista de contraejemplos posibles debe ser en realidad un contraejemplo válido para la conjetura de imposibilidad. Por ejemplo, una conjetura de que es imposible que una potencia irracional elevada a una potencia irracional sea racional fue refutada mostrando que uno de dos contraejemplos posibles debe ser un contraejemplo válido, sin mostrar cuál es.
Otro tipo de prueba por contradicción es la prueba por descendencia, que procede primero asumiendo que algo es posible, como una solución entera positiva [5] para una clase de ecuaciones, y que por lo tanto debe haber una solución más pequeña (por el principio de buen ordenamiento ). A partir de la supuesta solución más pequeña, se demuestra luego que se puede encontrar una solución más pequeña, contradiciendo la premisa de que la solución anterior era la más pequeña posible, mostrando así que la premisa original de que existe una solución debe ser falsa.
La forma obvia de refutar una conjetura de imposibilidad es proporcionar un único contraejemplo . Por ejemplo, Euler propuso que eran necesarias al menos n potencias n diferentes para sumar otra potencia n . Esta conjetura fue refutada en 1966, con un contraejemplo que implicaba contar solo cuatro potencias 5 diferentes que sumaban otra quinta potencia:
La prueba por contraejemplo es una forma de prueba constructiva , en la que se exhibe un objeto que refuta la afirmación.
En la teoría de la elección social , el teorema de imposibilidad de Arrow muestra que es imposible diseñar un sistema de votación por orden de preferencia que no sea dictatorial y satisfaga un requisito básico para el comportamiento racional llamado independencia de alternativas irrelevantes .
El teorema de Gibbard muestra que cualquier forma de juego a prueba de estrategias (es decir, una con una estrategia dominante ) con más de dos resultados es dictatorial .
El teorema de Gibbard-Satterthwaite es un caso especial que muestra que ningún sistema de votación determinista puede ser totalmente invulnerable a la votación estratégica en todas las circunstancias, independientemente de cómo voten los demás.
El principio de revelación puede verse como un teorema de imposibilidad que muestra lo "opuesto" del teorema de Gibbard, en un sentido coloquial: cualquier juego o sistema de votación puede hacerse resistente a la estrategia incorporando la estrategia al mecanismo . Por lo tanto, es imposible diseñar un mecanismo con una solución que sea mejor que la que se puede obtener mediante un mecanismo veraz .
La demostración de Pitágoras, realizada alrededor del año 500 a. C., tuvo un profundo efecto en las matemáticas. Demuestra que la raíz cuadrada de 2 no puede expresarse como el cociente de dos números enteros. La demostración dividió "los números" en dos conjuntos no superpuestos: los números racionales y los números irracionales .
Hay un famoso pasaje en el Teeteto de Platón en el que se afirma que Teodoro (el maestro de Platón) demostró la irracionalidad de
Tomando todos los casos separados hasta la raíz de 17 pies cuadrados.... [6]
Una prueba más general muestra que la raíz m de un entero N es irracional, a menos que N sea la potencia m de un entero n . [7] Es decir, es imposible expresar la raíz m de un entero N como el cociente a ⁄ b de dos enteros a y b , que no comparten ningún factor primo común , excepto en los casos en que b = 1.
La geometría griega se basaba en el uso del compás y de una regla (aunque la regla no es estrictamente necesaria). El compás permite al geómetra construir puntos equidistantes entre sí, lo que en el espacio euclidiano equivale implícitamente a cálculos de raíces cuadradas . Cuatro famosas preguntas sobre cómo construir:
Durante más de 2.000 años se hicieron intentos infructuosos de resolver estos problemas; por fin, en el siglo XIX, se demostró que las construcciones deseadas son matemáticamente imposibles sin admitir herramientas adicionales a una brújula. [8]
Todos estos son problemas de construcción euclidiana , y las construcciones euclidianas pueden realizarse solo si involucran solo números euclidianos (por definición de este último). [9] Los números irracionales pueden ser euclidianos. Un buen ejemplo es la raíz cuadrada de 2 (un número irracional). Es simplemente la longitud de la hipotenusa de un triángulo rectángulo con catetos de una unidad de longitud, y puede construirse con una regla y un compás. Pero se demostró siglos después de Euclides que los números euclidianos no pueden involucrar ninguna operación que no sea la suma, la resta, la multiplicación, la división y la extracción de raíces cuadradas.
Tanto para trisecar el ángulo general como para duplicar el cubo es necesario tomar raíces cúbicas , que no son números construibles .
no es un número euclidiano ... y por lo tanto es imposible construir, por métodos euclidianos, una longitud igual a la circunferencia de un círculo de diámetro unitario
Debido a que se demostró en 1882 que es un número trascendental , no es un número euclidiano; por lo tanto, la construcción de una longitud a partir de un círculo unitario es imposible. [10] [11]
El teorema de Gauss-Wantzel demostró en 1837 que construir un n -gono equilátero es imposible para la mayoría de los valores de n .
El postulado de las paralelas de los Elementos de Euclides es equivalente a la afirmación de que, dada una línea recta y un punto que no está sobre esa línea, solo se puede trazar una paralela a la línea a través de ese punto. A diferencia de los otros postulados, se consideraba menos evidente. Nagel y Newman sostienen que esto puede deberse a que el postulado se refiere a regiones "infinitamente remotas" del espacio; en particular, las líneas paralelas se definen como aquellas que no se encuentran ni siquiera "en el infinito", en contraste con las asíntotas . [12] Esta falta percibida de evidencia condujo a la pregunta de si podría probarse a partir de los otros axiomas y postulados euclidianos. Fue solo en el siglo XIX que la imposibilidad de deducir el postulado de las paralelas a partir de los otros se demostró en las obras de Gauss , Bolyai , Lobachevsky y Riemann . Estos trabajos mostraron que el postulado de las paralelas puede, además, reemplazarse por alternativas, lo que conduce a geometrías no euclidianas .
Nagel y Newman consideran que la cuestión planteada por el postulado de las paralelas es "...quizás el desarrollo más significativo en sus efectos de largo alcance sobre la historia matemática posterior". [12] En particular, consideran que su resultado es "de la mayor importancia intelectual", ya que mostró que " se puede dar una prueba de la imposibilidad de probar ciertas proposiciones [en este caso, el postulado de las paralelas] dentro de un sistema dado [en este caso, los primeros cuatro postulados de Euclides]". [13]
El último teorema de Fermat fue conjeturado por Pierre de Fermat en el siglo XVII y establece la imposibilidad de encontrar soluciones en números enteros positivos para la ecuación con . El propio Fermat dio una prueba para el caso n = 4 utilizando su técnica de descenso infinito , y otros casos especiales fueron probados posteriormente, pero el caso general no fue probado hasta 1994 por Andrew Wiles .
La pregunta "¿Tiene alguna ecuación diofántica arbitraria una solución entera?" es indecidible . Es decir, es imposible responder a la pregunta para todos los casos.
Franzén introduce el décimo problema de Hilbert y el teorema MRDP (teorema de Matiyasevich-Robinson-Davis-Putnam) que establece que "no existe ningún algoritmo que pueda decidir si una ecuación diofántica tiene o no solución ". MRDP utiliza la prueba de indecidibilidad de Turing: "... el conjunto de ecuaciones diofánticas resolubles es un ejemplo de un conjunto computablemente enumerable pero no decidible, y el conjunto de ecuaciones diofánticas irresolubles no es computablemente enumerable". [14]
Esta profunda paradoja planteada por Jules Richard en 1905 sirvió de base para el trabajo de Kurt Gödel [15] y Alan Turing. En Principia Mathematica se encuentra una definición sucinta : [16]
La paradoja de Richard... es la siguiente. Considérense todos los decimales que pueden definirse por medio de un número finito de palabras [“palabras” son símbolos; negrita añadida para énfasis] ; sea E la clase de tales decimales. Entonces E tiene [un número infinito de] términos; por lo tanto, sus miembros pueden ordenarse como el 1er, 2do, 3er, ... Sea X un número definido como sigue [Whitehead y Russell ahora emplean el método diagonal de Cantor] . Si la n -ésima cifra en el n -ésimo decimal es p , sea la n -ésima cifra en X p + 1 (o 0, si p = 9). Entonces X es diferente de todos los miembros de E , ya que, cualquiera que sea el valor finito que pueda tener n , la n -ésima cifra en X es diferente de la n -ésima cifra en el n -ésimo de los decimales que componen E , y por lo tanto X es diferente del n -ésimo decimal. Sin embargo, hemos definido X en un número finito de palabras [es decir, esta misma definición de “palabra” anterior] y, por lo tanto , X debería ser un miembro de E. Por lo tanto, X es y no es un miembro de E.
— Principia Mathematica , 2.ª edición, 1927, pág. 61
Kurt Gödel consideró su prueba como “una analogía” de la paradoja de Richard, a la que llamó “ antinomia de Richard ” [17] ( ).
Alan Turing construyó esta paradoja con una máquina y demostró que esta máquina no podía responder a una pregunta simple: ¿será esta máquina capaz de determinar si alguna máquina (incluida ella misma) quedará atrapada en un " bucle infinito " improductivo (es decir, si no puede continuar su cálculo del número diagonal)?
Como dicen Nagel y Newman (p. 68), "el artículo de Gödel es difícil. Hay que dominar cuarenta y seis definiciones preliminares, junto con varios teoremas preliminares importantes, antes de llegar a los resultados principales". De hecho, Nagel y Newman exigieron una introducción de 67 páginas para su exposición de la prueba. Pero si el lector se siente lo suficientemente fuerte como para abordar el artículo, Martin Davis observa que "este notable artículo no es sólo un hito intelectual, sino que está escrito con una claridad y un vigor que hacen que sea un placer leerlo" (Davis en Undecidable, p. 4).
Gödel demostró, con sus propias palabras:
Gödel comparó su prueba con la "antinomia de Richard" (una " antinomia " es una contradicción o una paradoja; para más información, véase paradoja de Richard ):
Poco antes y después de la prueba de Turing aparecieron varias pruebas de indecidibilidad similares:
Para una exposición adecuada para no especialistas, véase Beltrami, pág. 108 y siguientes. Véase también Franzen, capítulo 8, págs. 137-148, y Davis, págs. 263-266. La discusión de Franzen es significativamente más complicada que la de Beltrami y profundiza en Ω, la llamada "probabilidad de detención" de Gregory Chaitin . El tratamiento anterior de Davis aborda la cuestión desde el punto de vista de una máquina de Turing . Chaitin ha escrito varios libros sobre sus esfuerzos y las posteriores repercusiones filosóficas y matemáticas de ellos.
Una cadena se denomina (algorítmicamente) aleatoria si no se puede generar a partir de ningún programa informático más corto. Si bien la mayoría de las cadenas son aleatorias , no se puede demostrar que ninguna en particular lo sea, excepto en el caso de un número finito de cadenas cortas:
Beltrami observa que “la prueba de Chaitin está relacionada con una paradoja planteada por el bibliotecario de Oxford G. Berry a principios del siglo XX, que pide “el número entero positivo más pequeño que no puede definirse mediante una oración en inglés con menos de 1000 caracteres”. Evidentemente, la definición más corta de este número debe tener al menos 1000 caracteres. Sin embargo, la oración entre comillas, que es en sí misma una definición del supuesto número, tiene menos de 1000 caracteres de longitud”. [22]
En las ciencias naturales , los teoremas de imposibilidad se derivan como resultados matemáticos probados dentro de teorías científicas bien establecidas . La base para esta fuerte aceptación es una combinación de evidencia extensa de que algo no ocurre, combinada con una teoría subyacente, muy exitosa en hacer predicciones, cuyos supuestos conducen lógicamente a la conclusión de que algo es imposible.
Dos ejemplos de imposibilidades ampliamente aceptadas en física son las máquinas de movimiento perpetuo , que violan la ley de conservación de la energía , y exceder la velocidad de la luz , que viola las implicaciones de la relatividad especial . Otro es el principio de incertidumbre de la mecánica cuántica , que afirma la imposibilidad de conocer simultáneamente tanto la posición como el momento de una partícula. También está el teorema de Bell : ninguna teoría física de variables ocultas locales puede reproducir jamás todas las predicciones de la mecánica cuántica.
Si bien una afirmación de imposibilidad en las ciencias naturales nunca puede probarse de manera absoluta, podría refutarse mediante la observación de un único contraejemplo . Tal contraejemplo requeriría que se reexaminaran los supuestos subyacentes a la teoría que implicaba la imposibilidad.
