¿Por qué el teorema de incompletitud de Gödel no se aplica a afirmaciones falsas?

Question

He leído y escuchado en conferencias que

Una forma de demostrar que la hipótesis de Riemann es verdadera es demostrar que su negación no es demostrable.

El argumento (de manera informal) generalmente va así

Si una afirmación es falsa, entonces debe existir un contraejemplo que muestre su falsedad.

Por lo tanto, para demostrar que una afirmación es falsa, se debe tener una prueba constructiva.

Pregunta: ¿Por qué el teorema de incompletitud de Gödel no se aplica a las afirmaciones falsas? Es decir, ¿cómo sabemos que todas las afirmaciones falsas son demostrablemente incorrectas?

Answer 1

Es decir, ¿cómo sabemos que todas las declaraciones falsas son demostrablemente falsas?

Esto es simplemente incorrecto. Hay declaraciones tanto verdaderas como falsas que no pueden ser probadas. Lo cierto es que cualquier sistema de fundamentos lo suficientemente bueno (es decir, uno que tenga un programa verificador de pruebas y pueda razonar sobre ejecuciones finitas de programas) es $Σ_1$-completo, lo que significa que prueba cada oración verdadera de $Σ_1$. Aquí, una $Σ_1$-oración es una oración aritmética (es decir, cuantifica solo sobre $\mathbb{N}$) que es equivalente a $∃k∈\mathbb{N}\ ( Q(k) )$ para alguna propiedad aritmética $Q$ que usa solo cuantificadores acotados. Por ejemplo, "Existe un número par que no es la suma de dos números primos." se puede expresar como una $Σ_1$-oración. El "$Σ_1$" significa "$1$ existencial no acotado". De manera similar, una $Π_1$-oración es una oración aritmética equivalente a una con solo $1$ cuantificador universal no acotado en forma normal de Skolem.

En general, si tienes una $Π_1$-oración $C ≡ ∀k∈\mathbb{N}\ ( Q(k) )$, entonces $¬C$ es una $Σ_1$-oración. Por lo tanto, si $C$ es falso, $¬C$ es verdadero y, por lo tanto, demostrable en cualquier sistema de fundamentos lo suficientemente bueno por $Σ_1$-completitud. ¡Esto no se aplica a todas las oraciones falsas!

Resulta que de manera no trivial RH (Hipótesis de Riemann) es equivalente a una $Π_1$-oración, y por lo tanto, por lo anterior sabemos que si es falsa, entonces incluso PA (Aritmética de Peano) puede refutarla. Además, debo agregar que ningún experto cree que sería más fácil probar la imposibilidad de probar RH sobre PA que desmentir directamente RH, incluso si es falso en primer lugar.

El teorema de incompletitud de Gödel no tiene absolutamente nada que ver con la $Σ_1$-completitud. De hecho, el teorema de incompletitud generalizado muestra que cualquier sistema de fundamentos lo suficientemente bueno (independientemente de la lógica subyacente que use) necesariamente es o $Π_1$ o prueba $0=1$. Es decir, si es aritméticamente consistente (es decir, no prueba $0=1$) entonces tampoco prueba alguna $Π_1$-oración verdadera. Además, podemos encontrar dicha oración uniforme y explícitamente (como se describe en el enlace mencionado).

Answer 2

Este argumento no muestra que todos los enunciados falsos sean demostrablemente así. (Eso es imposible por razones triviales: si $P$ es un enunciado verdadero que no es demostrable, entonces $\lnot P$ es un enunciado falso que no es demostrable). El argumento muestra que la hipótesis de Riemann, si es falsa, es demostrablemente así, porque habría un número específico $s$ (en la banda crítica pero no en la línea crítica) en el cual $\zeta(s)=0$, y por lo tanto existiría una prueba (demostrar que ese número específico es un cero de $\zeta$).

Answer 3

Porque si tuvieras la suerte de adivinar el contraejemplo, simplemente podrías verificarlo. Ten en cuenta que esto solo funciona para problemas donde es fácil verificar si un valor dado es de hecho un contraejemplo. Para tomar un ejemplo no matemático, no tienes esperanza de demostrar que has encontrado un contraejemplo para "todas las personas son mortales" porque tendrías que verificar que algún individuo es inmortal, lo que significa que tendrías que verificar que nada puede matarlos, lo cual no es posible.