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

Definizione

• Sia $S=\langle {\mathcal {L}},Ax,{\mathcal {R}}\rangle$ un sistema formale costruito su un linguaggio del primo ordine ${\mathcal {L=\langle A,F\rangle }}$, dove $Ax$ è l'insieme degli assiomi di $S$ e ${\mathcal {R}}$ è l'insieme delle sue regole d'inferenza; ${\mathcal {A}}$ è l'alfabeto di ${\mathcal {L}}$ e ${\mathcal {F}}$ l'insieme delle sue formule ben formate.
• Sia $c\in D$, il simbolo che lo denota in ${\mathcal {L}}$ è rappresentato da ${\overline {c}}\in {\mathcal {A}}$, dove ${\mathcal {A}}$ è l'alfabeto di ${\mathcal {L}}$.
• Sia $R\subseteq D^{k}$ una relazione $k$-aria. In teoria degli insiemi, essa è definita come l'insieme delle liste numerate $\langle c_{1},...,c_{k}\rangle$ di lunghezza $k$ ($k$-uple), tali che esse siano in grado di soddisfare una determinata proprietà $R(c_{1},...,c_{k})$. $D$ è il dominio degli elementi $c_{1},...,c_{k}$, cioè $c_{i}\in D$, per ogni $i=1,...,k$.
• Sia $f:D^{k}\mapsto D$ una funzione $k$-aria.

Rappresentabilità

Relazione rappresentabile

Definizione

$R$ è rappresentabile in $S$ sse esiste una formula $\alpha [x_{1},...,x_{k}]\in {\mathcal {F}}$, contenente esattamente $k$ variabili libere $x_{1},...,x_{k}$, tale che, per ogni $k$-upla di elementi $\langle c_{1},...,c_{k}\rangle$:

1. se $\langle c_{1},...,c_{k}\rangle \in R$, allora $\vdash _{S}\alpha [{\overline {c_{1}}}/x_{1},...,{\overline {c_{k}}}/x_{k}]$;
2. se $\langle c_{1},...,c_{k}\rangle \not \in R$, allora $\vdash _{S}\neg \alpha [{\overline {c_{1}}}/x_{1},...,{\overline {c_{k}}}/x_{k}]$.

Dove $\alpha [{\overline {c_{1}}}/x_{1},...,{\overline {c_{k}}}/x_{k}]$ indica la sostituzione di ogni variabile $x_{i}$ con il simbolo ${\overline {c_{i}}}$, per ogni $i=1,...,k$. Si dice allora che la formula rappresenta la relazione $R$.

Relazione semi-rappresentabile

Definizione

$R$ è semi-rappresentabile (o debolmente rappresentabile) in $S$ sse esiste una formula $\alpha [x_{1},...,x_{k}]\in {\mathcal {F}}$, contenente esattamente $k$ variabili libere $x_{1},...,x_{k}$, tale che, per ogni $k$-upla di elementi $\langle c_{1},...,c_{k}\rangle$, $\langle c_{1},...,c_{k}\rangle \in R$ sse $\vdash _{S}\alpha [{\overline {c_{1}}}/x_{1},...,{\overline {c_{k}}}/x_{k}]$.

Funzione rappresentabile

Definizione

$f$ è rappresentabile in $S$ sse esiste una formula $\alpha [x_{1},...,x_{k},x_{k+1}]\in {\mathcal {F}}$, contenente esattamente $k+1$ variabili libere $x_{1},...,x_{k},x_{k+1}$, tale che, per ogni $(k+1)$-upla di elementi $\langle c_{1},...,c_{k},c_{k+1}\rangle$, se $f(c_{1},...,c_{k})=c_{k+1}$, allora:

1. $\vdash _{S}\alpha [{\overline {c_{1}}}/x_{1},...,{\overline {c_{k}}}/x_{k},{\overline {c_{k+1}}}/x_{k+1}]$;
2. $\vdash _{S}\forall x_{1},...,x_{k}\exists x_{k+1}\forall y(\alpha [x_{1},...,x_{k},y]\leftrightarrow y=x_{k+1})$.

Ricorsività

Definizione

Una funzione $f$ è detta ricorsiva sse essa è esprimibile mediante la teoria della ricorsività. Una relazione (o un insieme) $R$ è ricorsiva sse la sua funzione caratteristica è ricorsiva.

• L'insieme ${\mathcal {F}}$ delle formule ben formate di un sistema formale $S$, essendo definito induttivamente, è ricorsivo.
• Sia ${\text{SEQ}}=\bigcup _{k\in \mathbb {N} }{\mathcal {F}}^{k}$ l'unione di tutti gli insiemi di tutte le sequenze ($k$-uple) di lunghezza $k$ contenenti formule, per ogni $k\in \mathbb {N}$. L'insieme ${\text{DIM}}\subseteq {\text{SEQ}}$ delle dimostrazioni di $S$ può essere definito induttivamente.

Sia $Ax$ l'insieme degli assiomi di $S$ e ${\mathcal {R}}$ l'insieme delle sue regole d'inferenza. L'insieme ${\text{DIM}}$ è così definito:

1. $\langle \alpha \rangle \in {\text{DIM}}$ sse $\alpha \in Ax$;
2. $\langle \alpha _{1},...,\alpha _{n},\alpha _{n+1}\rangle \in {\text{DIM}}$ sse $(d=\langle \alpha _{1},...,\alpha _{n}\rangle )\in {\text{DIM}}$ e $\alpha _{n+1}\in Ax$, oppure $\alpha _{n+1}$ è conseguenza diretta di qualche $j$-upla $\langle \alpha _{1},...,\alpha _{j}\rangle$ (i cui elementi sono in $d$) per qualche $R_{i}\in {\mathcal {R}}$.

Gödelizzazione

Sia ora $g:({\mathcal {A}}\cup {\mathcal {F}}\cup \mathrm {SEQ} )\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 {L=\langle A,F\rangle }}$, 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 ({\mathcal {A}}\cup {\mathcal {F}}\cup \mathrm {SEQ} )$. Supponiamo che anche $g^{-1}$ sia ricorsiva.

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

Definizione

• la relazione $Dim_{S}(m,n)\subseteq \mathbb {N} ^{2}$ è definita come $Dim_{S}(m,n)=\{\langle m,n\rangle |g^{-1}(m)=\langle \alpha _{1},...,\alpha _{k}\rangle ,g^{-1}(m)\in {\text{DIM}},\alpha _{k}=g^{-1}(n)\}$. In sostanza, il predicato $Dim_{S}$ codifica la relazione "$(d=\langle \alpha _{1},...,\alpha _{k}\rangle )\vdash _{S}\alpha$", cioè, vale sse $d$ dimostra $\alpha$, ovvero, sse $d$ è una dimostrazione in $S$ e $\alpha =\alpha _{k}$.
• la funzione $sost:\mathbb {N} ^{3}\mapsto \mathbb {N}$ è definita come $sost(x,y,z)=g(g^{-1}(x)[{\overline {z}}/g^{-1}(y)])$, cioè, la funzione $sost$ restituisce il gödeliano della formula ottenuta sostituendo nella formula di gödeliano $x$ il simbolo (numerale) di $z$ al posto della variabile libera di gödeliano $y$. In sostanza, la funzione $sost$ aritmetizza la sostituzione di un numerale al posto di una variabile libera in una formula.

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

ω-coerenza

Definizione

Un sistema formale $S$ è ω-coerente sse non esiste una formula $\alpha [x]\in {\mathcal {F}}$ tale per cui $\vdash _{S}\exists x\alpha [x]$ e, per ogni $c\in D$, $\vdash _{S}\neg \alpha [{\overline {c}}/x]$.

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 {\mathcal {F}}$, $\vdash _{S}\exists x\alpha [x]$ e, per ogni $c\in D$, $\vdash _{S}\neg \alpha [{\overline {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 $\nvdash _{S}\gamma$;
2. se $S$ è ω-coerente, allora $\nvdash _{S}\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 $Dim_{S}$ e le funzioni $sost$ e $g$ all'interno del suo linguaggio ${\mathcal {L}}$, 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 \neg \exists x{\text{Dim}}_{S}(x,{\text{sost}}(y,{\text{g}}('y'),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('y')$ (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('\gamma (y)')$.

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

$\gamma \equiv \neg \exists x{\text{Dim}}_{S}(x,{\text{sost}}({\overline {q}},{\text{g}}('y'),{\overline {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)[{\overline {q}}/y]$, quindi abbiamo che $g('\gamma ')=sost(q,g('y'),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 $\vdash _{S}\gamma$, allora esiste un $x$ tale per cui esso è il gödeliano di una dimostrazione di $\gamma$. Essendo $Dim_{S}$ rappresentabile in $S$, vale $\vdash _{S}\exists x{\text{Dim}}_{S}(x,{\text{g}}('\gamma '))$. Ma, essendo che $g('\gamma ')=sost(q,g('y'),q)$, abbiamo che $\vdash _{S}\exists x{\text{Dim}}_{S}(x,{\text{sost}}({\overline {q}},{\text{g}}('y'),{\overline {q}}))$, dunque $\vdash _{S}\neg \gamma$. Perciò, se $\gamma$ è dimostrabile, allora $S$ è incoerente.
2. Supponiamo che $S$ sia ω-coerente, ma che, per assurdo, valga $\vdash _{S}\neg \gamma$, allora abbiamo che $\vdash _{S}\exists x{\text{Dim}}_{S}(x,{\text{g}}('\gamma '))$. Essendo $S$ ω-coerente, per il lemma di coerenza esso è anche coerente, dunque, per il punto 1, vale $\nvdash _{S}\gamma$, cioè $\nvdash _{S}\neg \exists x{\text{Dim}}_{S}(x,{\text{g}}('\gamma '))$. Quindi, essendo $Dim_{S}$ rappresentabile in $S$, abbiamo che, per ogni $n$, $\vdash _{S}\neg {\text{Dim}}_{S}({\overline {n}},{\text{g}}('\gamma '))$. Dunque, valendo sia $\vdash _{S}\exists x{\text{Dim}}_{S}(x,{\text{g}}('\gamma '))$ che $\vdash _{S}\neg {\text{Dim}}_{S}({\overline {n}},{\text{g}}('\gamma '))$ 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 \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 ${\overline {\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 $\vdash _{S}\alpha$, allora $\vdash _{S}{\text{Teor}}_{S}({\overline {\alpha }})$;

T2. $\vdash _{S}{\text{Teor}}_{S}({\overline {\alpha }})\to {\text{Teor}}_{S}({\overline {{\text{Teor}}_{S}({\overline {\alpha }})}})$;

T3.$\vdash _{S}{\text{Teor}}_{S}({\overline {\alpha }})\land {\text{Teor}}_{S}({\overline {\alpha \to \beta }})\to {\text{Teor}}_{S}({\overline {\beta }})$;

T4. Se $\vdash _{S}{\text{Teor}}_{S}({\overline {\alpha }})$, allora $\vdash _{S}\alpha$.