Logica matematica/Incompletezza/Teoremi di incompletezza di Gödel

In Logica matematica, i teoremi di incompletezza di Gödel sono due famosi teoremi dimostrati da Kurt Gödel nel 1931. Essi fanno parte dei teoremi limitativi, che precisano cioè le proprietà che i sistemi formali non possono avere.

Definizioni preliminari

Gödelizzazione

Sia ora $g:(𝒜\cup ℱ\cup \mathrm{S}\mathrm{E}\mathrm{Q})\mapsto \mathbb{N}$ una funzione ricorsiva e iniettiva, detta numero di Gödel (in onore al grande logico). La funzione non fa altro che assegnare univocamente ad ogni stringa di $ℒ\mathcal{=}\mathcal{⟨}𝒜,ℱ\mathcal{⟩}$, e ad ogni sua sequenza di stringhe (l'insieme $\text{SEQ}$), uno ed un solo numero naturale, detto appunto numero di Gödel o gödeliano. Essendo $g$ una funzione iniettiva, essa è invertibile, dunque esiste $g^{-1}:\mathbb{N}\mapsto (𝒜\cup ℱ\cup \mathrm{S}\mathrm{E}\mathrm{Q})$. Supponiamo che anche $g^{-1}$ sia ricorsiva.

A partire da questa funzione, possiamo ora definire una relazione ($Di{m}_S(m,n)$) e una funzione sui numeri naturali ($sost(x,y,z)$), a loro volta ricorsive:

$Di{m}_S$ e $sost$ sono ricorsive, essendo definite a partire da funzioni o insiemi ricorsivi, quali $g$, $g^{-1}$, $\text{DIM}$ e $ℱ$, e non contenendo quantificatori nelle loro definizioni.

ω-coerenza

Lemma di coerenza

Se $S$ è ω-coerente, allora è coerente.

Dimostrazione

Se $S$ fosse incoerente, allora, per definizione, dimostrerebbe qualsiasi formula, pertanto varrebbe, per ogni formula $\alpha [x]\in ℱ$, ${⊢}_S\mathrm{\exists }x\alpha [x]$ e, per ogni $c\in D$, ${⊢}_S\mathrm{\neg }\alpha [\bar{c}/x]$. Quindi, se $S$ è incoerente, allora è anche ω-incoerente, dunque, per contrapposizione, la tesi è dimostrata.

Primo Teorema di incompletezza

Sia $S$ un sistema formale in grado di rappresentare le funzioni ricorsive, allora esiste una formula $\gamma$ tale per cui:

1. se $S$ è coerente, allora ${⊬}_S\gamma$;
2. se $S$ è ω-coerente, allora ${⊬}_S\mathrm{\neg }\gamma$.

Dunque, se si verificano tali condizioni, $S$ è sintatticamente incompleto.

Dimostrazione

Essendo $S$ in grado di rappresentare funzioni ricorsive, esso può esprimere la relazione $Di{m}_S$ e le funzioni $sost$ e $g$ all'interno del suo linguaggio $ℒ$, che conterrà i simboli di predicato e di funzione ${\text{Dim}}_S$, $\text{sost}$ e $\text{g}$.

Consideriamo la formula $\gamma (y)$ di $S$, contenente libera la variabile $y$:

$\gamma (y)\equiv \mathrm{\neg }\mathrm{\exists }x{\text{Dim}}_S(x,\text{sost}(y,\text{g}{(}^{\prime }{y}^{\prime }),y))$

$\gamma (y)$ afferma che non esiste una dimostrazione in $S$ per la formula ottenuta dalla formula di gödeliano $y$, sostituendo (all'interno di essa) le occorrenze libere della variabile il cui gödeliano è $g{(}^{\prime }{y}^{\prime })$ (cioè $y$) con il gödeliano della formula stessa, cioè $y$. In breve, essa afferma che la formula ottenuta da tale sostituzione non è dimostrabile.

Supponiamo ora che $q$ sia il gödeliano di $\gamma (y)$, cioè: $q=g{(}^{\prime }\gamma (y{)}^{\prime })$.

Eseguiamo la seguente sostituzione su $\gamma (y)$: sostituiamo la variabile $y$ con il numerale di $q$. Otteniamo così la formula chiusa $\gamma$:

$\gamma \equiv \mathrm{\neg }\mathrm{\exists }x{\text{Dim}}_S(x,\text{sost}(\bar{q},\text{g}{(}^{\prime }{y}^{\prime }),\bar{q}))$

$\gamma$ afferma che non esiste una dimostrazione in $S$ per la formula ottenuta dalla formula di gödeliano $q$, sostituendo (all'interno di essa) le occorrenze libere della variabile $y$ con il gödeliano della formula stessa, cioè $q$. In pratica, $\gamma$ afferma che la formula che si ottiene tramite tale sostituzione non è dimostrabile, ma tale formula è esattamente $\gamma$, dato che $\gamma \equiv \gamma (y)[\bar{q}/y]$, quindi abbiamo che $g{(}^{\prime }{\gamma }^{\prime })=sost(q,g{(}^{\prime }{y}^{\prime }),q)$. Dunque, $\gamma$ afferma di non essere un teorema, cioè, è l'aritmetizzazione dell'enunciato metamatematico che afferma l'indimostrabilità di $\gamma$.

1. Supponiamo che valga ${⊢}_S\gamma$, allora esiste un $x$ tale per cui esso è il gödeliano di una dimostrazione di $\gamma$. Essendo $Di{m}_S$ rappresentabile in $S$, vale ${⊢}_S\mathrm{\exists }x{\text{Dim}}_S(x,\text{g}{(}^{\prime }{\gamma }^{\prime }))$. Ma, essendo che $g{(}^{\prime }{\gamma }^{\prime })=sost(q,g{(}^{\prime }{y}^{\prime }),q)$, abbiamo che ${⊢}_S\mathrm{\exists }x{\text{Dim}}_S(x,\text{sost}(\bar{q},\text{g}{(}^{\prime }{y}^{\prime }),\bar{q}))$, dunque ${⊢}_S\mathrm{\neg }\gamma$. Perciò, se $\gamma$ è dimostrabile, allora $S$ è incoerente.
2. Supponiamo che $S$ sia ω-coerente, ma che, per assurdo, valga ${⊢}_S\mathrm{\neg }\gamma$, allora abbiamo che ${⊢}_S\mathrm{\exists }x{\text{Dim}}_S(x,\text{g}{(}^{\prime }{\gamma }^{\prime }))$. Essendo $S$ ω-coerente, per il lemma di coerenza esso è anche coerente, dunque, per il punto 1, vale ${⊬}_S\gamma$, cioè ${⊬}_S\mathrm{\neg }\mathrm{\exists }x{\text{Dim}}_S(x,\text{g}{(}^{\prime }{\gamma }^{\prime }))$. Quindi, essendo $Di{m}_S$ rappresentabile in $S$, abbiamo che, per ogni $n$, ${⊢}_S\mathrm{\neg }{\text{Dim}}_S(\bar{n},\text{g}{(}^{\prime }{\gamma }^{\prime }))$. Dunque, valendo sia ${⊢}_S\mathrm{\exists }x{\text{Dim}}_S(x,\text{g}{(}^{\prime }{\gamma }^{\prime }))$ che ${⊢}_S\mathrm{\neg }{\text{Dim}}_S(\bar{n},\text{g}{(}^{\prime }{\gamma }^{\prime }))$ per ogni $n$, segue che $S$ è ω-incoerente, contraddicendo l'ipotesi iniziale.

Perciò, se $S$ è ω-coerente, allora $\gamma$ è indecidibile all'interno di $S$ stesso.

Secondo Teorema di incompletezza

Predicato di dimostrabilità

Supponiamo che

${\text{Teor}}_S$

sia il predicato che descrive la proprietà "essere un teorema", in relazione ad una formula (e dunque un gödeliano). Detto formalmente,

${\text{Teor}}_S(n)\equiv \mathrm{\exists }m{\text{Dim}}_S(m,n)$

ovvero, il predicato è vero sse esiste un

$m$

tale per cui esso è il gödeliano che rappresenta una dimostrazione della formula rappresentata da

$n$

.

Proprietà

Per ogni formula $\alpha$, sia $\bar{\alpha }=\text{g}(\alpha )$.

Il predicato unario ${\text{Teor}}_S$, per essere considerato valido, deve godere delle seguenti proprietà.

Date due formule

$\alpha ,\beta$

:

T1. Se

${⊢}_S\alpha$

, allora

${⊢}_S{\text{Teor}}_S(\bar{\alpha })$

;

T2.

${⊢}_S{\text{Teor}}_S(\bar{\alpha })\to {\text{Teor}}_S(\overline{{\text{Teor}}_S(\stackrel{‾}{\alpha })})$

;

T3.

${⊢}_S{\text{Teor}}_S(\bar{\alpha })\wedge {\text{Teor}}_S(\overline{\alpha \to \beta })\to {\text{Teor}}_S(\bar{\beta })$

;

T4. Se

${⊢}_S{\text{Teor}}_S(\bar{\alpha })$

, allora

${⊢}_S\alpha$

.