¿Sabemos si existen enunciados matemáticos verdaderos que no se puedan demostrar?

Question

Dado el conjunto de axiomas estándar (no pido que se demuestren), ¿sabemos con seguridad que existe una demostración para todos los teoremas no demostrados? Por ejemplo, creo que la conjetura de Goldbach no está demostrada aunque la "consideremos" verdadera.

Dicho de otro modo, ¿hemos probada que si un enunciado matemático es verdadero, existe una prueba del mismo? ¿Que, por lo tanto, todo lo que es verdadero se puede demostrar, y todo lo que no se puede demostrar no es verdadero? ¿O existe un contraejemplo a esta afirmación?

Si no se ha demostrado ninguna de las dos cosas, ¿tenemos una idea clara de una u otra? ¿Se piensa generalmente que algunos teoremas no pueden tener demostración, o no?

Answer 1

Los descubrimientos relativamente recientes arrojan un número de los llamados "naturales independencia" que proporcionan ejemplos mucho más naturales de independencia que el ejemplo de Gödel basado en la la paradoja del mentiroso (u otras diagonalizaciones sintácticas). Como ejemplo de tales resultados, esbozaré un ejemplo sencillo debido a Goodstein de un teorema concreto de la teoría de los números cuya demostración es independiente de la teoría formal de los números PA (Aritmética de Peano) (tras [Sim]).

Dejemos que $\,b\ge 2\,$ sea un número entero positivo. Cualquier entero no negativo $n$ puede escribirse de forma única en base $b$ $$\smash{n\, =\, c_1 b^{\large n_1} +\, \cdots + c_k b^{\large n_k}} $$

donde $\,k \ge 0,\,$ y $\, 0 < c_i < b,\,$ y $\, n_1 > \ldots > n_k \ge 0,\,$ para $\,i = 1, \ldots, k.$

Por ejemplo, la base $\,2\,$ representación de $\,266\,$ es $$266 = 2^8 + 2^3 + 2$$

Podemos ampliar esto escribiendo cada uno de los exponentes $\,n_1,\ldots,n_k\,$ en la base $\,b\,$ notación, y luego hacer lo mismo para cada uno de los exponentes en las representaciones resultantes, $\ldots,\,$ hasta que el proceso se detenga. Así se obtiene la llamada "base hereditaria". $\,b\,$ representación de $\,n$ '. Por ejemplo, la base hereditaria $2$ representación de $\,266\,$ es $$\smash{266 = 2^{\large 2^{2+1}}\! + 2^{2+1} + 2} $$

Dejemos que $\,B_{\,b}(n)$ sea el número entero no negativo que resulta si tomamos el base hereditaria $\,b\,$ representación de $\,n\,$ y luego sintácticamente reemplazar cada $\,b\,$ por $\,b+1,\,$ es decir $\,B_{\,b}\,$ es un operador de cambio de base que "bate la base de $\,b\,$ hasta $\,b+1.\,$ Por ejemplo, al golpear la base de $\,2\,$ a $\,3\,$ en la ecuación anterior da como resultado $$\smash{B_{2}(266) = 3^{\large 3^{3+1}}\! + 3^{3+1} + 3\quad\ \ \ }$$

Consideremos una secuencia de números enteros obtenida aplicando repetidamente la operación: bumpear la base y luego restarle uno al resultado. Por ejemplo, aplicando iterativamente esta operación a $\,266\,$ rinde $$\begin{eqnarray} 266_0 &=&\ 2^{\large 2^{2+1}}\! + 2^{2+1} + 2\\ 266_1 &=&\ 3^{\large 3^{3+1}}\! + 3^{3+1} + 3 - 1\ =\ B_2(266_0) - 1 \\ ~ \ &=&\ 3^{\large 3^{3+1}}\! + 3^{3+1} + 2 \\ 266_2 &=&\ 4^{\large 4^{4+1}}\! + 4^{4+1} + 1\qquad\! =\ B_3(266_1) - 1 \\ 266_3 &=&\ 5^{\large5^{5+1}}\! + 5^{5+1}\phantom{ + 2}\qquad\ =\ B_4(266_2) - 1 \\ 266_4 &=&\ 6^{\large 6^{6+1}}\! + \color{#0a0}{6^{6+1}\! - 1} \\ ~ \ &&\ \textrm{using}\quad \color{#0a0}{6^7\ -\,\ 1}\ =\ \color{#c00}{5555555}\, \textrm{ in base } 6 \\ ~ \ &=&\ 6^{\large 6^{6+1}}\! + \color{#c00}5\cdot 6^6 + \color{#c00}5\cdot 6^5 + \,\cdots + \color{#c00}5\cdot 6 + \color{#c00}5 \\ 266_5 &=&\ 7^{\large 7^{7+1}}\! + 5\cdot 7^7 + 5\cdot 7^5 +\, \cdots + 5\cdot 7 + 4 \\ &\vdots & \\ 266_{k+1} &=& \ \qquad\quad\ \cdots\qquad\quad\ = \ B_{k+2}(266_k) - 1 \\ \end{eqnarray}$$

En general, si iniciamos este procedimiento en el número entero $\,n\,$ entonces obtenemos lo que se conoce como Secuencia de Goodstein a partir de $\,n.$

Más concretamente, para cada número entero no negativo $\,n\,$ definimos recursivamente una secuencia de enteros no negativos $\,n_0,\, n_1,\, \ldots ,\, n_k,\ldots\,$ por $$\begin{eqnarray} n_0\ &:=&\ n \\ n_{k+1}\ &:=&\ \begin{cases} B_{k+2}(n_k) - 1 &\mbox{if }\ n_k > 0 \\ \,0 &\mbox{if }\ n_k = 0 \end{cases} \\ \end{eqnarray}$$

Si examinamos la anterior secuencia de Goodstein para $\,266\,$ numéricamente encontramos que la secuencia aumenta inicialmente de forma extremadamente rápida:

$$\begin{eqnarray} 2^{\large 2^{2+1}}\!+2^{2+1}+2\ &\sim&\ 2^{\large 2^3} &\sim&\, 3\cdot 10^2 \\ 3^{\large 3^{3+1}}\!+3^{3+1}+2\ &\sim&\ 3^{\large 3^4} &\sim&\, 4\cdot 10^{38} \\ 4^{\large 4^{4+1}}\!+4^{4+1}+1\ &\sim&\ 4^{\large 4^5} &\sim&\, 3\cdot 10^{616} \\ 5^{\large 5^{5+1}}\!+5^{5+1}\ \ \phantom{+ 2} \ &\sim&\ 5^{\large 5^6} &\sim&\, 3\cdot 10^{10921} \\ 6^{\large 6^{6+1}}\!+5\cdot 6^{6}\quad\!+5\cdot 6^5\ \:+\cdots +5\cdot 6\ \ +5\ &\sim&\ 6^{\large 6^7} &\sim&\, 4\cdot 10^{217832} \\ 7^{\large 7^{7+1}}\!+5\cdot 7^{7}\quad\!+5\cdot 7^5\ \:+\cdots +5\cdot 7\ \ +4\ &\sim&\ 7^{\large 7^8} &\sim&\, 1\cdot 10^{4871822} \\ 8^{\large 8^{8+1}}\!+5\cdot 8^{8}\quad\!+5\cdot 8^5\ \: +\cdots +5\cdot 8\ \ +3\ &\sim&\ 8^{\large 8^9} &\sim&\, 2\cdot 10^{121210686} \\ 9^{\large 9^{9+1}}\!+5\cdot 9^{9}\quad\!+5\cdot 9^5\ \: +\cdots +5\cdot 9\ \ +2\ &\sim&\ 9^{\large 9^{10}} &\sim&\, 5\cdot 10^{3327237896} \\ 10^{\large 10^{10+1}}\!\!\!+5\cdot 10^{10}\!+5\cdot 10^5\!+\cdots +5\cdot 10+1\ &\sim&\ 10^{\large 10^{11}}\!\!\!\! &\sim&\, 1\cdot 10^{100000000000} \\ \end{eqnarray}$$

Sin embargo, a pesar de las primeras impresiones numéricas, se puede demostrar que esta secuencia converge a $\,0.\,$ En otras palabras, $\,266_k = 0\,$ para todos suficientemente grande $\,k.\,$ Este sorprendente resultado se debe a Goodstein $(1944)$ que en realidad demostró el mismo resultado para todo Goodstein secuencias:

Teorema de Goodstein $\ $ Para todos $\,n\,$ existe $\,k\,$ tal que $\,n_k = 0.\,$ En otras palabras, toda secuencia de Goodstein converge a $\,0.$

El secreto subyacente al teorema de Goodstein es que la herencia expresión de $\,n\,$ en la base $\,b\,$ imita una notación ordinal para todos los ordinales menores que epsilon nought $\,\varepsilon_0 = \omega^{\large \omega^{\omega^{\Large\cdot^{\cdot^\cdot}}}}\!\!\! =\, \sup \{ \omega,\, \omega^{\omega}\!,\, \omega^{\large \omega^{\omega}}\!,\, \omega^{\large \omega^{\omega^\omega}}\!,\, \dots\, \}$ . Para tales ordinales, la base bumping deja el ordinal fijo, pero la sustracción de uno disminuye el ordinal. Pero estos ordinales están bien ordenados, lo que nos permite concluir que una secuencia de Goodstein converge finalmente a cero. En realidad, Goodstein demostró su teorema para una función de base creciente general $\,f:\Bbb N\to \Bbb N\,$ (vs. $\,f(b)=b+1\,$ arriba). Demostró que la convergencia de todas esas $f$ -Las secuencias de Goodstein son equivalentes a la inducción transfinita debajo de $\,\epsilon_0.$

Una de las principales medidas de resistencia de un sistema lógico es el tamaño del ordinal más grande para el que la inducción transfinita es válida. Es un resultado clásico de Gentzen que la consistencia de la PA (Aritmética de Peano, o teoría formal de los números) puede demostrarse por inducción transfinita sobre ordinales inferiores a $\,\epsilon_0.\,$ Pero sabemos del segundo teorema de incompletitud de Godel que la consistencia de PA no puede ser demostrada en PA. De ello se deduce que tampoco se puede demostrar el el teorema de Goodstein en PA. Así tenemos un ejemplo de un enunciado teórico numérico concreto muy simple en PA cuya prueba es, sin embargo, independiente de PA.

Otra forma de ver que el teorema de Goodstein no se puede demostrar en PA es observar que la secuencia tarda demasiado en terminar, por ejemplo

$$ 4_k\,\text{ first reaches}\,\ 0\ \,\text{for }\, k\, =\, 3\cdot(2^{402653211}\!-1)\,\sim\, 10^{121210695}$$

En general, si "para todos $\,n\,$ existe $\,k\,$ tal que $\,P(n,k)$ ' es es demostrable, entonces debe ser atestiguado por una elección demostrablemente computable función de elección $\,F\!:\, $ para todos $\,n\!:\ P(n,F(n)).\,$ Pero el problema es que $\,F(n)\,$ crece demasiado rápido como para que sea demostrablemente computable en PA, ver [Smo] $1980$ para más detalles.

El teorema de Goodstein fue uno de los primeros ejemplos del llamado fenómenos de independencia natural", que la mayoría de los lógicos consideran los lógicos como más naturales que los resultados de incompletitud metamatemática descubiertos por Gödel. resultados de incompletitud descubiertos por Gödel. Otros ejemplos combinatoria finita fueron descubiertos en la misma época, por ejemplo, una forma finita del teorema de Ramsey, y una forma finita del teorema del árbol de Kruskal, véase [KiP], [Smo] y [Gal]. [Kip] presenta el juego de Hércules contra Hidra, que proporciona un ejemplo elemental de un teorema del árbol combinatorio finito (una forma más gráfica de la secuencia de Goodstein).

El teorema del árbol de Kruskal desempeña un papel fundamental en la informática informática porque es una de las principales herramientas para demostrar que ciertos ordenamientos en los árboles están bien fundados. Estos ordenamientos juegan un papel crucial en la demostración de la terminación de las reglas de reescritura y la corrección de la terminación ecuacional de Knuth-Bendix de Knuth-Bendix. Véase [Gal] para un estudio de los resultados en esta área.

Para más detalles, véanse las siguientes referencias, especialmente los documentos de Smorynski. Comience con el libro de Rucker si no sabe de lógica, luego lógica, luego pase a los documentos de Smorynski, y después a los otros que son trabajos de investigación originales. Para trabajos más recientes, vea las referencias citadas en Gallier, especialmente a la escuela de Friedman de "Matemáticas Inversas", y ver [JSL].

Referencias

[Gal] Gallier, Jean. ¿Qué tiene de especial el teorema de Kruskal y el ordinal $\Gamma_0$ ?
Un estudio de algunos resultados en la teoría de la prueba,
Ann. Pure and Applied Logic, 53 (1991) 199-260.

[HFR] Harrington, L.A. et.al. (editores)
La investigación de Harvey Friedman sobre los fundamentos de las matemáticas, Elsevier 1985.

[KiP] Kirby, Laurie, y Paris, Jeff. Resultados de independencia accesibles para la aritmética de Peano,
Bula. London Math. Soc., 14 (1982), 285-293.

[JSL] The Journal of Symbolic Logic,* v. 53, nº 2, 1988
Este número contiene las ponencias del Simposio "Hilbert's Program 60 años después".

[Kol] Kolata, Gina. ¿Es importante el teorema de Goedel para las matemáticas?
Ciencia 218 19/11/1982, 779-780; reproducido en [HFR]

[Ruc] Rucker, Rudy. El infinito y la mente, 1995, Princeton Univ. Press.

[Sim] Simpson, Stephen G. Teoremas no demostrables y funciones de crecimiento rápido,
Matemáticas contemporáneas. 65 1987, 359-394.

[Smo] Smorynski, Craig. (los tres artículos se reproducen en [HFR])
Algunas funciones de rápido crecimiento, Matemáticas. Inteligencia.., 2 1980, 149-154.
Las variedades de la experiencia arbórea, Matemáticas. Inteligencia.., 4 1982, 182-188.
"Grandes" noticias de Arquímedes a Friedman, Avisos AMS, 30 1983, 251-256.

[Spe] Spencer, Joel. Grandes números y teoremas indemostrables,
Amer. Math. Monthly, Dic 1983, 669-675.

Answer 2

Gödel fue capaz de construir un enunciado que dice "este enunciado no es demostrable".

La prueba es algo así. Primero crea un esquema de enumeración de documentos escritos. A continuación, crear una declaración en la teoría de números " $P(x,y,z)$ ", que significa "si $x$ se interpreta como un programa de ordenador, y se introduce el valor $y$ , entonces el valor $z$ es la salida". (Esta parte fue bastante difícil, pero intuitivamente se ve que se puede hacer).

A continuación, escriba un programa informático que compruebe las pruebas. Crear pruebas es indecidible, y es difícil crear un programa que lo haga. Pero se puede crear un programa que compruebe una prueba. Supongamos que este programa se convierte en el número literal $n$ en nuestro esquema de enumeración. Entonces podemos crear una declaración en teoría de números " $Q(x)$ " ${}={}$ " $\exists y:P(n,\text{cat}(x,y),1)$ ". Aquí $\text{cat}(x,y)$ concatena un enunciado escrito en teoría de números $x$ con su prueba $y$ . Así que $Q(x)$ dice " $x$ es demostrable".

Ahora construye en teoría de números una fórmula $S(x,y)$ , lo que significa tomar la declaración enumerada por $x$ y siempre que vea el símbolo $x$ en él, sustitúyalo por el número literal representado por $y$ .

Ahora considere la afirmación " $T(x)$ " ${}={}$ " $\text{not} \ Q(S(x,x))$ ". Supongamos que esto enumera como el número $m$ .

Entonces " $T(m)$ " es una afirmación en teoría de números que dice "esta afirmación no es demostrable".

Ahora supongamos que " $T(m)$ "es demostrable. Entonces es verdadera. Pero si es cierto, entonces no es demostrable (porque eso es lo que dice la afirmación).

Así que " $T(m)$ " no es claramente demostrable. Por lo tanto, es cierto.

Sé que me faltan algunas cuestiones técnicas importantes. Las responderé lo mejor que pueda cuando se me pregunten. Pero este es el esquema de la demostración del teorema de incompletitud de Gödel.

Answer 3

"No se puede demostrar" es una noción inapropiadamente vaga para la pregunta que quieres hacer. ¿Demostrado a partir de qué axiomas? En un sistema lógico que incluye la conjetura de Goldbach como axioma, la prueba de la conjetura de Goldbach sólo tiene una línea. Así que para que la pregunta tenga sentido, no puedes decir simplemente "se ha demostrado"; tienes que decir "se ha demostrado a partir de tales y tales axiomas".

Existe un conjunto estándar de axiomas para la aritmética, llamado Axiomas de Peano . Nos gustan estos axiomas porque son intuitivos y sencillos, y también porque parecen ser lo suficientemente potentes como para demostrar casi todas las cosas que nos gustaría demostrar sobre la aritmética.

Sin embargo, se sabe que hay enunciados verdaderos particulares de la aritmética que no son demostrables a partir de los axiomas de Peano; Teorema de Goodstein es un ejemplo.

El famoso teorema de incompletitud de Gödel afirma que cualquier Un sistema de axiomas lo suficientemente expresivo como para demostrar todos los enunciados verdaderos de la aritmética debe demostrar también algunos enunciados falsos de la aritmética. A la inversa, cualquier sistema de axiomas que demuestre sólo enunciados verdaderos de la aritmética debe dejar de demostrar algunos enunciados verdaderos de la aritmética. La prueba es constructiva; partiendo de los axiomas dados, construye un enunciado (muy artificial) de la aritmética $G$ lo que es cierto si y sólo si no hay ninguna prueba de $G$ de los axiomas. O bien $G$ es falsa y tiene una prueba, o es verdadera y no tiene ninguna prueba.

Answer 4

El teorema de incompletitud de Gödel es uno de esos resultados ampliamente incomprendidos.

A grandes rasgos, significa que en el contexto de la aritmética sólo puede haber dos de los siguientes:

• Axiomas decidibles
• Consistencia
• Integridad

Las "verdades que no se pueden demostrar" es una abreviatura del contexto de elección de axiomas decidibles, la consistencia, pero la falta de completitud. Esto significa que hay sentencias P para las que no hay prueba de P o no P.

Puedes añadir más axiomas de aritmética para que cada frase P tenga una prueba de P o no P. Eso dará completitud, consistencia, pero los axiomas serán necesariamente indecidibles debido al teorema de incompletitud de Gödel.

Un punto que a menudo se pasa por alto en la afirmación "verdades que no se pueden demostrar" es que tiene sentido hablar de axiomas indecidibles, completos y consistentes de la aritmética, en los que cada frase verdadera se puede demostrar. Pero tiene el coste de los axiomas indecidibles, por lo que no es especialmente útil.

Answer 5

Entre las muchas y excelentes respuestas que ha recibido, nadie parece haber respondido directamente a su pregunta.

La conjetura de Goldbach puede ser verdadera y demostrable, verdadera pero no demostrable utilizando las "reglas normales de la aritmética", o falsa.

Hay fuertes argumentos estadísticos que sugieren que es casi seguro.

No se sabe si es demostrable utilizando las "leyes normales de la aritmética", como las que se utilizan para demostrar el último teorema de Fermat o el teorema de los números primos y todo lo que aprendiste en las matemáticas del instituto. Asumir que no se puede demostrar es un completo callejón sin salida. Para que te interese, tienes que suponer que es verdadera y buscar una prueba, o suponer que es falsa y buscar un contraejemplo.