Aritmetica classica e intuizionista: la traduzione negativa

Nel 1932 G¨odel tenne, su invito di Karl Menger, un intervento al Mengers Kolloquium, dedicato all’aritmetica intuizionista, quella che oggi viene comu-

nemente chiamata “aritmetica di Heyting” (HA). Una sintesi di quell’inter- vento fu pubblicata nel 1933 col titolo “Zum intuitionistischen Arithmetik und Zahlentheorie”87 sugli Ergebnisse.88

Si tratta di un contributo davvero notevole nell’ambito della precisazione della logica e della matematica intuizioniste in quanto mostra che, almeno dal punto di vista formale, in un certo senso l’aritmetica intuizionista e quella classica sono (deduttivamente) equivalenti.

G¨odel cita i fondamentali articoli di Heyting “Die formalen Regeln der intuitionistischen Logik” (1930) e “Die formalen Regeln der intuitionistischen Mathematik” (1930) a proposito dei sistemi formali che oggi chiameremmo IPC, IQC e HA89_{. Egli fa inoltre riferimento all’articolo di Valerii I. Gli-}

venko “Sur quelques points de la logiques de M. Brouwer” (1929) per quanto riguarda l’interpretabilit`a di CPC in IPC e ai due articoli di Herbrand “Les bases de la logique hilbertienne” (1930) e “Sur la non-contradiction de l’ari- thmetique” (1931), rispettivamente, per una caratterizzazione della nozione di “dimostrazione finitista” nel senso di Hilbert e per un sistema formale per l’aritmetica classica.

Dopo aver osservato che, sulla base dell’interpretazione di Glivenko del frammento di CPC basato sull’insieme {¬, ∧} di connettivi “il calcolo pro- posizionale classico `e ... un sottoinsieme di quello intuizionista”,90 _G¨odel

descrive l’obiettivo del suo contributo come un tentativo di far vedere che qualcosa di simile si verifica anche per l’aritmetica classica. L’autore ca- ratterizza quindi il principale risultato che andr`a a dimostrare, nei seguenti termini:91

... possiamo fornire un’interpretazione delle nozioni classiche in termini di quelle intuizioniste tale che ogni proposizione dimostrabile a partire dagli assiomi classici vale pure per l’intuizionismo.

Ossia, egli dimostra il seguente:

Teorema. Esiste un’applicazioneN dall’insieme delle formule di PA sull’in- sieme delle formule di HA tale che per ogni formula ϕ del linguaggio

87_{Cf. G¨odel 1933a.}

88_{Che, come si sapr`a, erano proprio gli atti del Mengers Kolloquium.}

89_{Rispettivamente: il calcolo proposizionale intuizionista, il calcolo quantificazionale}

intuizionista e l’aritmetica intuizionista o aritmetica di Heyting.

90_{Cf. G¨odel 1933a in G¨odel 1986, pag. 286.} 91_{Cf. G¨odel 1933a in G¨odel 1986, pag. 288.}

di PA:

PA ` ϕ ⇐⇒ HA ` ϕN.

Chiaramente la parte da destra a sinistra dell’equivalenza `e banale, visto che per un’opportuna formulazione dei due sistemi si ha che:

HA ⊂ PA.

La dimostrazione della parte da sinistra a destra del teorema di basa invece sulla traduzione N definita per induzione come segue.

Base. Se ϕ `e atomica: - ϕN _{:= ϕ.}

Passo. Se ϕ e ψ sono due formule del linguaggio di PA: - (¬ϕ)N := ¬ϕN, - (ϕ ∧ ψ)N _{:= ϕ}N _{∧ ψ}N_, - (ϕ ∨ ψ)N _{:= ¬(¬ϕ}N _{∧ ¬ψ}N_), - (ϕ → ψ)N := ¬(ϕN ∧ ¬ψN_), - (∀xϕ)N _{:= ∀xϕ}N_, - (∃xϕ)N _{:= ¬∀x¬ϕ}N_.

L’idea alla base di questa traduzione `e analoga a quella di Glivenko:92 _es-

sa trasforma le formule dell’aritmetica classica in formule contenenti solo i connettivi non problematici dal punto di vista intuizionista ¬, ∧, ∀.93

La dimostrazione del Teorema `e del tutto simile a quella del Teorema relativo alla traduzione modale. Essa procede cio`e per ispezione degli as- siomi di PA e verificando che dalla dimostrabilit`a della N-traduzione delle premesse di una certa regola segue la dimostrabilit`a della N_{-traduzione della}

conclusione di quella regola.

Per semplificare la dimostrazione del Teorema, G¨odel dimostra prima due risultati ausiliari. Il primo `e il seguente:

92_{Cf. Glivenko 1929.}

93_{Altre traduzioni sono state formulate in 1925 da Kolmogorov (per il calcolo proposi-}

zionale), nel 1933 da Bernays e Gentzen (per l’aritmetica) e in 1951 da Kuroda. Si pu`o dimostrare che queste traduzioni sono tutte fra loro equivalenti a livello proposizionale, predicativo e aritmetico.

Lemma 1. Per ogni formula ϕ del linguaggio di PA si ha: HA ` ¬¬ϕN → ϕN_.

Questo risultato lo si dimostra facilmente per induzione sulla complessit`a logica di ϕ (cio`e sul numero di connettivi e quantificatori occorrenti in ϕ).

Il secondo risultato ausiliario `e il seguente:

Lemma 2. Per due qualsiasi formule ϕ, ψ del linguaggio di PA: HA ` (ϕN → ψN_{) ↔ ¬(ϕ}N _{∧ ¬ψ}N_).

G¨odel conclude il suo articolo con una serie di osservazioni che vale la pena di considerare nel dettaglio. La prima `e che il Teorema sulla doppia negazione evidenzia il fatto che l’aritmetica di Heyting costituisce “solo appa- rentemente” una restrizione dell’aritmetica di Peano, mentre di fatto, modulo l’interpretazioneN_{, la contiene. L’autore spiega questo risultato sorprendente}

sulla base del fatto che:94

... la proibizione intuizionista contro la riformulazione di negazioni di pro- posizioni universali come proposizioni puramente esistenziali non ha alcun effetto visto che il predicato di assurdit`a pu`o essere applicato a proposizioni universali e ci`o conduce a proposizioni che, formalmente, sono esattamente le stesse di quelle asserite dalla matematica classica.

Come vedremo nel prossimo paragrafo dedicato alla “Dialectica interpreta- tion” G¨odel ribadir`a in vari lavori degli anni Trenta e Quaranta95 _{il fatto che}

uno dei punti deboli del costruttivismo di ispirazione intuizionista sta pro- prio nel fatto di ammettere l’uso dei connettivi logici ed in particolare della negazione su proposizioni quantificate universalmente. In tal modo, sostiene G¨odel, il divieto nei confronti delle proposizioni esistenziali non-costruttive finisce per essere inutile.

Proprio in quest’ottica si inserisce anche l’osservazione successiva dell’au- tore, secondo cui l’intuizionismo introduce restrizioni essenziali della mate- matica classica solo nell’analisi e nella teoria degli insiemi, e non a causa del rifiuto del principio del terzo escluso, bens`ı per quello delle definizioni impredicative.

L’articolo termina con una nota relativa al seguente corollario del Teorema sulla traduzione negativa:

94_{Cf. G¨odel 1933a in G¨odel 1986, pag. 294.}

Corollario. Se HA `e noncontraddittoria, allora anche PA lo `e.

G¨odel osserva che, sebbene la traduzione negativa fornisca una dimostrazione di noncontraddittoriet`a per l’aritmetica classica, non si tratta certo di una dimostrazione finitista nel senso di Hilbert. Insomma, il Teorema fornisce una dimostrazione di noncontraddittoriet`a nel senso che si hanno due sistemi formali S ⊂ T e si dimostra che:

W id_S → W id_T.

Il problema `e che con ci`o si ottiene solo un risultato di noncontraddittoriet`a relativa e quindi non si arriva all’obiettivo desiderato a meno che non si as- suma o si dimostri in qualche modo la noncontraddittoriet`a del sistema S. In un certo senso invece questa dimostrazione pu`o essere considerata valida dal punto di vista intuizionista e questa volta non in quanto riduzione del pro- blema della consistenza da un certo sistema formale ad un suo sottosistema, bens`ı in quanto riduzione del problema da un sistema meno intuitivo ad uno pi`u intuitivo.