Gödel, Kurt

logico e matematico di origine cecoslovacca naturalizzato statunitense (Brno 1906-Princeton 1978). Libero docente all'Università di Vienna (1933-38), fece parte del cosiddetto circolo di Vienna. Dopo il 1938 si trasferì negli Stati Uniti; fu membro e, dal 1953, professore all'Institute for Advanced Study di Princeton. La sua non vasta produzione scientifica (una monografia e ca. venti articoli) rappresenta un momento basilare nella storia della logica classica e intuizionista. Nel 1930 esponeva il teorema di completezza e compattezza per il calcolo dei predicati del primo ordine o senza identità (Die Vollständigkeit der Axiome des logischen Funktionenkalküls, La completezza degli assiomi del calcolo funzionale di logica). L'anno seguente, nello scritto Über formal unentscheidbare Sätze der “Principia mathematica” und verwandter Systeme (Sulle proposizioni formalmente indecidibili dei “Principia mathematica” e di sistemi affini), stabiliva il noto teorema di incompletezza dell'aritmetica e di quello relativo alle dimostrazioni di non contraddittorietà. Nel 1940 dava le dimostrazioni di consistenza relative all'assioma di scelta e all'ipotesi generalizzata del continuo con gli altri assiomi della teoria degli insiemi (The Consistency of the Axiom of Choice and of Generalized Continuum Hypothesis). Notevole inoltre la sua analisi dei rapporti tra logica intuizionista e classica nonché tra logica modale e intuizionista.

Teorema di Gödel

Esso dimostra che nei sistemi formali, come quello dei Principia mathematica, si danno proposizioni che non sono dimostrabili o derivabili nel sistema stesso, pur essendo “vere” (incompletezza dell'aritmetica). Questa dimostrazione è caratterizzata da due momenti fondamentali: l'aritmetizzazione della sintassi e, tramite questa, l'espressione nella teoria di tutte le proposizioni metateoriche a essa relative senza che si generi confusione tra teoria e metateoria; la dimostrazione che esiste una formula, costruita in modo effettivo, che non è dimostrabile o derivabile nella teoria stessa con i mezzi dimostrativi di cui essa dispone. Gödel prende in considerazione il sistema logico dei Principia mathematica e associa a ogni simbolo primitivo un numero. Per esempio, sia M il sistema e siano “¬”; “ ”; “(”; “)”; “,”; “x”; “y”; “z”; “ ”; “=”; “O”; “´”; “+”; “.”; “∃”; “∀” i simboli primitivi di M, allora:

Così, per esempio, alla formula (x=y) corrisponde la sequenza 5, 11, 19, 13, 7. Questa viene associata alle potenze di numeri primi come segue:

Il risultato di questo prodotto è il numero di Gödel, o gödeliano, della formula considerata. Ora, siano n₁, n₂,..., n_k i gödeliani di una sequenza di segni di M, allora il gödeliano di questa sequenza è dato dal prodotto

.

È facile vedere che a ogni formula è possibile associare uno e un solo numero di Gödel e che da un numero di Gödel è possibile, grazie alla legge della scomposizione in fattori primi, pervenire a una e una sola formula di M. Lo stesso vale per ogni sequenza di formule. Questa procedura non solo è effettiva e decidibile, ma consente di formulare la metateoria sintattica: ogni proprietà, relazione o enunciato su formule, dimostrazioni, ecc. di M si trasforma in una proprietà, relazione o enunciato tra numeri. Si consideri ora il predicato metamatematico: (1) “a è una dimostrazione di b”. Esiste allora un predicato aritmetico P(x, y) che gli corrisponde, tale cioè che esso vale se e solo se a è il gödeliano della formula che ha per gödeliano il numero b. Si consideri ora la funzione ricorsiva primitiva d=f(s, t) in cui d è il gödeliano della formula ottenuta quando si rimpiazza nella formula, il cui gödeliano è s, ogni occorrenza libera della variabile y con O, la cifra nel sistema M del numero t (se y non occorre in s, allora d=s). Essa è effettivamente calcolabile. Gödel mostra che il predicato (1) è ricorsivo primitivo, cioè che la sua funzione caratteristica è una funzione ricorsiva primitiva. Ora le funzioni ricorsive primitive sono numericamente rappresentabili in M nel senso che se, per esempio, la funzione u=φ(s) è ricorsiva primitiva, esiste una formula A(x, y) tale che A(O, O) è dimostrabile se u≠φ(s) e ¬A(O, O) se u≠φ(s). Si considerino ora la funzione ricorsiva primitiva d=f(s, t) e i predicati (1) e “u è una dimostrazione di f(t, t)”, che chiamiamo (2), ottenuta per sostituzione. La (2) è numericamente rappresentabile in M dalla formula Q(x, y). Sia ora i il gödeliano della formula ∀x¬Q(x, y) e sia G il nome della formula ∀x¬Q(x, O). L'enunciato del teorema si può così formulare: se M è consistente, allora G non è dimostrabile. Lo schema della dimostrazione procede nel modo seguente: il gödeliano di G è f=(i, i), poiché G si ottiene quando nella formula, il cui gödeliano è i, si rimpiazza y con O. Se G è dimostrabile, il predicato “u è una dimostrazione della formula il cui gödeliano è f=(i, i)” sarà valido per qualche u e quindi Q(O, O) sarà dimostrabile per qualche k in M. Si può quantificare questo fatto con ∃xQ(x, O). Questa sarà dimostrabile e lo sarà per la regola di quantificazione anche ¬∀x¬Q(x, O). Ma questa è ¬G. Ora se G e ¬G sono entrambe dimostrabili in M, allora M è inconsistente. Quindi se M è consistente, allora G non è dimostrabile. D'altra parte si dimostra anche che se M è ω-consistente, cioè se per nessuna formula A(x) sono simultaneamente dimostrabili in M: A(O), A(O´), A(O‟,... e non ∀xA(x), nemmeno ¬G può essere dimostrabile. Si ha allora una formula G, “vera” che è nel linguaggio di M, ma tale che né G né ¬G sono dimostrabili in M, per cui G è indecidibile e M è incompleto. Da questo teorema, noto come primo teorema di Gödel, se ne ottiene un altro (secondo teorema di Gödel) il quale afferma che “se M è consistente, non è possibile dimostrare in M la formula Cons(M), dove Cons(M) esprime in termini aritmetici la consistenza di M”. Se si ammette con D. Hilbert che i metodi finitisti siano non più forti di quelli formulabili nell'aritmetica, ne risulta che non esiste dimostrazione finitista della consistenza dell'aritmetica. Da qui il significato rivoluzionario del teorema di Gödel nei confronti del programma hilbertiano.