¿Puede la indemostrabilidad ser indemostrable? ¿Existe una $\omega$ -¿Inprobabilidad doble?

Question

Estaba pensando en la incomprobabilidad. Sólo quería saber si es posible hacer una frontera concreta entre los problemas demostrables y los no demostrables en un determinado sistema axiomático.

Sabemos que hay una afirmación que es verdadera pero no demostrable. Entonces, ¿es posible que una afirmación sea verdadera e indemostrable, pero que la indemostrabilidad sea indemostrable?

Podemos extenderlo a una cuestión de "improbabilidad de la improbabilidad de la improbabilidad", o cualquier número finito de veces, o incluso $\omega$ tiempos....

No tengo ni idea. ¿Ha habido alguna investigación sobre este tipo de tema?

Answer 1

Lógica de la probabilidad

Podría ser mucho más claro reescribir todo esto de la "demostrabilidad" en la lógica de la demostrabilidad donde " $P$ es demostrable" se denota por " $□ P$ ", donde " $□$ "es un operador modal. Entonces, dada cualquier teoría de primer orden $T$ que es lo suficientemente fuerte como para realizar la manipulación de cadenas o equivalente (como PA con alguna codificación adecuada) y tiene validez de prueba decidible, $T$ satisfará las condiciones de demostrabilidad de Hilbert-Bernays, así como el teorema del punto fijo modal: $\def\imp{\rightarrow}$ $\def\eq{\leftrightarrow}$ $\def\nn{\mathbb{N}}$ $\def\pa{\mathrm{PA}}$ $\def\zf{\mathrm{ZF}}$

(D1) Si $T \vdash P$ entonces $T \vdash □ P$ para cualquier frase $P$ en $T$ .

(D3) $T \vdash □ P \imp □ □ P$ para cualquier frase $P$ en $T$ .

(D2) $T \vdash □ P \land □ ( P \imp Q ) \imp □ Q$ para cualquier frase $P,Q$ en $T$ .

(F) Dado cualquier $1$ -sentencia con parámetro proposicional $P$ en $T$ de manera que cada ocurrencia del parámetro en $P$ está limitado por algún $□$ hay una frase $Q$ en $T$ para que $T \vdash Q \eq P(Q)$ .

Teorema de Lob y segundo teorema de incompletitud de Godel

Ahora, ten en cuenta que usando esto puedes probar Teorema de Lob en forma externa e interna para cualquier frase $P$ en $T$ :

(L*) Si $T \vdash □ P \imp P$ entonces $T \vdash P$ .

(L) $T \vdash □ ( □ P \imp P ) \imp □ P$ .

Prueba : Véase el artículo de Wikipedia.

De estos aplicados a $P = \bot$ obtenemos inmediatamente el segundo teorema de incompletitud de Godel (en forma externa e interna):

(GI*) Si $T$ es consistente entonces $T \nvdash \neg □ \bot$ .

(GI) $T \vdash \neg □ \bot \imp \neg □ \neg □ \bot$ .

Dos teoremas sobre la incomprobabilidad interna

También obtenemos los dos teoremas siguientes.

(U*) Si $T$ es consistente, entonces $T \nvdash \neg □ P$ para cada frase $P$ en $T$ .

Prueba : Tome cualquier frase $P$ en $T$ . Entonces $T \vdash □ ( \bot \imp P )$ por (D1), y por tanto $T \vdash □ \bot \imp □ P$ por (D2). Si $T \vdash \neg □ P$ entonces $T \vdash \neg □ \bot$ , contradiciendo a (GI*). Por lo tanto, $T \nvdash \neg □ P$ .

(U) $T \vdash \neg □ \bot \imp \neg □ \neg □ P$ para cada frase $P$ en $T$ .

Prueba : $T \vdash \neg □ P \imp \neg □ \bot$ como se muestra arriba, y por lo tanto $T \vdash □ ( \neg □ P \imp \neg □ \bot )$ por (D1). Así, $T \vdash □ \neg □ P \imp □ \neg □ \bot$ por (D2). También $T \vdash □ \neg □ \bot \imp □ \bot$ por (GI). Por lo tanto, combinando obtenemos $T \vdash \neg □ \bot \imp \neg □ \neg □ P$ . Obsérvese que a partir de esto también obtenemos $T \vdash \neg □ P \imp \neg □ \neg □ P$ .

Observaciones

El primer teorema muestra que $T$ es incapaz de demostrar en sí mismo que cualquier frase es indemostrable sobre $T$ , a menos que $T$ es inconsistente en cuyo caso, por supuesto $T$ demuestra y refuta todo. El segundo teorema demuestra que $T$ sabe" que si ella misma es consistente (o que hay alguna sentencia indemostrable), ¡entonces no puede demostrar ninguna sentencia indemostrable sobre ella misma! Esto responde a su pregunta si se refiere a la incomprobabilidad interna .

Ejemplo explícito de frase independiente no demostrable

Lo anterior se realiza dentro de $T$ pero si vamos en el exterior podemos decir aún más, a saber, que realmente podemos mostrar una ejemplo explícito de una frase independiente no comprobable cuando estamos en el meta-sistema y estudiando $T$ . Nótese que esto no contradice el hecho de que $T$ no conoce ninguna frase de este tipo, básicamente porque $T$ "conoce menos que" el metasistema; todos los metasistemas razonables "conocen" el conjunto de oraciones que $T$ no demuestra, pero $T$ no lo hace.

Dada cualquier frase $P$ en $T$ aunque $T$ siempre demuestra $P \lor \neg P$ Puede que no resulte $□ P \lor □ \neg P$ ni puede demostrar siempre $□ P \lor □ \neg P \lor □ \neg ( □ P \lor □ \neg P )$ porque existe la clara posibilidad de que $\neg □ \neg ( □ P \lor □ \neg P )$ . Para ver por qué, fíjate en lo siguiente. (En nuestro metasistema, donde asumimos la existencia y las propiedades de $\nn$ . Además, deja que " $□$ " denotan probabilidad sobre $\pa$ si no se especifica).

1. $\nn \nvDash □ □ \bot$ si no, podemos extraer una prueba de $□ \bot$ en $\pa$ y luego una prueba de $\bot$ lo que contradice la coherencia de $\pa$ .

2. $\nn \nvDash □ \neg □ \bot$ si no, podemos extraer una prueba de $\neg □ \bot$ en $\pa$ , lo que contradice el teorema de incompletitud de Godel.

3. $\nn \nvDash □ \neg ( □ □ \bot \lor □ \neg □ \bot )$ de lo contrario podemos obtener una prueba de $\neg □ □ \bot$ en $\pa$ que da una prueba de $\neg □ \bot$ , contradiciendo de nuevo el teorema de Godel.

4. Por lo tanto, $\nn \nvDash □ C \lor □ \neg C \lor □ \neg ( □ C \lor □ \neg C )$ donde $C = □ \bot$ y por lo tanto $\pa$ no puede probarlo porque $\nn \vDash PA$ . Del mismo modo, si $C = \neg □ \bot$ lo que es cierto en $\nn$ .

5. También $\nn \vDash \neg □ \neg ( □ C \lor □ \neg C )$ pero (por U* y nuestra suposición de que $\nn$ satisface $\pa$ ) $\pa$ ¡no puede probarlo!

Esto demuestra que existe una sentencia $C$ que es cierto en $\nn$ pero que $\pa$ no demuestra " $C$ es demostrable o $(\neg C)$ es demostrable o que ( $C$ es independiente ) es demostrable o que ( $C$ es independiente ) es indemostrable". Cualquier $C$ es, por supuesto, indemostrable en $\pa$ (por D1).

Por lo tanto, esta es una respuesta positiva fuerte a su pregunta si usted está pidiendo una oración que es externamente verdadera e independiente pero internamente indemostrable .

Otras observaciones

Arreglemos $\zf$ como nuestro metasistema. A partir de ahora utilizaremos " $□_T$ " para denotar la demostrabilidad sobre $T$ ya que difiere de $T$ a $T$ .

Por (GI) sabemos que:

1. $\pa \nvdash \neg □_\pa \bot$ .

2. $\zf \nvdash \neg □_\zf \bot$ .

Pero por la propia axiomatización de $\zf$ también tenemos:

3. $\zf \vdash \neg □_\pa \bot$ .

No hay ninguna contradicción, porque $\zf$ es estrictamente más fuerte que $\pa$ Desde el momento en que fue hecho asumir la existencia de un modelo de $\pa$ pero muestra que tenemos que declarar con precisión qué estamos hablando de probabilidad por encima.

Además, $\pa$ puede razonar un poco sobre las pruebas sobre $\zf$ ya que las pruebas son sólo cadenas, por lo que tenemos:

4. $\pa \nvdash \neg □_\zf \bot$ ya que $\pa \vdash □_\pa \bot \imp □_\zf \bot$ .

Answer 2

Se ha señalado en los comentarios que esta respuesta tiene un fallo importante, ya que pretendía esbozar una prueba en términos poco formales, pero al hacerlo se perdió un punto de gran importancia. Aunque el trabajo que sigue se desprende de los cuatro axiomas que planteo a continuación, no hay una forma evidente de formalizar una noción de demostrabilidad que satisfaga los axiomas que se exponen a continuación. Esto debería preocuparnos, porque tener la "demostrabilidad" simplemente como una palabra que no corresponde a ninguna noción formal es problemático.

Los comentarios contienen más discusiones y esta respuesta contiene un tratamiento formal de la cuestión.

---

En primer lugar, examinemos qué significa que un problema sea 2 veces indemostrable. Según su notación, llamamos a un problema n veces indemostrable si no hay ninguna prueba de que el problema es (n-1)-inmostrable o no (donde 0 veces indemostrable se entiende como "demostrable"). En este caso, un enunciado que es 1 veces indemostrable es uno que es independiente de un sistema.

Entendemos por "demostrable" que "existe una prueba o refutación de $P$ ".

(A) Si $P$ es demostrable entonces " $P$ es demostrable" es demostrable.

Esto parece claro, ya que, sabiendo que una prueba de $P$ existe, podemos ciertamente encontrarlo enumerando todas las pruebas (si los axiomas son recursivamente enumerables), y así demostrar que $P$ es demostrable.

(B) $P$ es demostrable si y sólo si $\neg P$ es demostrable.

Claramente, si una prueba o refutación de $P$ existe, podemos fácilmente refutar o probar $\neg P$ .

(C) Si $P$ es demostrable y $P\rightarrow Q$ es demostrable, entonces $Q$ es demostrable.

Lo cual está claro, dado cómo se construyen las pruebas. También necesitamos

(D) Si $P$ es probadamente verdadera, entonces $P$ es cierto.

A partir de aquí, podemos argumentar:

1. Si $P$ es demostrable, entonces " $P$ es demostrable" es demostrable (desde (A)).
2. Si " $P$ es demostrable" es indemostrable, entonces $P$ es indemostrable (contrapositivo de (1)).
3. Si " $P$ es indemostrable" es indemostrable, entonces " $P$ es demostrable" es indemostrable (de (B)).
4. Si " $P$ es indemostrable" es indemostrable, entonces $P$ es indemostrable (silogismo de (3) y (2))

Lo cual es claramente un problema, ya que podemos llegar rápidamente a una contradicción si tomamos

5. "" $P$ es indemostrable" es indemostrable" es demostrablemente cierto.
6. " $P$ es indemostrable" es indemostrable. (de (D))
7. " $P$ es indemostrable" es demostrable (a partir de 5, 4 y (C), observando que 4 es demostrable ya que lo acabamos de demostrar).
8. " $P$ es indemostrable" es demostrable y " $P$ es indemostrable" es indemostrable (6 y 7)

Una contradicción. Como aceptamos A, B y C, debe ser que la dada (5) implica una contradicción y por tanto es falsa, lo que significa que nunca se puede demostrar que $P$ es 2 veces indemostrable -por lo tanto, si una afirmación es 2 veces indemostrable, también es 3 veces indemostrable, ya que no podría existir ninguna prueba de que es 2 veces indemostrable. De hecho, cada ordinal superior sufre el mismo argumento.

Así, podríamos considerar que existen potencialmente 4 clases de declaraciones:

• Los que tienen una prueba
• Los que tienen una refutación
• Los que se pueden demostrar no tienen ni prueba ni refutación.
• Aquellos de los que no se puede decir nada. (es decir, los indemostrables, pero de los que no se puede decir nada, porque cualquier prueba de que un enunciado pertenece a esta clase es inconsistente por el argumento anterior)

El problema es que nunca podemos elegir un ejemplo de un enunciado en algún sistema formal y demostrar, utilizando ese mismo sistema, que un enunciado está en la última clase. Utilizando un enunciado similar al de Godel -aunque sin proporcionar ninguna construcción del mismo, y asumiendo que una construcción similar a la de Godel sería suficiente- se podría cuestionar ese enunciado

Esta afirmación es indemostrable o falsa.

No se podría demostrar que es falsa (ya que es verdadera si existe una prueba de que es falsa), ni demostrar que es verdadera (ya que afirma que no existe tal prueba), ni demostrar que es independiente (ya que eso demostraría también la afirmación), ni demostrar que es doblemente independiente (ya que tal prueba demostraría que es independiente). Esto es paradójico, pero demuestra que debe haber algunos enunciados que no pueden demostrarse en ninguna clase, lo que implica que hay enunciados doblemente indemostrables.

---

Una prueba más concreta, pero quizás menos satisfactoria, de que los enunciados de la cuarta clase existen si consideramos las máquinas de Turing. Consideremos que, si una máquina de turing se detiene, podemos probar que se detenga - simplemente lo ejecutamos y, al final, observamos que se ha detenido. Lo contrario es que, si no hay prueba de que la máquina de Turing se detenga, entonces no debe detenerse -lo que significa que, de forma similar a lo anterior, si hay una prueba de que no hay prueba de que una máquina de Turing se detenga, podemos demostrar que la máquina no se detiene. Por lo tanto, nunca se puede demostrar que "T se detiene" es indemostrable*.

Ahora bien, si suponemos que la teoría de la que hablamos satisface las restricciones de Teorema de Godel . Las restricciones pueden expresarse como "El sistema axiomático puede simular máquinas de Turing y las máquinas de Turing pueden enumerar los axiomas". Esto significa que, para cualquier máquina $T$ podríamos crear una máquina que enumere cada teorema de un sistema y busca una prueba de " $T$ se detiene" o " $T$ no se detiene" - y, si nuestro sistema siempre resulta "verdadero" o "falso" (ya que, "indecidible" fue descartado en el párrafo anterior), estaría garantizado que eventualmente encontraría uno. Esto implicaría que el problema de parada es decidible. No lo es. Ergo, no se puede demostrar que algunas afirmaciones sean verdaderas, falsas o indecidibles.

Estas pruebas funcionan intuitivamente; hay sistemas formales que las desafían (por ejemplo, cada afirmación de la teoría de aritmética verdadera es verdadera o falsa - pero tiene infinitos axiomas). Esto es difícil de evitar, ya que la "indemostrabilidad" es, por supuesto, relativa a un sistema formal dado, y es posible que "P es indemostrable es indemostrable en el sistema A" sea un teorema de un sistema diferente B. Sin embargo, cualquier sistema que satisfaga las condiciones de la prueba de Godel tendrá, en sí mismo, enunciados indemostrables en dos ocasiones, y estos enunciados serán también indemostrables en tres ocasiones, y así sucesivamente.

_{* Otras afirmaciones, como la conjetura de Goldbach, funcionarían de forma similar: Si son falsas, habría un contraejemplo, y podríamos utilizarlo para refutar la conjetura. Esto significa, paradójicamente, que si no existe ninguna prueba o refutación de la misma en un sistema que la modele, entonces es verdadera. Sin embargo, esto no significa que deba ser posible probarla o refutarla: podría ser indemostrable. Sólo que nunca podríamos demostrar que es indemostrable dentro de ese mismo sistema, porque eso equivale a no mostrar ningún contraejemplo. De hecho, si es indemostrable, entonces es indemostrable en dos ocasiones, en tres ocasiones y así sucesivamente, no se podría decir absolutamente nada de ella.}

Answer 3

[Esto no es una respuesta a la pregunta. Se suponía que era una respuesta a un comentario de Milo bajo su respuesta, pero como es demasiado largo y puede ser interesante para otros, lo pongo aquí].

Diferentes nociones de probabilidad

Milo sugirió que tal vez podamos considerar un tipo de "demostrable" diferente al habitual, con la esperanza de que pueda haber uno que satisfaga todas las propiedades que a él le gustaría tener, es decir (A) a (D) en su post. Comenté que creo que no puede haber tal noción, pero aquí hay un análisis del tipo sugerido en el que "no demostrable" incluye alguna noción de consistencia. Usaré libremente lo que he definido y probado en mi otra respuesta.

Reservemos "demostrable" para la noción estándar. Trabajaremos en una teoría fija $T$ que es lo suficientemente fuerte como para interpretar la aritmética. Dejemos que " $! P$ " denotar " $□ P \lor □ \neg P$ " ( $P$ es internamente demostrable o refutable), y " $? P$ " denotar " $\neg □ \bot → \neg □ P \land \neg □ \neg P$ "(si hay coherencia interna, entonces $P$ es internamente independiente), lo que equivale a " $□ P \lor □ \neg P → □ \bot$ ". Entonces estos son realmente útiles. Por ejemplo $PA \vdash{} ? R$ donde $R$ es el Sentencia Rosser (sobre $PA$ ), formalizando todo el truco de Rosser en la propia PA. También creo que $ZF \vdash{} ? AC$ (basado en https://math.stackexchange.com/a/1596529 ), lo que sería un ejemplo muy poco trivial. Además, siempre tenemos $! P \lor{} ? P$ .

Ahora veamos lo que (A) a (D) sería, debería o no puede ser. Resulta que sólo (A) y (B) tienen algún tipo de interpretación verdadera, pero incluso así no son precisamente muy útiles.

(A) debe ser " $! P →{} ! ! P$ ", lo cual es cierto porque $□ P → □ □ P$ y $□ \neg P → □ □ \neg P$ por (D3), y $□ □ P →{} □ ! P$ y $□ □ \neg P →{} □ ! P$ por (D1,D2).

(B) debe ser " $! P ↔{} ! \neg P$ ", lo cual es obviamente cierto.

(C) sería " $! P \land{} ! ( P → Q ) →{} ! Q$ ", que no es válido cuando $(P,Q) = (\bot,\neg □ \bot)$ ya que la AP demostraría $□ \neg P$ y $□ ( P → Q )$ pero no $! Q$ . (C) debería haber sido (D2).

(D) dice " $□ P → P$ ", que es aún más inválido que " $□ □ P → □ P$ ". Incluso si lo cambiamos por (D*) " $\neg □ \bot \land □ P → P$ ", sigue siendo inválida. Para ver por qué, (D*) da $\neg □ \bot \land □ □ \bot → □ \bot$ y por lo tanto $□ □ \bot → □ \bot$ por lo que por (L*) obtenemos $□\bot$ Lo cual es lo más falso que se puede hacer.

Algunas afirmaciones correctas

Aunque los argumentos de Milo son erróneos, hay una serie de afirmaciones relacionadas que, de hecho, son correctas para cualquier sentencia $P$ en $T$ :

(1) Si $T$ es consistente, entonces $T \nvdash \neg □ P$ .

Igual que (U*).

(2) Si $T$ es aritméticamente sólido o ω-consistente, entonces $T \nvdash □ \neg □ P$ .

Prueba : Si $T \vdash □ \neg □ P$ entonces $T \vdash □ \bot$ por (U), y como $T$ es aritméticamente sólido o ω-consistente podemos extraer una prueba de $\bot$ en $T$ , lo cual es imposible. Por lo tanto $T \nvdash □ \neg □ P$ .

(3) $T \vdash \neg □ \bot → \neg □ \neg □ P$ .

Igual que (U).

Independencia interna

¿Se puede decir algo más sobre la independencia interna, que hemos denotado como " $?$ ", de forma similar a lo que ocurre con " $□$ "? No lo sé; no parece haber ningún hecho simple pero no trivial que lo implique, y tampoco espero que lo haya.

Answer 4

La "probabilidad" es siempre relativa a algún sistema axiomático $T$ y la respuesta a tu pregunta puede ser trivial o muy complicada dependiendo del sistema que consideres para la prueba de la improbabilidad. Veamos cómo.

En lo que sigue estoy asumiendo que (1) usted quiere considerar una declaración $A$ en alguna poderosa teoría $T$ que puede formalizar la mayor parte de las matemáticas como $ZFC$ y (2) quiere considerar la demostrabilidad o no demostrabilidad de $A$ en la teoría $T$ (3) quiere considerar la demostrabilidad o no demostrabilidad de " $A$ es incomprobable en $T$ "en la metateoría que es $T$ o posiblemente extensiones razonables de $T$ .

1. No es tan evidente cuáles son las afirmaciones que realmente expresan que " $A$ es demostrable en $T$ " pero hay un enunciado que sí lo expresa y que quizás quieras considerar: el enunciado aritmético construido por Numeración de Gödel y la codificación del sistema $T$ . Llamémoslo $P_T(A)$ .
2. Gödel demostró que si $A$ es incomprobable en el sistema $T$ (y por lo tanto $T$ es consistente) entonces $\neg P_T(A)$ nunca puede probarse en $T$ (Segundo teorema de incompletitud). Así que no hay afirmaciones $A$ tal que $A$ es incomprobable $T$ y su incomprobabilidad expresada con la fórmula de Godel $\neg P_T(A)$ se puede demostrar en $T$ sí mismo.
3. Dada una declaración $A$ aunque $\neg P_T(A)$ nunca es demostrable para un $T$ (como se ha dicho anteriormente) todavía es posible que $\neg P_T(A)$ se puede demostrar en un sistema más fuerte, por ejemplo en el sistema $T'=T+\text{Con}(T)$ (donde $\text{Con}(T)$ es la fórmula de Godel que expresa la consistencia de $T$ como un enunciado aritmético) o tal vez $T''=T+\text{Con}(T)+\text{Con}(T+\text{Con}(T))$ u otras extensiones razonables y coherentes de $T$ , y no habría manera de decidir en general cuál de estas extensiones (si es que hay alguna) podría eventualmente probarlo.