En matemáticas , una prueba de imposibilidad es una prueba que demuestra que un problema particular no puede resolverse como se describe en la reivindicación, o que un conjunto particular de problemas no puede resolverse en general. Este caso también se conoce como prueba negativa , prueba de un teorema de imposibilidad o resultado negativo . La prueba de la imposibilidad a menudo son las resoluciones de décadas o siglos de trabajo intentando encontrar una solución, y que finalmente demuestran 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 de imposibilidad importante fue la prueba de Ferdinand von Lindemann en 1882, que demostró 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 sólo un subconjunto del número algebraico Los números se pueden construir con compás y regla . Otros dos problemas clásicos ( trisecar el ángulo general y duplicar el 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.
Un problema que surgió en el siglo XVI fue la creación de una fórmula general usando radicales para expresar la solución de cualquier ecuación polinómica de grado fijo k , donde k ≥ 5. En la década de 1820, el teorema de Abel-Ruffini (también conocido como teorema de imposibilidad de Abel ) demostró que esto era imposible, [3] utilizando conceptos como grupos solubles de la teoría de Galois , un nuevo subcampo del álgebra abstracta .
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. [4]
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 . [5] 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.
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 [6] 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.
Hay dos métodos alternativos para refutar una conjetura de que algo es imposible: mediante 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, 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. 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 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 contraejemplos posibles debe ser un contraejemplo válido, sin mostrar cuál es.
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 . Esta bifurcación fue utilizada por Cantor en su método 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.
Se desconoce cuándo ni quién descubrió el "teorema de Pitágoras". Difícilmente el descubrimiento pudo haber sido hecho por el propio Pitágoras, pero ciertamente se hizo en su escuela. Pitágoras vivió entre el 570 y el 490 a. C. Demócrito, nacido alrededor del 470 a. C., escribió sobre líneas y sólidos irracionales ...
- Heath, [ cita necesaria ]
Siguieron pruebas para varias raíces cuadradas de los números primos hasta 17.
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... [7]
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 números enteros a y b , que no comparten ningún factor primo común , excepto en los casos en que b = 1.
Tres preguntas famosas de la geometría griega fueron cómo:
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 lógicamente imposibles. [9]
Un cuarto problema de los antiguos griegos era construir un polígono equilátero con un número específico n de lados, más allá de los casos básicos n = 3, 4, 5, 6 que sabían construir.
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). [10] 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 con compás y regla.
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 [11]
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 polinómica . Por lo tanto, como en 1882 se demostró que es un número trascendental y, por lo tanto, por definición no es un número algebraico, no es un número euclidiano. Por lo tanto, la construcción de una longitud a partir de un círculo unitario es imposible, [12] y el círculo no se puede cuadrar.
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 . [13] 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". [13] 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]". [14]
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 .
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 ). Es recomendado [ ¿ por quién? ] que la mayoría de los lectores ven primero a Nagel y Newman.
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 una 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 llama (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 1.000 caracteres. Sin embargo, la frase entre comillas, que es en sí misma una definición del supuesto número, ¡tiene menos de 1.000 caracteres! [22]
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". [23]
En ciencia política , el teorema de imposibilidad de Arrow establece que es imposible idear un sistema de votación que satisfaga un conjunto de cinco axiomas específicos. Este teorema se demuestra demostrando que cuatro de los axiomas juntos implican lo contrario del quinto.
De manera similar, el teorema de Gibbard-Satterthwaite establece que ningún sistema de votación puede tener más de dos alternativas, ser robusto a la votación estratégica e impedir que un solo votante decida el resultado.
En economía , el teorema de Holmström es un teorema de imposibilidad que demuestra que ningún sistema de incentivos para un equipo de agentes puede satisfacer los tres criterios deseables.
En las 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 incuestionables. 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.
