Nella conferenza inedita sul teorema di completezza, pubblicata nel 1995 nel terzo volume dei Collected works, col titolo “Vortrag ¨uber Vollst¨andigkeit des Funktionenkalk¨uls”, G¨odel definisce in primo luogo la nozione di formula normale come una formula in cui “tutti i quantificatori occorrono all’inizio ... e ... un quantificatore universale viene per primo e un quantificatore esistenziale per ultimo”.31 In secondo luogo egli definisce il grado di una formula normale come “il numero dei blocchi di quantificatori universali”32
in essa occorrenti. A questo punto l’autore traccia le linee essenziali della dimostrazione, individuando i tre seguenti passaggi:
1. se ogni formula normale `e refutabile o soddisfacibile, allora ogni formula `
e refutabile o soddisfacibile;
2. se ogni formula normale di grado k `e refutabile o soddisfacibile, allora ogni formula normale di grado k + 1 `e refutabile o soddisfacibile; 3. ogni formula normale di grado uno `e refutabile o soddisfacibile.
Chiaramente da 2 e 3, per induzione sul grado delle formule normali, si ha che ogni formula normale `e refutabile o soddisfacibile, e quindi, per 1, si ottiene il risultato voluto cio`e l’enunciato di quello che abbiamo chiamato teorema di completezza in forma disgiuntiva.
Detto altrimenti, col punto 1, il problema della completezza in tutta ge- neralit`a viene ridotto al problema della completezza per le formule normali, e dal dominio di tutte le formule del linguaggio di CQC ci si pu`o quindi legit- timamente restringere a quello delle formule normali dello stesso linguaggio. A questo punto `e possibile procedere per induzione sul grado delle formule normali. La base dell’induzione consister`a nel dimostrare che ogni formula normale ϕ di grado uno `e refutabile o soddisfacibile, mentre il passo sar`a dato dalla verifica del fatto che, se ogni formula normale di grado k `e refutabile o soddisfacibile, allora ogni formula normale di grado k + 1 `e refutabile o soddisfacibile.
Il primo passo della dimostrazione di completezza di G¨odel sta comun- que33 nella chiara distinzione delle nozioni di soddisfacibilit`a, validit`a in un
31Cf. G¨odel *1930c in G¨odel 1995, pagg. 20-22. 32Cf. G¨odel *1930c in G¨odel 1995, pag. 22.
modello, validit`a in ogni modello, dal lato semantico, e dimostrabilit`a for- male, refutabilit`a, formula normale, grado di una formula normale, dal lato sintattico.34
Consideriamo lo schema dimostrativo del punto 1. Indichiamo con SR la propriet`a di una formula di essere soddisfacibile o refutabile. Dovremo allora stabilire che: se per ogni formula normale ϕ del linguaggio L di CQC si ha SR(ϕ), allora per ogni formula ψ di L si ha SR(ψ). E’ facile verificare che per ogni formula ϕ di L esiste una formula normale ψ dello stesso linguaggio tale che:
a) CQC ` ϕ ↔ ψ;
b) se ψ `e soddisfacibile, anche ϕ `e soddisfacibile; c) se ψ `e refutabile, anche ϕ ´e refutabile.
Dunque data una formula ϕ di L e la formula normale ψ ad essa associata, se ψ `e refutabile o soddisfacibile, allora anche ϕ `e refutabile o soddisfacibile. Con ci`o il punto 1 di cui sopra risulta dimostrato.
Consideriamo ora il punto 2. Questa parte della dimostrazione si basa sul fatto che, per ogni formula normale ϕ di grado k + 1, si pu`o determinare una formula normale ψ di grado k tale che la refutabilit`a (o soddisfacibilit`a) di ψ implica la refutabilit`a (o soddiffacibilit`a) di ϕ. G¨odel d`a un esempio esplicativo di come ottenere questo risultato. Si consideri la formula:
∀x∃y∀z∃uA(x, y, z, u) (1) dove A(x, y, z, u) `e una formula priva di quantificatori o meglio deve es- sere pensata come “costruita a partire da variabili funzionali soltanto me- diante le operazioni del calcolo proposizionale (dunque senza ∀x o ∃x)”.35 Chiaramente ϕ `e una formula normale di grado 2. Si consideri ora la formula: ∀v∃wF (v, w) ∧ ∀x∀y(F (x, y) → ∀z∃uA(x, y, z, u)) (2) dove F “denota una variabile funzionale a due posti”.36 La forma normale della (2) sar`a la formula:
∀v∀x∀y∀z∃w∃u(F (v, w) ∧ (F (x, y) → A(x, y, z, u))). (3)
34Naturalmente, ci`o non vuol dire che in G¨odel si abbia gi`a una matematizzazione di
queste nozioni, infatti la matematizzazione delle nozioni semantiche di soddisfacibilit`a, validit`a, ecc... si avr`a solo con Tarski.
35Cf. G¨odel *1930c in G¨odel 1995, pag. 22. 36Cf. G¨odel *1930c in G¨odel 1995, pag. 22.
G¨odel osserva che per la formula (2) si ha che:
(a) la formula normale ad essa associata, la (3), ha grado 1;
(b) se essa `e refutabile (o soddisfacibile), allora anche la (1) `e refutabile (o soddisfacibile).
Il punto (a) `e banale. Consideriamo quindi il punto (b) ed in particolare il caso della refutabilit`a. Supponiamo che la formula (2) sia refutabile. Ci`o significa che la formula:
¬(∀v∃wF (v, w) ∧ ∀x∀y(F (x, y) → ∀z∃uA(x, y, z, u))) (4)
`
e dimostrabile. Dunque sar`a dimostrabile anche la formula:
¬(∀v∃w∀z∃uA(v, w, z, u) ∧ ∀x∀y(∀z∃uA(x, y, z, u) → ∀z∃uA(x, y, z, u)) (5)
ottenuta dalla (4) sostituendo ad ogni occorrenza della variabile F la formula ∀z∃uA(x, y, z, u). Affinch´e la formula (5) sia vera occorre che una delle due formule:
∀x∀y(∀z∃uA(x, y, z, u) → ∀z∃uA(x, y, z, u)) (6) o
∀v∃w∀z∃uA(x, y, z, u) (7) sia falsa. La (6) `e chiaramente vera (oltre che dimostrabile in CQC). Dunque la (7) sar`a invece falsa e di conseguenza refutabile. Ma la formula (7) non `e altro che un cambio alfabetico della (1) e quindi, come volevasi dimostrare, dalla refutabilit`a della (2) segue la refutabilit`a della (1). In modo analogo, spiega G¨odel, si dimostra che dalla soddisfacibilit`a della (2) segue la soddi- sfacibilit`a della (1). Ci`o naturalmente non costituisce una dimostrazione del passo induttivo bens`ı un’esemplificazione di come si dovrebbe procedere nel caso generale.
Il punto 3 della strategia g¨odeliana consiste nel dimostrare che, per ogni formula normale ϕ di grado 1, ϕ `e soddisfacibile o refutabile. Anche per que- sta parte della dimostrazione, in G¨odel *1930c, l’autore, anzich´e procedere in piena generalit`a come negli articoli pubblicati, illustra invece la procedura dimostrativa con un esempio. Sia ϕ la formula:
dove A(x, y, z) `e una formula priva di quantificatori. Si consideri ora la successione di formule: A(x0, x1, x2), A(x1, x3, x4), A(x2, x5, x6), .... .... A(xn, x2n+1, x2n+2),
che si ottiene da ϕ rimpiazzando successivamente x con le variabili x0, ..., xn
e y, z con variabili sempre nuove. Chiamiamo An la chiusura congiuntiva
delle prime n formule cos`ı ottenute:
A(x0, x1, x2) ∧ A(x1, x2, x3) ∧ ... ∧ A(xn, x2n+1, x2n+2)
e PnAn la chiusura esistenziale di An, cio`e la formula:
∃x0∃x1...∃x2n+2An.
Chiaramente ϕ → PnAn `e una tautologia ossia per ogni valutazione V del
linguaggio L si ha che:
V |= ϕ → PnAn.
Inoltre in CQC si dimostrano le seguenti implicazioni: ∀x∃y∃zA(x, y, z) → ∃y∃zA(x0, y, z), ∃y∃zA(x0, y, z) → ∃x0∃x1∃x2A(x0, x1, x2), ϕ → P1A1. Analogamente in CQC `e dimostrabile: ∀x∃y∃zA(x, y, z) → ∃x1∃x3∃x4A(x1, x3, x4) e quindi: ϕ → P2A2.
Procedendo in questo modo per induzione si ottiene quindi che per ogni n ∈ N CQC ` ϕ → PnAn.
Ma il frammento puramente esistenziale di CQC `e decidibile e di conseguenza per ogni n ∈ N, PnAn `e soddisfacibile o refutabile. Per il principio del
terzo escluso si danno quindi solo due possibilit`a: o tutte le PnAn sono
soddisfacibili oppure almeno una delle PnAn `e refutabile. Ossia abbiamo
un’alternativa secca fra le due seguenti proposizioni:
A1. per ogni numero naturale n, esiste una valutazione V di L tale che: V |= PnAn;
A2. per qualche numero naturale n:
CQC ` ¬PnAn.
Se vale la proposizione A2 allora poich´e:
CQC ` ϕ → PnAn
per contrapposizione e modus ponens otteniamo che: CQC ` ¬ϕ.
Ossia: se c’`e un numero naturale n tale che PnAn `e refutabile, allora ϕ `e
refutabile. D’altro canto, se vale la clausola A1 cio`e se per ogni numero naturale n esiste una valutazione V di L tale che:
V |= PnAn,
allora per ogni numero naturale n esiste una valutazione V di L tale che: V |= Pn−1An−1,
V |= Pn−2An−2,
.... .... V |= P0A0.
Da ci`o segue, per il lemma di K¨onig,37 che le formule PnAn sono tutte sod-
disfacibili simultaneamente. Ossia, dal fatto che per ogni n ∈ N esiste una
valutazione V di L che soddisfa PnAnsegue che esiste una valutazione V∗ di L
che soddisfa tutte le PnAn. Ci`o significa esattamente che per ogni oggetto o
della base cod(V∗) della valutazione V∗ esistono due oggetti o1, o2 ∈ cod(V∗)
tali che: V∗(xo)( y o1)(zo2)|= A(x, y, z) ossia che: V∗ |= ∀x∃y∃zA(x, y, z).
Dunque: se ogni PnAn `e soddisfacibile, allora ϕ `e soddisfacibile.
Con questo termina lo schizzo di dimostrazione proposto in G¨odel *1930c.