El teorema de Gödel dice que, para cualquier coherente teoría de la $T$ lo suficientemente fuerte como para expresar algunas elementales de cálculo, habrá una verdadera, pero no demostrable declaración "esta oración no es demostrable" . Básicamente, la idea es que si $T$ demuestra que tenemos una contradicción, sino $T$ es consistente, por lo que no demostrarlo y, en consecuencia, la afirmación es verdadera.
Gödel descubrió que la declaración "esta oración no es demostrable" puede ser expresado aritméticamente a través de una técnica de codificación que ahora conocemos como la numeración de Gödel. Aquí está un ejemplo sencillo. Tomar el alfabeto $PROP_{pq}=\{p,q,\neg,\rightarrow,(,)\}$ y llamar a una palabra cualquier concatenación de los signos. Por ejemplo, '$(\neg q)$', '$(p\rightarrow q)$' o incluso '$q))\rightarrow$'. Una palabra es una secuencia $x_1,...,x_n$ donde cada $x_n$ es '$p$','$q$','$\neg$','$\rightarrow$','$($' o '$)$'. A continuación, podemos enumerar las palabras de $PROP_{pq}$
$$2^{g_1}\cdot 3^{g_2} \cdot ... \cdot p_n^{g_n}$$
donde $p_i$ $i$'th primer número y $g_j$ se define como
$$g=\cases{1, when &$j=p$\cr 2, when&$j=q$\cr 3, when&$j=\neg$\cr 4, when&$j=\rightarrow$\cr 5, when&$j=($\cr 6, when&$j=)$\cr}$$
Luego, en el primer ejemplo anterior, $(\neg q)=2^5 \cdot 3^3 \cdot 5^2 \cdot 7^6=2541218400$. (De hecho, se puede ver que este tipo de codificación son únicos por el teorema fundamental de la aritmética.)
Se supone que es esto para explicar por qué una teoría debe ser capaz de expresar los números naturales con el fin de Gödel del teorema se aplica a él. Pero, ¿por qué no es suficiente? Si lo fuera, otras teorías como la aritmética de Presburger, sería incompleta así. El segundo punto es así que una teoría de la $T$ debe ser lo suficientemente fuerte como para representar funciones recursivas, que, muy brevemente, permite a $T$ a representar su propia provability y expresar la auto-referencia necesaria en "esta oración no es demostrable (en T)".
