Dimostrazione originale del teorema di completezza di Gödel

Kurt Gödel (1925)

La dimostrazione del teorema di completezza di Gödel, fornita da Kurt Gödel nella sua tesi di dottorato del 1929 (e una versione più breve, pubblicata come articolo nel 1930, intitolata "La completezza degli assiomi del calcolo funzionale della logica" in tedesco) ad oggi non è facile da leggere: utilizza concetti e formalismi in disuso e terminologie spesso oscure. La versione fornita di seguito tenta di rappresentare fedelmente tutti i passaggi della dimostrazione e tutte le idee importanti, pur riformulandola nel linguaggio odierno della logica matematica. Questa traccia non deve essere considerata una prova rigorosa del teorema.

Presupposti

Lavoriamo nel calcolo dei predicati del primo ordine. I linguaggi consentono i simboli di costanti, di funzioni e di predicati. Le strutture sono costituite da un dominio (non vuoto) e da una funzione che interpreta i simboli del relativo linguaggio come elementi, funzioni o relazioni su quel dominio.

Utilizziamo la logica classica (invece che la logica intuizionistica, per esempio).

Fissiamo una qualche assiomatizzazione (cioè un sistema di deduzione attuabile da una macchina) del calcolo dei predicati, formato da assiomi logici e regole di inferenza: uno qualunque dei numerosi sistemi equivalenti andrà bene. La dimostrazione originale di Gödel usava il sistema di Hilbert-Ackermann.

Assumiamo, senza dimostrarli, tutti i ben noti risultati di base sul nostro formalismo di cui abbiamo bisogno, come il teorema della forma normale e il teorema di correttezza.

Usiamo il calcolo dei predicati senza uguaglianza (a volte chiamato erroneamente senza identità), cioè non ci sono assiomi speciali che esprimono le proprietà dell'uguaglianza (tra elementi del dominio) come un simbolo di relazione speciale. Dopo aver dimostrato la forma base del teorema, sarà facile estenderla al caso del calcolo dei predicati con uguaglianza.

Enunciato del teorema e dimostrazione

Di seguito enunciamo due forme del teorema e ne mostriamo l'equivalenza. Successivamente, dimostriamo il teorema. Ciò viene realizzato attraverso i seguenti passaggi:

1. Riduciamo il teorema ai soli enunciati (formule senza variabili libere) in forma prenessa, cioè con tutti i quantificatori (∀ e ∃) all'inizio. Inoltre, lo riduciamo a formule il cui primo quantificatore è ∀. Questo è possibile perché, per ogni formula chiusa, ne esiste una equivalente in forma prenessa il cui primo quantificatore è ∀.
2. Riduciamo il teorema ai soli enunciati della forma $\mathrm{\forall }{x}_1\dots \mathrm{\forall }{x}_k\mathrm{\exists }{y}_1\dots \mathrm{\exists }{y}_m\varphi [x_1,\dots ,x_k,y_1,\dots ,y_m]$. Sebbene non possiamo farlo semplicemente riordinando i quantificatori, mostriamo che è ancora sufficiente provare il teorema per enunciati di questa forma.
3. Infine, dimostriamo il teorema per enunciati della suddetta forma.
   • Ciò viene effettuato notando prima che un enunciato come $B=\mathrm{\forall }{x}_1\dots \mathrm{\forall }{x}_k\mathrm{\exists }{y}_1\dots \mathrm{\exists }{y}_m\varphi [x_1,\dots ,x_k,y_1,\dots ,y_m]$ è refutabile (la sua negazione è dimostrabile) oppure soddisfacibile, cioè c'è qualche modello nel quale è vero (potrebbe anche essere sempre vero, cioè una tautologia); questo modello sta semplicemente assegnando valori di verità ai sottoenunciati da cui $B$ è formato. La ragione di ciò è la completezza della logica proposizionale, con i quantificatori esistenziali che non giocano alcun ruolo.
   • Estendiamo questo risultato a enunciati sempre più complessi e lunghi $D_n(n=1,2,\dots )$, costruiti a partire da $B$, in modo che qualcuno di essi è refutabile e quindi lo è anche $\varphi$, oppure sono tutti non refutabili e quindi ognuno è vero in qualche modello.
   • Usiamo infine i modelli in cui valgono i $D_n$ (nel caso siano tutti non refutabili) per costruire un modello in cui vale $\varphi$.

Teorema 1. Ogni enunciato valido (vero in tutte le strutture) è dimostrabile.

Questa è la forma più elementare del teorema di completezza. Lo riformuliamo subito in una forma più comoda per i nostri scopi: quando diciamo "tutte le strutture", è importante specificare che le strutture coinvolte sono interpretazioni classiche (tarskiane) $I=⟨U,F⟩$, dove $U$ è un insieme di oggetti non vuoto (possibilmente infinito), mentre $F$ è una funzione che mappa simboli di costanti, di funzioni e di predicati rispettivamente in elementi di $U$, funzioni e relazioni su $U$ (al contrario, le cosiddette "logiche libere" accettano anche che il dominio sia vuoto; per saperne di più sulle logiche libere, si veda il lavoro di Karel Lambert).

Teorema 2. Ogni formula non soddisfacibile è refutabile.

"$\varphi$ è refutabile" significa per definizione "$\mathrm{\neg }\varphi$ è dimostrabile".

Equivalenza dei due teoremi

Se vale il Teorema 1 e $\varphi$ non è soddisfacibile, allora $\mathrm{\neg }\varphi$ è valida in tutte le strutture e quindi dimostrabile, dunque $\varphi$ è refutabile e vale il Teorema 2. Se invece vale il Teorema 2 e $\varphi$ vale in tutte le strutture, allora $\mathrm{\neg }\varphi$ non è soddisfacibile e quindi refutabile; ma allora $\mathrm{\neg }\mathrm{\neg }\varphi$ è dimostrabile e dunque lo è anche $\varphi$, quindi vale il Teorema 1.

Dimostrazione del teorema 2: primo passo

Iniziamo la dimostrazione del Teorema 2 restringendo sequenzialmente la classe di tutte le formule $\varphi$ per le quali dobbiamo dimostrare che "$\varphi$ è insoddisfacibile solo se è refutabile".

All'inizio dobbiamo dimostrarlo per tutte le possibili formule del linguaggio preso in esame. Tuttavia, supponiamo che per ogni formula $\varphi$ esista qualche formula ${\psi }_{\varphi }$, presa da una classe più ristretta di formule $\mathrm{C}$, tale per cui "${\psi }_{\varphi }$ è insoddisfacibile solo se è refutabile"$⟹$"$\varphi$ è insoddisfacibile solo se è refutabile".

Allora, una volta provata questa affermazione (espressa nella frase precedente), basterà dimostrare che "$\varphi$ è insoddisfacibile solo se è refutabile" solo per le $\varphi$ che stanno nella classe $\mathrm{C}$. Se $\varphi$ e ${\psi }_{\varphi }$ sono sintatticamente equivalenti, ovvero $\varphi \equiv {\psi }_{\varphi }$ (cioè, se la formula $\varphi \leftrightarrow {\psi }_{\varphi }$ è dimostrabile), allora è vero che "${\psi }_{\varphi }$ è insoddisfacibile solo se è refutabile"$⟹$"$\varphi$ è insoddisfacibile solo se è refutabile" (il teorema di correttezza è necessario per provare ciò).

Esistono tecniche standard per riscrivere una formula arbitraria in un'altra che non utilizzi funzioni e simboli costanti, a costo di introdurre quantificatori aggiuntivi; assumeremo quindi che tutte le formule siano prive di tali simboli. L'articolo di Gödel utilizzava dal principio una versione del calcolo dei predicati che non ha funzioni e costanti.

Ora, consideriamo una formula generica $\varphi$ (che non contiene funzioni o costanti) e applichiamo il teorema della forma prenessa per trovare una formula ${\psi }_{\varphi }$ in forma normale tale che $\varphi \equiv {\psi }_{\varphi }$ (forma normale significa che tutti i quantificatori in ${\psi }_{\varphi }$, se ce ne sono, si trovano proprio all'inizio di ${\psi }_{\varphi }$). Ne consegue che ora dobbiamo dimostrare il Teorema 2 solo per le formule $\varphi$ in forma normale.

Adesso, eliminiamo tutte le variabili libere da $\varphi$ quantificandole esistenzialmente: se poniamo che $x_1,\dots ,x_n$ sono libere in $\varphi$, formiamo ${\psi }_{\varphi }=\mathrm{\exists }{x}_1\dots \mathrm{\exists }{x}_n\varphi$. Se ${\psi }_{\varphi }$ è vera in qualche struttura $M$, allora esiste un'assegnazione su $M$ alle variabili $x_1,\dots ,x_n$ che verifica $\varphi$ in $M$, quindi $\varphi$ è soddisfacibile; se invece ${\psi }_{\varphi }$ è insoddisfacibile, allora $\mathrm{\neg }{\psi }_{\varphi }\equiv \mathrm{\forall }{x}_1\dots \mathrm{\forall }{x}_n\mathrm{\neg }\varphi$ è sempre vera e quindi, in ogni struttura $M$, ogni assegnazione su $M$ alle variabili $x_1,\dots ,x_n$ verifica $\mathrm{\neg }\varphi$, quindi $\varphi$ è insoddisfacibile. Possiamo allora restringerci alle sole formule $\varphi$ che sono enunciati, cioè formule senza variabili libere.

Infine vorremmo, per ragioni di convenienza tecnica, che il prefisso di $\varphi$ (ovvero la stringa di quantificatori all'inizio di $\varphi$, che è in forma normale) inizi con un quantificatore universale e finisca con un quantificatore esistenziale. Per ottenere ciò per una generica $\varphi$ (soggetta alle restrizioni che abbiamo già dimostrato), prendiamo due variabili $y$ e $z$ che non occorrono in $\varphi$. Se $\varphi =(P)\mathrm{\Phi }$, dove $(P)$ sta per il prefisso di $\varphi$ e $\mathrm{\Phi }$ per la matrice (la restante parte di $\varphi$ priva di quantificatori), formiamo ${\psi }_{\varphi }=\mathrm{\forall }y(P)\mathrm{\exists }z\mathrm{\Phi }$, che ovviamente è equivalente a $\varphi$, dato che $y$ e $z$ non compaiono in $\mathrm{\Phi }$.

Ridurre il teorema a formule di grado 1

La nostra formula generica $\varphi$ ora è un enunciato, in forma normale, e il suo prefisso inizia con un quantificatore universale e termina con un quantificatore esistenziale. Chiamiamo la classe di tutte queste formule $\mathrm{R}$. Dobbiamo dimostrare che ogni formula in $\mathrm{R}$ è insoddisfacibile solo se è refutabile. Data la nostra formula $\varphi$, raggruppiamo stringhe di quantificatori dello stesso tipo in blocchi:

$\varphi =(\mathrm{\forall }{x}_1\dots \mathrm{\forall }{x}_{k_1})(\mathrm{\exists }{x}_{k_1+1}\dots \mathrm{\exists }{x}_{k_2})\dots (\mathrm{\forall }{x}_{k_{n-2}+1}\dots \mathrm{\forall }{x}_{k_{n-1}})(\mathrm{\exists }{x}_{k_{n-1}+1}\dots \mathrm{\exists }{x}_{k_n})\mathrm{\Phi }$

Definiamo il grado di $\varphi$ come il numero di blocchi di quantificatori universali separati da blocchi di quantificatori esistenziali nel prefisso di $\varphi$, come mostrato sopra. Il seguente lemma, che Gödel ha adattato dalla dimostrazione di Skolem del teorema di Löwenheim-Skolem, ci permette di ridurre nettamente la complessità delle formule $\varphi$ per cui dobbiamo dimostrare il teorema:

Lemma. Sia $k\ge 1$. Se ogni formula in $\mathrm{R}$ di grado $k$ è soddisfacibile o refutabile, allora lo è anche ogni formula in $\mathrm{R}$ di grado $k+1$.

Commento: Si prenda una formula $\varphi$ di grado $k+1$ della forma $\varphi =\mathrm{\forall }x\mathrm{\exists }y\mathrm{\forall }u\mathrm{\exists }v(P)\psi$, dove $(P)\psi$ è il resto di $\varphi$ (quindi è di grado $k-1$). $\varphi$ afferma che per ogni $x$ esiste $y$ tale che... (qualcosa). Sarebbe stato bello avere un predicato $Q$ in modo che per ogni $x$, $Q(x,y)$ fosse vero se e solo se il valore di $y$ è quello richiesto per rendere (qualcosa) vero. Allora avremmo potuto scrivere una formula di grado $k$, equivalente a $\varphi$, vale a dire $\mathrm{\forall }{x}^{\prime }\mathrm{\forall }x\mathrm{\forall }y\mathrm{\forall }u\mathrm{\exists }v\mathrm{\exists }{y}^{\prime }(P)Q(x^{\prime },y^{\prime })\wedge (Q(x,y)\to \psi )$ . Questa formula è infatti equivalente a $\varphi$, perché afferma che per ogni $x$, se c'è un $y$ che soddisfa $Q(x,y)$, allora (qualcosa) vale, e inoltre sappiamo che c'è tale $y$, perché per ogni $x^{\prime }$ c'è un $y^{\prime }$ che soddisfa $Q(x^{\prime },y^{\prime })$. Quindi $\varphi$ segue da questa formula. È facile anche dimostrare che se la formula è falsa, lo è anche $\varphi$. Sfortunatamente, in generale non esiste un tale predicato. Tuttavia, questa idea può essere intesa come base per la seguente dimostrazione del lemma.

Dimostrazione. Sia $\varphi$ una formula di grado $k+1$. Allora, possiamo scriverla come:

$\varphi =(\mathrm{\forall }x)(\mathrm{\exists }y)(\mathrm{\forall }u)(\mathrm{\exists }v)(P)\psi$

dove $(P)$ è il resto del prefisso di $\varphi$ (quindi è di grado $k-1$) e $\psi$ è la matrice priva di quantificatori di $\varphi$. $x,y,u,v$ denotano qui ennuple di variabili invece che singole variabili; per esempio, $(\mathrm{\forall }x)$ in realtà sta per $\mathrm{\forall }{x}_1\mathrm{\forall }{x}_2\dots \mathrm{\forall }{x}_n$, dove $(x_1,\dots ,x_n)$ sono variabili distinte.

Siano ora $x^{\prime }$e $y^{\prime }$ennuple di variabili precedentemente inutilizzate, rispettivamente della stessa lunghezza di $x$ e $y$, e sia $Q$ un simbolo di relazione precedentemente inutilizzato, che accetta un numero di argomenti pari alla somma delle lunghezze di $x$ e $y$; consideriamo la formula

$\mathrm{\Phi }=(\mathrm{\forall }{x}^{\prime })(\mathrm{\exists }{y}^{\prime })Q(x^{\prime },y^{\prime })\wedge (\mathrm{\forall }x)(\mathrm{\forall }y)(Q(x,y)\to (\mathrm{\forall }u)(\mathrm{\exists }v)(P)\psi )$

Chiaramente, $\mathrm{\Phi }⟹\varphi$.

Ora, poiché la stringa di quantificatori $(\mathrm{\forall }u)(\mathrm{\exists }v)(P)$ non contiene variabili di $x$ e $y$, la seguente equivalenza è facilmente dimostrabile con l'aiuto del formalismo che stiamo usando:

$(Q(x,y)\to (\mathrm{\forall }u)(\mathrm{\exists }v)(P)\psi )\equiv (\mathrm{\forall }u)(\mathrm{\exists }v)(P)(Q(x,y)\to \psi )$

E poiché queste due formule sono equivalenti, se sostituiamo la prima con la seconda dentro $\mathrm{\Phi }$, otteniamo la formula ${\mathrm{\Phi }}^{\prime }$ tale che $\mathrm{\Phi }\equiv {\mathrm{\Phi }}^{\prime }$:

${\mathrm{\Phi }}^{\prime }=(\mathrm{\forall }{x}^{\prime })(\mathrm{\exists }{y}^{\prime })Q(x^{\prime },y^{\prime })\wedge (\mathrm{\forall }x)(\mathrm{\forall }y)(\mathrm{\forall }u)(\mathrm{\exists }v)(P)(Q(x,y)\to \psi )$

Ora ${\mathrm{\Phi }}^{\prime }$ ha la forma $(S)\rho \wedge (S^{\prime }){\rho }^{\prime }$, dove $(S)$ e $(S^{\prime })$ sono stringhe di quantificatori, $\rho$ e ${\rho }^{\prime }$ sono prive di quantificatori e, inoltre, nessuna variabile di $(S)$ occorre in ${\rho }^{\prime }$ e nessuna variabile di $(S^{\prime })$ occorre in $\rho$. In tali condizioni, ogni formula della forma $(T)(\rho \wedge {\rho }^{\prime })$, dove $(T)$ è una stringa di quantificatori contenente tutti i quelli in $(S)$ e $(S^{\prime })$ inseriti in qualsiasi ordine, ma mantenendo l'ordine relativo all'interno di $(S)$ e $(S^{\prime })$, sarà equivalente alla formula originale ${\mathrm{\Phi }}^{\prime }$ (questo è un altro risultato fondamentale del calcolo dei predicati su cui ci basiamo). Dunque, formiamo $\mathrm{\Psi }$ come segue:

$\mathrm{\Psi }=(\mathrm{\forall }{x}^{\prime })(\mathrm{\forall }x)(\mathrm{\forall }y)(\mathrm{\forall }u)(\mathrm{\exists }{y}^{\prime })(\mathrm{\exists }v)(P)Q(x^{\prime },y^{\prime })\wedge (Q(x,y)\to \psi )$

e abbiamo ${\mathrm{\Phi }}^{\prime }\equiv \mathrm{\Psi }$.

Ora $\mathrm{\Psi }$ è una formula di grado $k$ e quindi, per ipotesi induttiva, soddisfacibile o refutabile. Se $\mathrm{\Psi }$ è soddisfacibile, allora, considerando $\mathrm{\Psi }\equiv {\mathrm{\Phi }}^{\prime }\equiv \mathrm{\Phi }$ e $\mathrm{\Phi }⟹\varphi$, vediamo che anche $\varphi$ è soddisfacibile. Se $\mathrm{\Psi }$ è refutabile, allora lo è anche $\mathrm{\Phi }$, che è equivalente ad esso; dunque $\mathrm{\neg }\mathrm{\Phi }$ è dimostrabile. Ora possiamo sostituire tutte le occorrenze di $Q$ all'interno della formula dimostrabile $\mathrm{\neg }\mathrm{\Phi }$ da qualche altra formula dipendente dalle stesse variabili, e otterremo comunque una formula dimostrabile. (Questo è ancora un altro risultato fondamentale del calcolo dei predicati. A seconda del particolare formalismo adottato per il calcolo, esso può essere visto come una semplice applicazione della regola di inferenza di "sostituzione funzionale", come nell'articolo di Gödel, oppure può essere dimostrato considerando la dimostrazione formale di $\mathrm{\neg }\mathrm{\Phi }$, sostituendo in essa tutte le occorrenze di $Q$ con qualche altra formula con le stesse variabili libere, e notando che tutti gli assiomi logici nella dimostrazione formale rimangono tali dopo la sostituzione, e tutte le regole di inferenza si applicano ancora allo stesso modo.)

In questo caso particolare, sostituiamo $Q(x^{\prime },y^{\prime })$ in $\mathrm{\neg }\mathrm{\Phi }$ con la formula $(\mathrm{\forall }u)(\mathrm{\exists }v)(P)\psi [x,y/x^{\prime },y^{\prime }]$. Qui $[x,y/x^{\prime },y^{\prime }]$ significa che invece di $\psi$ stiamo scrivendo una formula diversa, in cui $x$ e $y$ sono sostituiti con $x^{\prime }$ e $y^{\prime }$. $Q(x,y)$ è semplicemente sostituito da $(\mathrm{\forall }u)(\mathrm{\exists }v)(P)\psi$.

$\mathrm{\neg }\mathrm{\Phi }$ diventa

$\mathrm{\neg }((\mathrm{\forall }{x}^{\prime })(\mathrm{\exists }{y}^{\prime })(\mathrm{\forall }u)(\mathrm{\exists }v)(P)\psi [x,y/x^{\prime },y^{\prime }]\wedge (\mathrm{\forall }x)(\mathrm{\forall }y)((\mathrm{\forall }u)(\mathrm{\exists }v)(P)\psi \to (\mathrm{\forall }u)(\mathrm{\exists }v)(P)\psi ))$

e questa formula è dimostrabile; poiché la parte dopo il segno $\wedge$ è ovviamente dimostrabile, e la parte sotto negazione e prima del segno $\wedge$ è ovviamente $\varphi$, ma con $x$ e $y$ sono sostituiti da $x^{\prime }$ e $y^{\prime }$, segue che $\mathrm{\neg }\varphi$ è dimostrabile e $\varphi$ è refutabile. Abbiamo dimostrato che $\varphi$ è soddisfacibile o refutabile, e questo conclude la dimostrazione del Lemma.

Si noti che non possiamo utilizzare $(\mathrm{\forall }u)(\mathrm{\exists }v)(P)\psi [x,y/x^{\prime },y^{\prime }]$ invece di $Q(x^{\prime },y^{\prime })$ dall'inizio, perché in quel caso $\mathrm{\Psi }$ non sarebbe stata una formula in $\mathrm{R}$, e quindi non avremmo potuto usare l'induzione. Ecco perché non possiamo usare ingenuamente l'argomento che compare al commento che precede la dimostrazione.

Dimostrazione del teorema per enunciati di grado 1

Come mostrato nel precedente Lemma, dobbiamo dimostrare il teorema solo per le formule $\varphi$ in $\mathrm{R}$ di grado 1. $\varphi$ non può essere di grado 0, poiché le formule in $\mathrm{R}$ non hanno variabili libere e non usano costanti. Quindi la formula $\varphi$ ha la forma generale:

$(\mathrm{\forall }{x}_1\dots \mathrm{\forall }{x}_k)(\mathrm{\exists }{y}_1\dots \mathrm{\exists }{y}_m)\varphi [x_1,\dots ,x_k,y_1,\dots ,y_m]$

Ora, definiamo un ordinamento delle k-uple di numeri naturali come segue: $(x_1,\dots ,x_k)<(y_1,\dots ,y_k)$ se e solo se vale almeno una delle seguenti:

• $\sum _{i=1}^k{x}_i<\sum _{i=1}^k{y}_i$;
• $\sum _{i=1}^k{x}_i=\sum _{i=1}^k{y}_i$ e $(x_1,\dots ,x_k)$ precede $(y_1,\dots ,y_k)$ in ordine lessicografico.

Denotiamo l'ennesima k-upla nell'ordine appena definito con $(a_1^n,\dots ,a_k^n)$.

Poniamo:

• $B_n:=\varphi [z_{a_1^n},\dots ,z_{a_k^n},z_{(n-1)m+2},z_{(n-1)m+3},\dots ,z_{nm+1}]$;
• $D_n:=\mathrm{\exists }{z}_1\dots \mathrm{\exists }{z}_{nm+1}(B_1\wedge \dots \wedge B_n)$.

Lemma: Per ogni intero $n\ge 1$, $\varphi ⟹D_n$.

Dimostrazione: Per induzione su $n$.

Abbiamo:

$\begin{array}{cc}{D}_n& ⟸D_{n-1}\wedge (\mathrm{\forall }{z}_1\dots \mathrm{\forall }{z}_{(n-1)m+1})(\mathrm{\exists }{z}_{(n-1)m+2}\dots \mathrm{\exists }{z}_{nm+1})B_n\\ & ⟸D_{n-1}\wedge (\mathrm{\forall }{z}_{a_1^n}\dots \mathrm{\forall }{z}_{a_k^n})(\mathrm{\exists }{y}_1\dots \mathrm{\exists }{y}_m)\varphi [z_{a_1^n},\dots ,z_{a_k^n},y_1,\dots ,y_m]\end{array}$

dove quest'ultima implicazione vale per sostituzione di variabili, poiché l'ordinamento delle k-uple è tale che, per ogni $k\ge 1$ e per ogni $i\in \{1,\dots ,k\}$, vale $a_i^n\le n<(n-1)m+2$. Ma l'ultima formula è equivalente a $D_{n-1}\wedge \varphi$.

Per il caso base, $D_1=\mathrm{\exists }{z}_1\dots \mathrm{\exists }{z}_{m+1}\varphi [z_{a_1^1},\dots ,z_{a_k^1},z_2,z_3,\dots ,z_{m+1}]\equiv \mathrm{\exists }{z}_1\dots \mathrm{\exists }{z}_{m+1}\varphi [z_1,\dots ,z_1,z_2,z_3,\dots ,z_{m+1}]$ è ovviamente un corollario di $\varphi$. Quindi il Lemma è dimostrato.

Ora, se $D_n$ è refutabile per qualche $n\ge 1$, segue che $\varphi$ è refutabile. D'altra parte, supponiamo che, per ogni $n\ge 1$, $D_n$ sia non refutabile. Allora, per ogni $n\ge 1$, la formula $D{\text{'}}_n:=B_1\wedge \dots \wedge B_n$ non è refutabile. Questa proprietà dev'essere una conseguenza diretta delle regole di deduzione, altrimenti il sistema non potrebbe garantire la propria completezza.

Dunque, per ogni $n\ge 1$, esiste un'assegnazione di verità alle distinte sottoformule $E_h$ (ordinate secondo la loro prima occorrenza in ${D_n}^{\prime }$; "distinto" qui è inteso in senso sintattico, ovvero sia predicati distinti, sia variabili distinte) nelle $B_i$, che rende vera ${D_n}^{\prime }$. Ciò deriva dalla completezza della logica proposizionale sottostante.

Ora, mostreremo che esiste un'assegnazione di verità alle $E_h$ che rende vere tutte le ${D_n}^{\prime }$: le $E_h$ appaiono nello stesso ordine in ogni ${D_n}^{\prime }$; definiremo induttivamente un'assegnazione generale mediante una sorta di "voto di maggioranza": poiché vi sono infinite assegnazioni per $E_1$ (una per ogni ${D_n}^{\prime }$), allora o infinite assegnazioni rendono $E_1$ vera, o solo un numero finito di assegnazioni la rende vera e infinite la rendono falsa. Nel primo caso, $E_1$ sarà vera nell'assegnazione generale, altrimenti sarà falsa. Nell'induzione, rendiamo $E_h$ vera se ci sono infinite assegnazioni che rendono $E_h$ vera, ma solo tra le infinite assegnazioni per le ${D_n}^{\prime }$ che coincidono con l'assegnazione generale da $E_1$ a $E_{h-1}$.

Questa assegnazione generale deve rendere vere ciascuna delle $B_i$ e ${D_n}^{\prime }$, poiché se l'assegnazione falsificasse una delle $B_i$, anche le $D{\text{'}}_j$ sarebbero false per ogni $j>n$. Ma questo contraddice il fatto che, per costruzione dell'assegnazione generale fino alle $E_h$ che compaiono in ${D_n}^{\prime }$, ci sono infiniti $j$ tali per cui l'assegnazione che avvera $D{\text{'}}_j$ coincide con l'assegnazione generale.

Da questa assegnazione, che rende tutte le ${D_n}^{\prime }$ vere, costruiamo un'interpretazione dei predicati del linguaggio che rende vera $\varphi$. Il dominio del modello saranno i numeri naturali. Ogni predicato $p$-ario $\mathrm{\Psi }$ è vero su $(u_1,\dots ,u_p)$ precisamente quando la formula atomica $\mathrm{\Psi }(z_{u_1},\dots ,z_{u_p})$ è vera nell'assegnazione generale, oppure non ha valore di verità (se non compare mai in nessuno dei ${D_n}^{\prime }$).

In questo modello, ciascuna delle formule $\mathrm{\exists }{y}_1\dots \mathrm{\exists }{y}_m\varphi [x_1,\dots ,x_k,y_1,\dots ,y_m]$ è vera per costruzione su ogni assegnazione $\eta$ tale per cui $\eta (x_1)=a_1^n,\dots ,\eta (x_k)=a_k^n$. Ma questo implica che $\varphi$ stessa è vera nel modello, poiché $(a_1^n,\dots ,a_k^n)$ può essere qualunque k-upla di numeri naturali. Quindi $\varphi$ è soddisfacibile, e abbiamo finito.

Spiegazione intuitiva

Possiamo scrivere ogni $B_i$ come $\varphi [x_1,\dots ,x_k,y_1,\dots ,y_m]$ per qualche $x_1,\dots ,x_k$, che possiamo chiamare "primi argomenti", e $y_1,\dots ,y_m$, che possiamo chiamare "ultimi argomenti".

Prendiamo $B_1$, per esempio. I suoi "ultimi argomenti" sono $z_2,z_3,\dots ,z_{m+1}$, e per ogni possibile combinazione di $k$ di queste variabili c'è un qualche $j$ tale per cui esse appaiono come "primi argomenti" in $B_j$. Quindi per $n_1$ sufficientemente grande, $D_{{n_1}^{\prime }}$ ha la proprietà che gli "ultimi argomenti" di $B_1$ appaiono, in ogni possibile combinazione di $k$ di essi, come "primi argomenti" in altri $B_j$ all'interno di $D_{{n_1}^{\prime }}$. Per ogni $B_i$ c'è un $D_{{n_i}^{\prime }}$ con la proprietà corrispondente.

Quindi, in un modello che soddisfa tutti i ${D_n}^{\prime }$, ci sono oggetti corrispondenti a $z_1,z_2,\dots$ e ogni combinazione di $k$ di questi appare come "primo argomento" in qualche $B_j$, nel senso che per ogni $k$ di questi oggetti $z_{p_1},\dots ,z_{p_k}$ ci sono $z_{q_1},\dots ,z_{q_m}$ che rendono $\varphi [z_{p_1},\dots ,z_{p_k},z_{q_1},\dots ,z_{q_m}]$ vera. Prendendo un sottomodello con solo questi $z_1,z_2,\dots$ oggetti, abbiamo un modello che soddisfa $\varphi$.

Estensioni

Estensione al calcolo dei predicati del primo ordine con uguaglianza

Gödel ha ridotto ogni formula in cui occorre il predicato di uguaglianza ad una che definisce l'uguaglianza su di essa. Il suo metodo prevede la sostituzione di una formula $\varphi$ contenente uguaglianze con la formula

$\mathrm{\forall }x(x=x)\wedge \mathrm{\forall }x\mathrm{\forall }y\mathrm{\forall }z[x=y\to (x=z\to y=z)]$ $\wedge \mathrm{\forall }x\mathrm{\forall }y\mathrm{\forall }z[x=y\to (z=x\to z=y)]$

$\wedge$

$\mathrm{\forall }{x}_1\dots \mathrm{\forall }{x}_k\mathrm{\forall }{y}_1\dots \mathrm{\forall }{x}_k[(x_1=y_1\wedge \dots \wedge x_k=y_k)\to (P_1(x_1,\dots ,x_k)\leftrightarrow P_1(y_1,\dots ,y_k))]$

$\wedge ...\wedge$

$\mathrm{\forall }{x}_1\dots \mathrm{\forall }{x}_m\mathrm{\forall }{y}_1\dots \mathrm{\forall }{x}_m[(x_1=y_1\wedge \dots \wedge x_m=y_m)\to (P_n(x_1,\dots ,x_m)\leftrightarrow P_n(y_1,\dots ,y_m))]$

$\wedge \varphi$

Qui $P_1,\dots ,P_n$ denotano i predicati che compaiono in $\varphi$ (con $k,\dots ,m$ le loro rispettive arità). Se questa nuova formula è refutabile, lo è anche l'originale $\varphi$; lo stesso vale per la soddisfacibilità, poiché possiamo prendere l'insieme quoziente del dominio del modello che soddisfa la nuova formula, usando la relazione di equivalenza che rappresenta l'uguaglianza. Questo quoziente è ben definito rispetto agli altri predicati, e quindi soddisferà la formula originaria $\varphi$.

Estensione a insiemi numerabili di formule

Gödel ha anche considerato il caso di insiemi numerabili di formule. Usando le stesse riduzioni di cui sopra, ha potuto considerare solo quei casi in cui ogni formula è di grado 1 e non contiene simboli di uguaglianza. Per un insieme numerabile di formule ${\varphi }^i$ di grado 1, possiamo definire $B_k^i$ come sopra; quindi definire $D_k$ come l'unione di $B_1^1,\dots ,B_k^1,\dots ,B_1^k,\dots ,B_k^k$ . Il resto della prova prosegue come prima.

Estensione a insiemi arbitrari di formule

Nel caso di insiemi non numerabili di formule, è necessario l'assioma della scelta (o almeno una sua forma debole). Usando l'AC completo, si possono ben ordinare le formule e dimostrare il caso non numerabile con lo stesso argomento di quello numerabile, ma con l'induzione transfinita. Altri approcci possono essere usati per dimostrare che il teorema di completezza in questo caso è equivalente al teorema dell'ideale booleano primo, una forma debole di AC.

Bibliografia

• Template:Cita pubblicazione La prima dimostrazione del teorema di completezza.

Voci correlate

• Kurt Gödel
• Prova ontologica di Gödel
• Teoremi di incompletezza di Gödel
• Teorema di completezza di Gödel

Collegamenti esterni

• Stanford Encyclopedia of Philosophy: "Kurt Gödel" — di Juliette Kennedy.
• Biografia di MacTutor: Kurt Gödel.