Prueba de imposibilidad

Uno de los tipos de demostración de imposibilidad más utilizados es la demostración por contradicción . En este tipo de demostración, se muestra que si se asume que una proposición, como la solución a una clase particular de ecuaciones, es verdadera, entonces, mediante deducción, se pueden demostrar dos cosas mutuamente contradictorias, como que un número sea par e impar a la vez, o negativo y positivo a la vez. Dado que la contradicción surge de la suposición original, esto significa que la premisa asumida debe ser imposible.

En cambio, una prueba no constructiva de una afirmación de imposibilidad procedería demostrando 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 ser, de hecho, un contraejemplo válido a la conjetura de imposibilidad. Por ejemplo, se refutó la conjetura de que es imposible que una potencia irracional elevada a otra potencia irracional sea racional , demostrando que uno de dos posibles contraejemplos debe ser un contraejemplo válido, sin mostrar cuál es.

La forma obvia de refutar una conjetura de imposibilidad es proporcionando un único contraejemplo . Por ejemplo, Euler propuso que se necesitaban al menos n potencias n ^-ésimas diferentes para sumar otra potencia n ^-ésima . La conjetura fue refutada en 1966 con un contraejemplo que involucraba solo cuatro potencias 5-ésimas diferentes que sumaban otra potencia 5-ésima.

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 demuestra que es imposible idear un sistema de votación por orden de preferencia que sea a la vez no dictatorial y que satisfaga un requisito básico para el comportamiento racional llamado independencia de alternativas irrelevantes .

El teorema de Gibbard demuestra 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 demuestra 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 considerarse un teorema de imposibilidad que demuestra lo opuesto al teorema de Gibbard, en un sentido coloquial: cualquier juego o sistema de votación puede hacerse resistente a la estrategia incorporando dicha estrategia al mecanismo . Por lo tanto, es imposible diseñar un mecanismo con una solución mejor que la que se puede obtener mediante un mecanismo veraz .

La demostración de Pitágoras alrededor del año 500 a. C. tuvo un profundo impacto en las matemáticas. Demuestra que la raíz cuadrada de 2 no puede expresarse como la razón de dos números enteros. La demostración dividió los números en dos grupos distintos: 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 (maestro de Platón) demostró la irracionalidad de

${\displaystyle {\sqrt {3}},{\sqrt {5}},...,}$

tomando todos los casos separados hasta la raíz de 17  pies cuadrados  ... . ^{[ 6 ]}

Una demostración más general muestra que la raíz m -ésima de un entero N es irracional, a menos que N sea la m -ésima potencia de un entero n . ^{[ 7 ]} Es decir, es imposible expresar la raíz m -ésima de un entero N como la razón 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 la regla (aunque la regla no es estrictamente necesaria). El compás 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 planteaban cómo construir:

1. un par de líneas que trisecan un ángulo dado ;
2. un cubo con un volumen que es el doble del volumen de un cubo dado ;
3. un cuadrado con una área igual a la de un círculo dado;
4. un polígono equilátero con un número arbitrario de lados.

Durante más de 2000 años se hicieron intentos infructuosos para resolver estos problemas; finalmente, en el siglo XIX se demostró que las construcciones deseadas son matemáticamente imposibles sin admitir herramientas adicionales además de un compás. ^{[ 8 ]}

Todos estos son problemas de construcción euclidiana , y las construcciones euclidianas solo 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 cuyos catetos miden una unidad, y puede construirse con una regla y un compás. Pero siglos después de Euclides se demostró 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 la trisección del ángulo general como la duplicación del cubo requieren tomar raíces cúbicas , que no son números construibles .

${\displaystyle \pi }$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.

Porque${\displaystyle \pi }$Se demostró en 1882 que era un número trascendental , no un número euclidiano; de ahí la construcción de una longitud.${\displaystyle \pi }$es imposible partir de un círculo unitario. ^{[ 10 ] [ 11 ]}

El postulado de las paralelas de los Elementos de Euclides equivale a afirmar que, dada una línea recta y un punto que no pertenece a ella, solo se puede trazar una paralela a la línea que pase por ese punto. A diferencia de los demás postulados, se consideraba menos evidente. Nagel y Newman argumentan 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 aquellas que no se cruzan ni siquiera «en el infinito», a diferencia de las asíntotas . ^{[ 12 ]} Esta aparente falta de evidencia llevó a la cuestión de si podría demostrarse a partir de los demás axiomas y postulados euclidianos. Fue solo en el siglo XIX cuando se demostró la imposibilidad de deducir el postulado de las paralelas a partir de los demás en las obras de Gauss , Bolyai , Lobachevsky y Riemann . Estas obras mostraron que el postulado de las paralelas puede, además, ser reemplazado por alternativas, lo que da lugar 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 por sus efectos a largo plazo en la historia matemática posterior». ^{[ 12 ]} En particular, consideran que su resultado es «de suma importancia intelectual», ya que demostró 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 cuatro primeros 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 enteros positivos para la ecuación.${\displaystyle x^{n}+y^{n}=z^{n}}$con${\displaystyle n>2}$El propio Fermat dio una demostración para el caso n  =  4 utilizando su técnica de descenso infinito , y posteriormente se demostraron otros casos especiales, pero el caso general no fue demostrado hasta 1994 por Andrew Wiles .

La pregunta "¿Tiene alguna ecuación diofántica arbitraria una solución entera?" es indecidible . Es decir, es imposible responderla en 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 ". El MRDP utiliza la prueba de indecidibilidad de Turing: "...el conjunto de ecuaciones diofánticas resolubles es un ejemplo de un conjunto computacionalmente enumerable pero no decidible, y el conjunto de ecuaciones diofánticas irresolubles no es computacionalmente enumerable". ^{[ 14 ]}

Esta profunda paradoja presentada por Jules Richard en 1905 influyó en el trabajo de Kurt Gödel ^{[ 15 ]} y Alan Turing. Una definición concisa se encuentra en Principia Mathematica : ^{[ 16 ]}

La paradoja de Richard... es la siguiente. Consideremos todos los decimales que pueden definirse mediante un número finito de palabras [“palabras” son símbolos; el texto en negrita se ha añadido para enfatizar] ; sea E la clase de dichos decimales. Entonces E tiene${\displaystyle \aleph _{0}}$[un número infinito de] términos; por lo tanto, sus miembros pueden ordenarse como el 1.º, 2.º, 3.º, ... 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. Así pues, X es y no es un miembro de E.

Kurt Gödel consideró que su demostración era “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 sencilla: ¿podrá esta máquina determinar si alguna máquina (incluida ella misma) quedará atrapada en un " bucle infinito " improductivo (es decir, si no logra continuar el cálculo del número diagonal)?

Citando a Nagel y Newman (p.  68): «El artículo de Gödel es complejo. Es necesario dominar cuarenta y seis definiciones preliminares, junto con varios teoremas preliminares importantes, antes de llegar a los resultados principales». De hecho, Nagel y Newman requirieron una introducción de 67 páginas para su exposición de la demostración. Pero si el lector se siente lo suficientemente preparado para abordar el artículo, Martin Davis observa que «Este extraordinario trabajo no solo constituye un hito intelectual, sino que está escrito con una claridad y un vigor que hacen que su lectura sea un placer» (Davis en Undecidable, p.  4).

Gödel demostró, con sus propias palabras:

«Es razonable conjeturar que los axiomas [de Principia Mathematica y Peano ] son ​​suficientes para resolver todas las cuestiones matemáticas que pueden expresarse formalmente en los sistemas dados. En lo que sigue se demostrará que esto no es así, sino que existen problemas relativamente sencillos de la teoría de los números enteros ordinarios que no pueden resolverse a partir de los axiomas» (Gödel en Undecidable, p. 4).

Gödel comparó su demostración con la "antinomia de Ricardo" (una " antinomia " es una contradicción o una paradoja; para más información, véase la paradoja de Ricardo ):

"La analogía de este resultado con la antinomia de Richard es inmediatamente evidente; también existe una estrecha relación [14] con la paradoja del mentiroso (nota al pie 14 de Gödel: Toda antinomia epistemológica puede utilizarse para una prueba similar de indecidibilidad)... Así pues, tenemos ante nosotros una proposición que afirma su propia indemostrabilidad [15]. (Su nota al pie 15: Contrariamente a las apariencias, tal proposición no es circular, pues, para empezar, afirma la indemostrabilidad de una fórmula bastante definida)". ^{[ 17 ]}

• El problema de decisión ( Entscheidungsproblem ) fue resuelto por primera vez por Church en abril de 1935, precediendo a Turing por más de un año, ya que el artículo de Turing fue recibido para su publicación en mayo de 1936. ^{[ 18 ]}
• La demostración de Turing se ve dificultada por la cantidad de definiciones necesarias y su naturaleza sutil. Consulte Máquina de Turing y Demostración de Turing para obtener más detalles.
• La primera demostración de Turing (de tres) sigue el esquema de la paradoja de Richard: la máquina de Turing es un algoritmo representado por una cadena de siete letras en una "máquina de computación". Su "computación" consiste en probar todas las máquinas de computación (incluida ella misma) en busca de "círculos" y formar un número diagonal a partir de las computaciones de las máquinas de computación no circulares o "exitosas". Para ello, comienza secuencialmente desde el 1, convirtiendo los números (en base 8) en cadenas de siete letras para su comprobación. Al llegar a su propio número, crea su propia cadena de letras. Decide que es la cadena de letras de una máquina exitosa, pero cuando intenta realizar la computación de esta máquina ( la suya propia ), se bloquea en un círculo y no puede continuar. Así, llegamos a la paradoja de Richard. (Si le resulta confuso, consulte la demostración de Turing para más información).

Varias pruebas de indecidibilidad similares aparecieron poco antes y después de la prueba de Turing:

1. Abril de 1935: Demostración de Alonzo Church ("Un problema irresoluble de la teoría elemental de números"). Su demostración consistió en "...proponer una definición de calculabilidad efectiva... y mostrar, mediante un ejemplo, que no todos los problemas de esta clase son resolubles" (Undecidible, pág.  90).
2. 1946: Problema de correspondencia postal (véase Hopcroft y Ullman ^{[ 19 ]} pág.  193 y ss., pág.  407 para la referencia)
3. Abril de 1947: Demostración de Emil Post ( Recursive Unsolvability of a Problem of Thue ) (Undecidable, pág.  293). Esto se conoce desde entonces como "El problema de la palabra de Thue" o "El problema de la palabra de Thue" ( Axel Thue propuso este problema en un artículo de 1914 (véase Referencias al artículo de Post en Undecidable, pág.  303)).
4. Teorema de Rice : una formulación generalizada del segundo teorema de Turing (cf. Hopcroft y Ullman ^{[ 19 ]} p.  185 y ss.) ^{[ 20 ]}
5. Teorema de Greibach : indecidibilidad en la teoría del lenguaje (cf. Hopcroft y Ullman ^{[ 19 ]} p.  205 y ss. y referencia en la p.  401 ibid: Greibach [1963] "The undecidability of the ambiguity problem for minimal linear grammars," Information and Control 6:2, 117–125, también referencia en la p.  402 ibid: Greibach [1968] "A note on undecidable properties of formal languages," Math Systems Theory 2:1, 1–6.)
6. Preguntas sobre el alicatado de Penrose .

Para una exposición adecuada para no especialistas, véase Beltrami, págs.  108 y siguientes. Véase también Franzen, capítulo 8, págs.  137-148, y Davis, págs.  263-266. El análisis de Franzén es considerablemente más complejo que el de Beltrami y profundiza en Ω, la denominada «probabilidad de parada» de Gregory Chaitin . El análisis anterior de Davis aborda la cuestión desde la perspectiva de una máquina de Turing . Chaitin ha escrito varios libros sobre sus investigaciones y las consiguientes repercusiones filosóficas y matemáticas derivadas de ellas.

Una cadena se denomina (algorítmicamente) aleatoria si no puede generarse 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, salvo un número finito de cadenas cortas:

"Una paráfrasis del resultado de Chaitin es que no puede haber una prueba formal de que una cadena suficientemente larga sea aleatoria..." ^{[ 21 ]}

Beltrami observa que «la demostración de Chaitin está relacionada con una paradoja planteada por el bibliotecario de Oxford G. Berry a principios del siglo XX, que pregunta por "el entero positivo más pequeño que no puede definirse mediante una oración en inglés de 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 ]}