En matemáticas , un teorema de imposibilidad es un teorema que demuestra que un problema o un conjunto general de problemas no se puede 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 dedicados a buscar una solución demostrando que no hay solución. Demostrar 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 en 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 una razón de dos números enteros . Otra prueba importante de imposibilidad fue la prueba de Ferdinand von Lindemann en 1882, que demostró que el problema de la cuadratura del círculo no puede resolverse [2] porque el número π es trascendental (es decir, no algebraico), y que sólo un subconjunto del número algebraico Los números se pueden construir con compás y regla . Otros dos problemas clásicos ( la trisección del ángulo general y la duplicación del cubo ) también resultaron 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 demostraron que hay problemas que en general no pueden resolverse mediante 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 de imposibilidad "débiles", 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 muestra que si se supone que se cumple una proposición, como la solución de una clase particular de ecuaciones, entonces, mediante deducción, se puede demostrar que se cumplen dos cosas mutuamente contradictorias, como que un número sea par. e impar o tanto negativo como positivo. Dado que la contradicción surge del supuesto original, esto significa que la premisa asumida debe ser imposible.
Por el contrario, una prueba no constructiva de una afirmación de imposibilidad procedería demostrando que es lógicamente contradictorio que todos los contraejemplos posibles sean inválidos: al menos uno de los elementos en una lista de posibles contraejemplos debe ser en realidad un contraejemplo válido para la conjetura de imposibilidad. . Por ejemplo, se refutó una conjetura de que es imposible que una potencia irracional elevada a potencia irracional sea racional , al mostrar que uno de dos posibles contraejemplos 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] a una clase de ecuaciones, y que por lo tanto debe haber una solución más pequeña (según el método de Well- principio de ordenación ). A partir de la supuesta solución más pequeña, se muestra 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 proporcionando un único contraejemplo . Por ejemplo, Euler propuso que eran necesarias al menos n enésimas potencias diferentes para sumar otra enésima potencia . La conjetura fue refutada en 1966, con un contraejemplo que implicaba un recuento de sólo cuatro quintas potencias diferentes que se sumaban a otra quinta potencia:
La prueba mediante 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 idear un sistema de votación por orden de preferencia que no sea dictatorial y que 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, uno 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 completamente invulnerable al voto estratégico 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 volverse resistente a la estrategia incorporando la estrategia al mecanismo . Por 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 alrededor del año 500 a. C. ha tenido un profundo efecto en las matemáticas. Muestra que la raíz cuadrada de 2 no se puede expresar como la razón de dos números enteros. La prueba dividió "los números" en dos colecciones que no se superponen: los números racionales y los números irracionales .
Hay un pasaje famoso 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 número entero N es irracional, a menos que N sea la potencia m de un número entero n . [7] Es decir, es imposible expresar la raíz m -ésima de un número entero N como la razón a ⁄ b de dos números enteros a y b , que no comparten ningún factor primo común , excepto en los casos en los que b = 1.
La geometría griega se basaba en el uso del compás y la regla (aunque la regla no es estrictamente necesaria). La brújula permite al geómetra construir puntos equidistantes entre sí, que en el espacio euclidiano equivalen implícitamente a cálculos de raíces cuadradas . Cuatro preguntas famosas preguntaban 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 además de una brújula. [8]
Todos estos son problemas de construcción euclidiana , y las construcciones euclidianas sólo pueden realizarse si involucran únicamente números euclidianos (por definición de estos últimos). [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 se puede construir con una regla y un compás. Pero siglos después de Euclides se demostró que los números euclidianos no pueden implicar más operaciones que 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 se requieren sacar raíces cúbicas , que no son números construibles .
no es un número euclidiano ... y por lo tanto es imposible construir, mediante métodos euclidianos, una longitud igual a la circunferencia de un círculo de diámetro unitario
Debido a que en 1882 se demostró que era un número trascendental , no es un número euclidiano; Por tanto, es imposible construir una longitud a partir de un círculo unitario. [10] [11]
El teorema de Gauss-Wantzel demostró en 1837 que construir un n -gon 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á en esa línea, sólo se puede trazar una paralela a la línea que pasa por ese punto. A diferencia de los otros postulados, se consideró menos evidente. Nagel y Newman sostienen que esto puede deberse a que el postulado se refiere a regiones del espacio "infinitamente remotas"; en particular, las líneas paralelas se definen como que no se encuentran ni siquiera "en el infinito", en contraste con las asíntotas . [12] Esta percibida falta de evidencia llevó a la pregunta de si podría probarse a partir de los otros axiomas y postulados euclidianos. No fue hasta el siglo XIX que la imposibilidad de deducir el postulado paralelo de los demás quedó demostrada en las obras de Gauss , Bolyai , Lobachevsky y Riemann . Estos trabajos demostraron que el postulado de las paralelas puede además ser reemplazado por alternativas, lo que lleva a geometrías no euclidianas .
Nagel y Newman consideran que la cuestión planteada por el postulado paralelo es "...quizás el desarrollo más significativo en sus efectos de largo alcance en la historia matemática posterior". [12] En particular, consideran que su resultado es "de la mayor importancia intelectual", ya que demostró que " se puede dar una prueba de la imposibilidad de probar ciertas proposiciones [en este caso, el postulado paralelo] 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 usando su técnica de descenso infinito , y posteriormente se probaron otros casos especiales, pero el caso general no fue probado hasta 1994 por Andrew Wiles .
La pregunta "¿Alguna ecuación diofántica arbitraria tiene una solución entera?" es indecidible . Es decir, es imposible responder a la pregunta para todos los casos.
Franzén presenta 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 solución alguna ". MRDP utiliza la prueba de indecidibilidad de Turing: "... el conjunto de ecuaciones diofánticas solubles 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 presentada por Jules Richard en 1905 informó el trabajo de Kurt Gödel [15] y Alan Turing. Una definición sucinta se encuentra en Principia Mathematica : [16]
La paradoja de Richard... es la siguiente. Considere todos los decimales que pueden definirse mediante un número finito de palabras [las “palabras” son símbolos; se agregó negrita para enfatizar] ; 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 1º, 2º, 3º, ... Sea X un número definido de la siguiente manera [Whitehead y Russell emplean ahora el método diagonal de Cantor] . Si la n -ésima cifra en el n -ésimo decimal es p , sea p + 1 (o 0, si p = 9) la n -ésima cifra en X. 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 miembro de E. Por tanto, X es y no es miembro de E.
— Principia Mathematica , 2ª edición 1927, p. 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: ¿podrá esta máquina determinar si alguna máquina (incluida ella misma) quedará atrapada en un ' bucle infinito ' improductivo (es decir, no puede continuar? su cálculo del número diagonal).
Para citar a Nagel y Newman (p. 68), "el artículo de Gödel es difícil. Es necesario dominar cuarenta y seis definiciones preliminares, junto con varios teoremas preliminares importantes, antes de alcanzar los resultados principales". De hecho, Nagel y Newman necesitaron 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 vigor que hace que su lectura sea un placer" (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, consulte la paradoja de Richard ):
Poco antes y después de la prueba de Turing aparecieron varias pruebas de indecidibilidad similares:
Para una exposición apta para no especialistas, véase Beltrami p. 108 y sigs. Véase también Franzen Capítulo 8, págs. 137-148, y Davis, págs. 263-266. La discusión de Franzén 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 la máquina de Turing . Chaitin ha escrito varios libros sobre sus esfuerzos y las consecuencias filosóficas y matemáticas posteriores de ellos.
Una cadena se denomina (algorítmicamente) aleatoria si no puede producirse 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 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 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 frase entre comillas, que es en sí misma una definición del supuesto número, ¡tiene menos de 1000 caracteres! [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 de 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 la superación de 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 locales ocultas podrá jamás reproducir 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 solo contraejemplo . Un contraejemplo así requeriría que se reexaminaran los supuestos subyacentes a la teoría que implicaba la imposibilidad.