Hola,
Una puntualización que suele ser fuente de muchos malentendidos:
Una vez establecida la diferencia entre el concepto de enunciado demostrable y el de enunciado verdadero, hay que usar también el llamado Teorema de Corrección, que dice simplemente que si en un sistema axiomático los axiomas son verdaderos entonces todos los teoremas (enunciados demostrables en ese sistema) serán también verdaderos.
Es interesante mencionar este teorema trival porque Gödel probó, justamente, que la inversa no se verifica (existen enunciados verdaderos no demostrables)
El teorema de corrección dice lo siguiente (sólo con sentencias para evitar complicaciones innecesarias): si \( \Gamma \vdash \varphi \) entonces \( \Gamma \models \varphi \). Es decir, si existe una demostración de \( \varphi \) con premisas en \( \Gamma \), entonces todo modelo de \( \Gamma \) es también modelo de \( \varphi \), esto es, para todo estructura M, si todas las sentencias de \( \Gamma \) son verdaderas en M, entonces \( \varphi \) también es verdadera en M. Hay que notar que esto es un teorema (trivial) de lógica de primer orden, y no hace ninguna referencia a la aritmética ni nada parecido, sirve para cualquier conjunto de sentencias de primer orden que se te ocurra.
Con esta forma, la inversa SÍ se verifica (también lo probó Gödel, en su tesis doctoral, un año antes de sus teoremas de incompletitud), y este es uno de los primeros resultados profundos de la lógica de primer orden: el teorema de completitud. Este teorema dice que si \( \Gamma \models \varphi \) entonces \( \Gamma \vdash \varphi \), es decir, si para toda estructura M donde todas las sentencias de \( \Gamma \) son verdaderas, \( \varphi \) también lo es, entonces existe una demostración de \( \varphi \) con premisas en \( \Gamma \).
Teniendo esto en cuenta, el hecho de que no exista una teoría completa y recursiva para la aritmética implica que cualquier axiomatización recursiva admite otras interpretaciones además de la natural, \( \mathbb{N} \), donde la sentencia de Gödel es falsa. Por ejemplo, esto quiere decir que hay estructuras donde todos los axiomas de Peano son verdaderos, pero la sentencia de Gödel es falsa (este es el punto de partida de la teoría de los modelos no estándar de la aritmética de Peano).
Por último, en los teoremas de incompletitud de Gödel es importante fijarse en la palabra recursiva, que es esencial y es lo primero que se suele olvidar la gente a la hora de enunciarlo. Existe una axiomatización completa de la aritmética: simplemente tomando como axiomas todas las sentencias de primer orden que son verdaderas en el modelo estándar \( \mathbb{N} \), lo que se conoce como la teoría de \( \mathbb{N} \), \( Th(\mathbb{N}) \). Por supuesto esta axiomatización no es recursiva, por lo que no incumple el teorema de incompletitud.
Saludos
En otro hilo surgió exactamente este tema, porque la formulación que hace Óscar (que es por supuesto correcta, y acorde con el main stream del pensamiento matemático moderno) es fuertemente contraintuitiva, y shockea bastante a las mentalidades afines al constructivismo (y por qué no, tal vez nostálgicas del intuicionismo).
La forma tradicional, que no ha dejado de ser correcta, es enunciar el teorema de completitud de Gödel de la siguiente manera:
Toda fórmula lógicamente verdadera es demostrable en el cálculo puro de predicados, y toda fórmula demostrable del cálculo puro de predicados es lógicamente verdadera. Como corolario, toda fórmula que es consecuencia lógica, en un modelo M de la teoría T, de un conjunto de fórmulas Gamma, es demostrable en el lenguaje de la teoría T a partir de Gamma:
\( M, \Gamma\vDash\varphi \) implica \( L,\Gamma\vdash\varphi \)
(Hoy en día se demuestra esto primeramente, y se saca la formulación original de Gödel como corolario para el caso en que Gamma es vacío.)
En esta formulación (si se quiere, histórica), la sentencia indecidible de Gödel (llamémosla SIG) es verdadera en el modelo estándar, pero no es consecuencia lógica de los axiomas de Peano (llamémoslos Ax(PA)):
\( M \vDash SIG \) pero \( M, Ax(PA)\not\vDash SIG \)
Extensionalmente esto es posible, porque las sentencias de un determinado conjunto pueden ser verdaderas en un modelo, pero ser independientes, es decir, no compartir ninguna relación.
Y por lo tanto
\( L, Ax(PA)\not\vdash SIG \)
En modo alguno intento desautorizar o enmendar lo que planteó Óscar, sólo dar una formulación más tradicional, y a mi juicio, más cercana a la intuición.

.
Saludos!