Prueba de imposibilidad
Una prueba de imposibilidad, también conocida como prueba negativa, prueba de un teorema de imposibilidad, o resultado negativo, es una demostración mediante la que se concluye que un problema particular no se puede resolver como se describe en su enunciado, o que un conjunto particular de problemas no se puede resolver en general. Algunas de estas pruebas han permanecido a la espera de resolución durante décadas o incluso siglos de trabajo. Comprobar que algo es imposible suele ser mucho más difícil que la tarea opuesta; ya que a menudo es necesario desarrollar una teoría en la que se apoya la demostración. Los teoremas de imposibilidad generalmente se pueden expresar como proposiciones de existencia negativas o proposiciones universales en lógica (véase cuantificador universal).
Quizás una de las pruebas de imposibilidad más antiguas es la de la irracionalidad de la raíz cuadrada de 2, que demuestra que es imposible expresar la raíz cuadrada de 2 como un cociente de números enteros. Otra famosa prueba de imposibilidad fue publicada en 1882 por Carl Louis Ferdinand von Lindemann, demostrando que el antiguo problema de la cuadratura del círculo no se puede resolver, porque el número π es transcendente (es decir, no algebraico) y solo un subconjunto de números algebraicos puede construirse con regla y compás. Otros dos problemas clásicos, la trisección del ángulo y la duplicación del cubo mediante construcciones con regla y compás, también se demostró rigurosamente en el siglo XIX que no tienen solución.
Un problema que surgió en el siglo XVI fue el de crear una fórmula general usando radicales que expresen la solución de cualquier ecuación polinomial de grado dado k, donde k≥5. En la década de 1820, el teorema de Abel-Ruffini (también conocido como el teorema de imposibilidad de Abel) demostró que esto era imposible, usando conceptos como el de grupo resoluble de la teoría de Galois, un nuevo subcampo del álgebra abstracta.
Entre las pruebas de imposibilidad más importantes del siglo XX figuran las relacionadas con el problema de indecibilidad, que demostraron que existen problemas que en general no pueden ser resueltos por ningún algoritmo, siendo el más famoso el problema de la parada. Otros hallazgos relacionados de manera similar son los teoremas de incompletitud de Gödel, que evidencian algunas limitaciones fundamentales en la posibilidad de disponer de pruebas independientes en los sistemas formales.
En teoría de la complejidad computacional, técnicas como la relativización (véase máquina oráculo) proporcionan pruebas débiles de imposibilidad excluyendo ciertas técnicas de prueba. Otras técnicas, como las pruebas de completitud para una clase de complejidad, proporcionan evidencia de la dificultad de los problemas, al mostrar que son tan difíciles de resolver como otros problemas conocidos que se han demostrado intratables.
Un tipo de prueba de imposibilidad ampliamente utilizado es la prueba por contradicción o reducción al absurdo. En este tipo de prueba, se demuestra que si algo, como una solución a una clase particular de ecuaciones, fuera posible, entonces dos cosas mutuamente contradictorias serían verdaderas, como que un número sea tanto par como impar. La contradicción implica que la premisa original es imposible.
Un tipo de prueba por contradicción es la prueba por descenso, que procede primero asumiendo que algo es posible, como una solución entera positiva a una clase de ecuaciones, y que por lo tanto debe haber una solución mínima. 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 primera solución era la más pequeña posible, mostrando así que la premisa original (que existe una solución) debe ser falsa.
Hay dos métodos alternativos para refutar una conjetura de que algo es imposible: mediante un contraejemplo (prueba constructiva) y por contradicción lógica (prueba no constructiva).
La forma obvia de refutar una conjetura de imposibilidad es proporcionando un único contraejemplo. Por ejemplo, la conjetura de la suma de potencias de Euler planteaba que en el campo de los números naturales, son necesarias al menos n potencias enésimas diferentes para sumar cualquier otra potencia n-ésima. La conjetura fue refutada en 1966, con un contraejemplo que involucra un total de solo cuatro quintas potencias diferentes sumadas para obtener otra quinta potencia:
Una demostración por contraejemplo es un prueba constructiva, en la que se presenta un caso que refuta la afirmación. Por el contrario, una prueba no constructiva de una afirmación de imposibilidad procedería mostrando que es lógicamente contradictorio que "todos" los posibles contraejemplos sean inválidos: al menos "uno" de los elementos de una lista de posibles contraejemplos debe en realidad ser un contraejemplo válido de la conjetura de imposibilidad. Por ejemplo, una conjetura de que es imposible que una potencia irracional elevada a una potencia irracional sea racional, se puede refutar mostrando que uno de los dos posibles contraejemplos debe ser un contraejemplo válido, sin mostrar cuál es.
La prueba de Pitágoras (o más probablemente, de uno de sus alumnos) descubierta sobre el año 500 a.C. ha tenido un efecto profundo en las matemáticas. Demuestra que la raíz cuadrada de dos no se puede expresar como la proporción de dos números enteros (numerables). La prueba bifurcó "los números" en dos colecciones que no se superponen: los números racionales y los números irracionales. Esta bifurcación fue utilizada por Cantor en su método de la diagonal, que a su vez fue utilizado por Turing en su prueba de que el Entscheidungsproblem, el problema de decisión de Hilbert, es indecidible.
La prueba de irracionalidad para las raíces cuadradas de los números primos hasta 17 figura en un texto clásico:
Ahora existe una prueba más general de que:
Es decir, es imposible expresar la raíz m-ésima de un número entero N como la razón a⁄b de dos enteros a y b, que no comparten números primos en común excepto en los casos en los que b = 1.
Tres cuestiones planteadas por los geómetras de la Grecia clásica se hicieron especialmente conocidas:
Durante más de 2000 años se hicieron intentos infructuosos para resolver estos problemas, hasta que por fin, en el siglo XIX se comprobó que estas tres construcciones son conceptualmente imposibles.
Un cuarto problema de los antiguos griegos era construir un polígono equilátero con un número específico de n lados, más allá de los casos básicos de n = 3, 4 y 5 que sí se sabían construir.
Todos estos son problemas de construcción euclídea, que solo son realizables si involucran únicamente números construibles (Hardy y Wright p. 159). Curiosamente, hay números irracionales que pueden ser euclidianos. Un buen ejemplo es el número irracional raíz cuadrada de 2 (la longitud de la hipotenusa de un triángulo rectángulo con catetos de una unidad de longitud), que se puede construir fácilmente con regla y compás. Siglos después de Euclides, se demostró que los números euclidianos no pueden involucrar ninguna operación más que la suma, la resta, la multiplicación, la división y la extracción de raíces cuadradas.
Tanto la trisección de un ángulo arbitrario como la duplicación del cubo requieren obtener raíces cúbicas, que no son números construibles exclusivamente con regla y compás.
Existe una prueba para demostrar que cualquier número euclidiano es un número algebraico, un número que es la solución de alguna ecuación algebraica. Por lo tanto, debido a que en 1882 se demostró que es un número trascendente (y que por lo tanto, por definición, no es un número algebraico), queda demostrado que no es un número euclidiano. En consecuencia, la construcción de una longitud a partir de un círculo unitario es imposible, y no se puede lograr la cuadratura del área del círculo exclusivamente por métodos euclídeos.
En 1837 se publicó el teorema de Gauss-Wantzel, mediante el que se demostró que la construcción euclídea de un polígono regular de n lados es imposible para la mayoría de los valores de n.
Nagel y Newman consideran que la cuestión implícitamente planteada en el quinto postulado de Euclides es "... quizás el desarrollo más significativo en sus efectos a largo plazo sobre la historia de la matemática posterior" (p. 9).
La pregunta es:
No fue hasta el trabajo en el siglo XIX de "... Gauss, Bolyai, Lobachevski y Riemann, que se demostró la imposibilidad de deducir el axioma de las paralelas de los demás. Este resultado fue de la mayor importancia intelectual ... Se puede dar "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]". (pág. 10)
El último teorema de Fermat fue conjeturado por Pierre de Fermat en el siglo XVII. 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 de n = 4 usando 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.
Esta profunda paradoja presentada por Jules Richard en 1905 precedió a los trabajos de Kurt Gödel (cf. Nagel y Newman p. 60ff) y de Alan Turing. Se encuentra una definición sucinta en los Principia Mathematica:
Kurt Gödel consideró que su prueba era “una analogía” de la paradoja de Richard, a la que llamó “antinomia de Richard” (la demostración de Gödel es analizada más adelante).
Alan Turing construyó esta paradoja valiéndose de una máquina virtual, y demostró que esta máquina no podría responder a una pregunta simple:
Dicho de otra manera, Turing demostró que la máquina teórica no podría continuar con el cálculo mediante un método de numeración diagonal.
Citando de nuevo a Nagel y Newman (p. 68), "El artículo de Gödel es difícil. Se deben dominar cuarenta y seis definiciones preliminares, junto con varios teoremas previos importantes, antes de alcanzar los resultados principales" (p. 68). De hecho, Nagel y Newman incorporaron una introducción de 67 páginas a su exposición de la prueba, lo que da una correcta imagen de su complejidad, aunque para Martin Davis "Este notable artículo no es solo un hito intelectual, sino que está escrito con una claridad y vigor que hace que sea un placer leerlo" (Davis, en Undecidable, pág. 4).
Entonces, ¿Qué demostró Gödel? En sus propias palabras:
Gödel comparó su prueba con la "antinomia de Richard" (un "antinomia" es una contradicción o una paradoja; para más información, consúltese la paradoja de Richard):
Varias pruebas de indecidibilidad similares aparecieron poco antes y después de la prueba de Turing:
Para una exposición adecuada para no especialistas, consúltese Beltrami (p. 108ff), y véase también Franzén (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 un punto de vista de una máquina de Turing. Chaitin ha escrito varios libros sobre sus esfuerzos y las consecuencias filosóficas y matemáticas que se deducen de ellos.
Una cadena es denominada (algorítmicamente) aleatoria de acuerdo con el concepto de complejidad de Kolmogórov, si no se puede producir a partir de un programa informático más corto. Mientras que la mayoría de las cadenas son aleatorias, ninguna en particular puede probarse así, excepto para un número finito de casos cortos:
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, en la que se solicita "el número entero positivo más pequeño que no pueda ser definido por 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 propia oración subrayada, que en sí misma es una definición del supuesto número, ¡tiene menos de 1000 caracteres!" (Beltrami, pág. 108).
La pregunta "¿Tiene una «ecuación diofántica arbitraria» una solución entera"? es indecidible. Es decir, es imposible responder a la pregunta en todos los casos.
Franzén introduce en su análisis el décimo problema de Hilbert y el teorema de Matiyasevich (también conocido como 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 "alguna" solución en absoluto. El teorema 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 insolubles no es computablemente enumerable" (p. 71).
En ciencias políticas, la paradoja de Arrow establece que es imposible diseñar un sistema electoral que satisfaga un conjunto de cinco axiomas específicos. Este teorema se demuestra comprobando que cuatro de los axiomas juntos implican el opuesto del quinto.
En economía, el teorema de Holmström (un teorema de imposibilidad) demuestra que ningún sistema de incentivos para un equipo de agentes puede satisfacer los tres criterios deseables.
En ciencias naturales, las afirmaciones de imposibilidad (como otras afirmaciones) llegan a ser ampliamente aceptadas como abrumadoramente probables en lugar de considerarse probadas hasta el punto de ser indiscutibles. La base para esta fuerte aceptación es una combinación de evidencia extensa de algo que no está ocurriendo, combinada con una teoría subyacente, muy exitosa en hacer predicciones, cuyas suposiciones llevan lógicamente a la conclusión de que algo es imposible.
Dos ejemplos de imposibilidades ampliamente aceptadas en física son el móvil perpetuo, que viola la ley de conservación de la energía, y la posibilidad de sobrepasar la velocidad de la luz, que viola las implicaciones de teoría de la relatividad especial. Otro es la relación de indeterminación de Heisenberg en la mecánica cuántica, que afirma la imposibilidad de conocer simultáneamente tanto la posición como el momento de una partícula; así como el teorema de Bell: ninguna teoría física de las variables ocultas locales puede 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. Tal contraejemplo requeriría que se reexaminaran los supuestos subyacentes a la teoría que implicaban la imposibilidad.