Indecibilità del Tao

Teorema VI: Ad ogni classe k di formule che sia ω-coerente e ricorsiva corrispondono  segni-di-classe ricorsivi r tali che nè vGen(r) nè Neg(vGen(r)) appartengano a Flg(k), dove v è la variabile libera di r.

ovvero:

Tutte le assiomatizzazioni coerenti dell'aritmetica contengono proposizioni indecidibili.

In uno dei più importanti lavori di logica della storia Kurt Gödel nel 1931 dimostrò due teoremi limitativi basati sui Principia Mathematica, ma in realtà validi (...and related systems) per ogni sistema formale sufficientemente potente.

Il primo teorema di incompletezza afferma:

In ogni teoria matematica T sufficientemente espressiva da contenere l'aritmetica, esiste una formula φ tale che, se T è coerente, allora né φ né la sua negazione Neg(φ) sono dimostrabili in T.

con qualche semplificazione:

In ogni formalizzazione coerente della matematica che sia sufficientemente potente da poter assiomatizzare la teoria elementare dei numeri naturali — vale a dire, sufficientemente potente da definire la struttura dei numeri naturali dotati delle operazioni di somma e prodotto — è possibile costruire una proposizione sintatticamente corretta che non può essere né dimostrata né confutata all'interno dello stesso sistema.

Il secondo teorema di incompletezza di Gödel, riportato all'inizio, che si dimostra formalizzando una parte della dimostrazione del primo teorema all'interno del sistema stesso, afferma che:

Sia T una teoria matematica sufficientemente espressiva da contenere l'aritmetica: se T è coerente, non è possibile provare la coerenza di T all'interno di T.

con qualche semplificazione:

Nessun sistema coerente può essere utilizzato per dimostrare la sua stessa coerenza.