Il primo teorema di Godel afferma che se un sistema formale, F, è corretto e coerente, allora è incompleto; il secondo, invece, stabilisce che un sistema di questo tipo, che è sufficientemente potente, non può dir di sé stesso d'essere corretto. Un sistema si dice corretto se in esso son dimostrabili solo verità (non si può dimostrare che 2+2=5, uguaglianza chiaramente falsa; tutt'al più la si può refutare!); coerente se non s'incappa in delle contraddizioni; sufficientemente potente se è autoreferenziale; completo se è consistente, cioè se in esso non si ravvisano frasi né dimostrabili né refutabili (in altri termini, indecidibili).

Dimostrazione del primo teorema

Se si considera la frase autoreferenziale che di sé stessa dice "io non sono dimostrabile all'interno del sistema formale F-corretto", allora, per definizione di sistema corretto, la frase in questione è dimostrabile: è vero che non è dimostrabile, dato che essa afferma proprio di non esserlo; di conseguenza, il suo contrario è falso: se, infatti, fosse vero, allora sarebbe refutabile. Tirando le somme, ci si trova innanzi ad una frase indecidibile: non è  né dimostrabile, né refutabile all'interno del sistema esaminato.

Dimostrazione del secondo teorema

Assumendo che F-corretto possa dire di sé stesso d'essere appunto corretto, allora dovrebbe poterlo arguire sfruttando le proposizioni, gli assiomi, le formule in esso definite; tuttavia, dato che contiene al suo interno un assunto indecidibile - quello autoreferenziale -, non può esser sicuro della propria correttezza: occorre che sia un altro sistema a stabilirne l'eventuale correttezza. Ö

Esempio

Se s'assume d'essere in un sistema in cui valgono gli assiomi validi sia per i numeri naturali che per quelli razionali, questi non può dire di sé stesso d'esser corretto: la formula sqrt(2d^2)= r, ove "d" è naturale, non ha che soluzioni irrazionali. Il sistema in esame, per come è stato definito, non ha gli strumenti necessari per poter esprimersi in merito ad essa; per cui, ai suoi "occhi", è indecidibile. La conclusione è che ci si trova in un sistema incompleto dove la formula sopra menzionata è autoreferenziale proprio perché indecidibile.