La Logica matematica dopo Gödel

Dr. Giuseppe Raguní Universitá UCAM di Murcia, Spagna, graguni@ucam.edu

1. Introduzione
2. Una revisione “semantica” della Logica
3. Informalizzabilità intrinseca dell’induzione completa
4. Una generalizzazione del Teorema d’incompletezza di Gödel
5. Esempi di Aritmetiche formali del secondo ordine
6. Paradossi e Teorema di incompletezza
7. Referenze

Abstract

In complemento al libro “I confini logici della Matematica” dello stesso autore, si sottolinea l’esigenza di una revisione di tipo semantico della Logica matematica. Essa, trascurando la classificazione delle Teorie in base all’ordine espressivo, rivaluta il ruolo della Teoria formale degli insiemi. Inoltre si indeboliscono le ipotesi del primo Teorema d’incompletezza e si chiarisce la sua esatta relazione con i paradossi semantici (di Berry, Richard, etc.).

In addition to the book “I confini logici della Matematica” by the same author, it is emphasized that a semantic type revision of the mathematical Logic is necessary. Neglecting the usual expressive-order type classification of Theories, this revision re-evaluates the role of the formal Set Theory. Moreover it is achieved a weakening of the hypotheses of the first incompleteness Theorem and its exact relationship with the semantic paradoxes (Berry, Richard, etc.) is clarified.

PAROLE CHIAVE: Teorema d’incompletezza di Gödel, semantica, metamatematica, paradossi, aritmetica del primo ordine, aritmetica del secondo ordine.

KEYWORDS: Gödel’s incompleteness Theorem, semantics, metamathematics, paradoxes, first order arithmetics, second order arithmetics.

1 Introduzione

Chiunque abbia mai scritto un libro, specie se con un considerevole contenuto tecnico, sa bene quanto sia oneroso il lavoro di correzione delle bozze. Se poi esso introduce novità, può succedere che molti argomenti evolvano come per conto proprio, chiarendosi e ridefinendosi in nuove prospettive. A quel punto per l’autore è fortissimo il desiderio di modificare ed integrare il testo. Uno dei principali vantaggi dell’odierna modalità di pubblicazione on-line dei testi digitalizzati consiste proprio nella facilità con cui l’autore può realizzare questo lavoro. A partire dalla sua prima pubblicazione, nell’aprile 2009, il testo de “I confini logici della Matematica” ha infatti subito diverse modifiche, l’ultima alla fine del 2011; comunque, nessuna di esse ha mai alterato le originali conclusioni filosofiche dell’opera.

Da quella data ho deciso di trattare autonomamente – come in questo articolo – ogni successivo chiarimento o integrazione. Per due ragioni fondamentali. La prima è che molti argomenti di chiarificazione finiscono, col tempo, per acquistare una importanza intrinseca e ogni tentativo di integrarli nel testo originale comporta una riduzione della loro valenza. La seconda, in considerazione dell’opportunità che ogni opera ben definita, dopo alcuni anni di assestamento, debba darsi per conclusa, pur con i difetti che, anche agli occhi dello stesso autore, contiene.

Il primo paragrafo di questo articolo è un importante commento circa l’approccio, per così dire semantico, che il libro propone per una moderna revisione della Logica. Si rileva che tale aggiornamento è necessario, in quanto molti argomenti ristagnano da troppo tempo nell’ambiguità di una presuntuosa impostazione sintattica. La nuova prospettiva, inoltre, rivaluta il ruolo della Teoria formale degli insiemi: un risvolto che nel libro potrebbe esser passato inavvertito.

Il secondo paragrafo è una rettifica di un passaggio tecnico nell’ambito della rappresentazione dell’Aritmetica in seno alla Teoria formale degli insiemi, trattata nel paragrafo II.14 del libro. Fortunatamente, il dettaglio non ha alcuna ripercussione sulle conclusioni del paragrafo: una ragione in più per non modificare il libro. Chiarire qui il punto soddisferà i lettori più tecnici, anche perché ne approfitto per approfondire diversi dettagli.

Nel terzo paragrafo si dimostra che le ipotesi del famosissimo primo Teorema d’incompletezza di Gödel possono indebolirsi: per la Teoria aritmetica è sufficiente che gli assiomi siano ricorsivamente numerabili e non necessariamente ricorsivi (ovvero, dall’ambito meccanico, decidibili[1]). Questo fatto, che nel libro, per eccessiva prudenza, è stato soltanto suggerito, ha invero una dimostrazione assai facile e per l’importanza del Teorema merita senz’altro di essere enfatizzato.

Nel paragrafo seguente esemplifico, molto brevemente, due casi di Teorie aritmetiche formali del secondo ordine: un argomento relativamente recente con ancora molto da scoprire.

L’ultimo paragrafo, infine, intende delucidare il legame tra il Teorema di incompletezza (nelle sue diverse versioni, sia matematiche che metamatematiche) e alcuni classici paradossi semantici (come quelli di Berry e di Richard). Se ne approfitta per ribadire il vero e concreto risvolto semantico di tali paradossi, così come è stato proposto, probabilmente per la prima volta, nel libro.

I paragrafi più importanti di questo documento, il 2 e il 6, devono la loro esistenza (come probabilmente l’intero articolo) all’intenso scambio epistolare che ho avuto con Giangiuseppe Pili, un eclettico filosofo, scacchista, epistemologo (per limitarmi), autore di diversi libri e curatore di un ammirevole sito web: www.scuolafilosofica.com. A lui un grazie di cuore per la sua contagiosa passione per il Sapere.

2 Una revisione “semantica” della Logica

Una recensione di Pili al libro, da poco apparsa nel suo sito web, evidenzia l’impostazione per così dire semantica della proposta revisione della Logica. Egli scrive:

<<[nel libro]… l’analisi semantica delle questioni interne alla Logica matematica, diventa sia metodo (chiarificazione terminologica dei concetti e termini fondamentali) sia scopo (la metamatematica è, in fondo, l’oggetto di analisi…) … L’autore riesce nell’intento di ridare uno spessore importante, assai spesso sottovalutato, alla metamatematica, vale a dire alla discussione semantica sui temi propriamente sintattici della logica matematica… E ciò non solo in termini propriamente descrittivi… ma pure in termini puramente logici, cioè fornendo metadimostrazioni di cui il suo Metateorema dell’indimostrabilità interna della coerenza rimane il caso più emblematico>>

In effetti in Logica matematica viene oggi esageratamente privilegiato l’aspetto sintattico, come se l’interpretazione degli enunciati, che in fondo costituisce l’obiettivo, fosse sempre spontanea ed esente da problemi. L’aspetto forse più eclatante di tale grossolanità si osserva nell’abuso del termine formale, oggi adoperato anche per Teorie che sono intrinsecamente semantiche. Perchè questa grave confusione? Nel nostro lavoro abbiamo recuperato – in un processo mosso solo da spontanea ragionevolezza – l’originale significato hilbertiano dell’aggettivo: equivalente a privo di significato (e quindi lo stesso che sintattico, codificato, simbolico, etc.).

L’eccessiva importanza data alle stringhe simboliche ha addirittura condotto a catalogare le stesse Teorie assiomatiche in funzione del loro ordine espressivo (primo ordine, secondo ordine, etc.) invece che in base al rispetto o non rispetto della formalità hilbertiana. E l’infelice neo-ambiguità del termine formale si spiega proprio con l’ingiustificabile trascurare di distinguere il caso in cui gli enunciati debbono possedere significato, da quello in cui esso è eliminabile. Per quale mistica ragione l’uso dei quantificatori ∃ e ∀ sui predicati (o super-predicati, etc.) dovrebbe dar luogo a una situazione in qualche modo peculiare? Nel libro abbiamo osservato che la chiave della faccenda risiede nella possibile innumerabilità degli enunciati: infatti, se l’universo è infinito (il caso più usuale), i predicati spaziano – in assenza di altri assiomi limitanti – su un insieme senz’altro più che numerabile. E il fattore scatenante è dato proprio dalle conseguenze semantiche dell’innumerabilità, un argomento inspiegabilmente ignorato o trascurato dalla “Logica ufficiale”. Succede infatti che un linguaggio più che numerabile è necessariamente semantico: una stessa sequenza simbolica dovrà indicare più cose e ciò può farsi solo mediante l’uso di significati variabili e dunque ineliminabili (par. II.13); oppure la “numerabilità” degli enunciati è incodificabile nella Teoria formale degli insiemi (TI) e da ciò deriva ancora intrinseca semanticità[2].

Ma anche nei Sistemi di ordine superiore al primo con modelli infiniti, la formalità può ristabilirsi mediante opportuni schemi assiomatici di comprensione, che limitano la variabilità dei predicati (o super-predicati, etc.) a collezioni che dovranno essere necessariamente numerabili. Questo criterio viene chiamato della Semantica generale[3]: ma perchè non chiamarlo semplicemente rispetto della formalità (hilbertiana)? In condizioni di formalità valgono sempre la numerabilità, la completezza semantica, la compattezza e il Teorema di Löwenheim-Skolem. Normalmente, invece, queste caratteristiche sono considerate come proprie del primo ordine espressivo: un grave errore, visto che sono possibili Sistemi assiomatici del primo ordine innumerabili (e dunque intrinsecamente semantici) in cui non valgono (par. II.14).

La nostra revisione, ribadiamo, propone semplicemente di rappresentare il Sistema in TI (l’unica Teoria in cui le cardinalità sono rigorosamente definite) allo scopo non soltanto di escludere o concludere la formalità (che si avrà se e solo se gli assiomi sono numerabili e privi di significato) ma anche di verificare se gli assiomi sono o non sono decidibili (oppure, più generalmente effettivamente numerabili: cosa che si avrà se e solo se lo schema assiomatico che li genera è fedelmente riproducibile in TI, par. III.3). Quest’ultima è una proprietà chiave per stabilire se è possibile applicare il Teorema d’incompletezza alla Teoria.

Questo criterio, dunque, rivaluta fortemente il ruolo della Teoria assiomatica degli insiemi nell’ambito della Logica matematica.

Anche le scorrette valenze del secondo Teorema di Gödel (riassumibili col ritenere che “un Sistema che soddisfa le sue ipotesi non può dimostrare la propria coerenza”) si devono all’esaltato, errato, approccio sintattico di cui stiamo parlando: in verità il fatto che una Teoria non possa dimostrare la propria coerenza è una conclusione metamatematica, e specificamente semantica, che vale per qualsiasi Sistema assiomatico classico, incluso non formale (Metateorema dell’indimostrabilità interna della coerenza, par. III.10).

Il significato è la necessaria premessa per la definizione di un qualsiasi linguaggio e solo mediante esso (o la sua assenza) può caratterizzarsi la sua natura espressiva; di fatto ciò accade anche per la stessa differenziazione degli ordini d’espressione: come potrebbe farlo un codice meramente simbolico in cui gli stessi quantificatori logici devono essere considerati come muti (o con un valore semantico ridefinibile in principio)? E, naturalmente, il significato è anche l’obiettivo, perchè le catene di caratteri, da sole, non sono che variegate macchiette nere. La Logica matematica non si fonda, pertanto, sulla sola struttura delle stringhe simboliche, ma non può che consistere in essenza di deduzioni informalizzabili, necessariamente semantiche. Perchè non è una Teoria assiomatica, ma pur sempre filosofia: rigorosa filosofia.

3 Informalizzabilità intrinseca dell’induzione completa

A metà del paragrafo II.14 descrivo, schematicamente, la rappresentazione delle due principali Teorie aritmetiche, PA e AI, in seno alla Teoria formale degli insiemi (TI). Ricordo che i Sistemi PA (Aritmetica formale di Peano) e AI (Aritmetica integrale, identificabile con quella chiamata frequentemente “Aritmetica del secondo ordine”), differiscono per l’ambito di applicabilità del principio d’induzione: nel primo caso, limitato alle proprietà esprimibili con proposizioni simboliche del Sistema con almeno una variabile libera (induzione parziale). Nel secondo, generalizzato a qualsiasi proprietà (anche non esprimibili in linguaggio simbolico, ovvero intrinsecamente semantiche) dei numeri naturali (induzione completa).

Rettificherò un dettaglio circa la rappresentazione insiemistica di AI. Ma prima di farlo è opportuno richiamare i fondamenti del procedimento.

La rappresentazione insiemistica di cui stiamo parlando è quella in cui le collezioni delle proposizioni e dei teoremi (includendovi gli assiomi) della Teoria vengono riprodotte con veri e propri insiemi, cioè con gli enti rigorosamente definiti in TI. Le proposizioni della Teoria vengono rappresentati con sequenze di simboli-insiemi (anch’esse costituendo un insieme, naturalmente). Infatti tutti i simboli classici: non, e, ∀, etc.[4] possono essere ridefiniti come insiemi in TI (par. II.7). In questo caso li distingueremo con un asterisco: non*, e*, ∀*, → *, e così via[5].

Cominciamo, come premessa chiarificatrice, con la rappresentazione di PA. La specificazione dell’insieme delle proposizioni di PA (ovvero della sua grammatica) può realizzarsi con la stessa assoluta fedeltà del caso di un generico Calcolo logico classico: anche la grammatica propria di PA (che, per esempio, stabilisce l’uso corretto del simbolo “+”) può riprodursi grazie al concetto di sequenza ordinata, rigorosamente formalizzato in TI (par. II.6).

Passando alla definizione dell’insieme, T, dei teoremi di PA, il primo assioma di Peano si può rendere con la definizione implicita:

(∃*, x*, (*, x*, =*, 0*, )*) ∈T

dove, per semplicità, si è introdotto un simbolo-insieme anche per le parentesi (le quali, in verità, non sono necessarie). Analogamente si esprimeranno gli altri assiomi che precedono il principio di induzione parziale[6].

Per riprodurre quest’ultimo, bisogna dichiarare, in linguaggio insiemistico, che la proposizione “se una proprietà è soddisfatta dal numero 0 ed è tale che se è soddisfatta da un certo numero naturale allora è soddisfatta anche dal successivo, converremo che sia valida per tutti i naturali” faccia parte dell’insieme dei teoremi della rappresentanda PA, qualunque sia la proprietà esprimibile con una proposizione con almeno una variabile libera. La soluzione presentata nel libro:

(A*(0*),e*,∀*,x*, …,→*,∀*, x*,(*, A*(x*), )*)∈T, ∀A*(x*)∈P₁

dove P₁ è l’insieme, infinito numerabile, di tutte le proposizioni con almeno una variabile libera della rappresentanda PA; esso è un preciso sottoinsieme dell’insieme delle proposizioni, P, prima definito. La sequenza “A*(x*)” per indicare il generico elemento di P₁ vuole agevolare la comprensione e non deve ingannare: un arbitrario elemento di P₁ (che, se il lettore lo preferisce, può essere indicato semplicemente con A) è costituito da una sequenza di simboli-insieme che contiene almeno una variabile libera-insieme. La sequenza “A*(0*)” (che, allo stesso modo, potrebbe essere indicata con un’altra qualsiasi lettera) denota l’insieme ottenuto da A sostituendo il simbolo- insieme 0* a tale variabile libera-insieme. Tale operazione di sostituzione può essere perfettamente definita in TI e, naturalmente, deve accompagnare la precedente dichiarazione (cosa da noi sottintesa, appunto, mediante l’uso delle discusse sequenze).

Fin qui, dunque, tutto OK. Ma veniamo al caso cruciale della rappresentazione insiemistica di AI. La strategia per riprodurre l’induzione completa non può che essere quella di far corrispondere alla generica proprietà dei numeri naturali, chiamiamola a, il sottoinsieme dei numeri naturali, A, che la soddisfano. E conseguentemente riprodurre la proposizione dell’originale Sistema AI, “x gode della proprietà a“, con qualcosa di simile a “(x*, ∈*, A)” nella Teoria rappresentata. Tuttavia il simbolo di appartenenza non può essere ridotto a insieme: ciò equivarrebbe a cercare di rappresentare TI all’interno di TI, cosa impossibile (par. II.7). Pertanto ho cercato di riprodurre il fatto che x* appartiene ad A semplicemente mediante la sequenza: “A, (*, x*, )*”. Per farlo, bisogna introdurre degli appositi assiomi di comprensione; i quali, essendo di numero infinito numerabile, devono essere prodotti da uno schema assiomatico. Ma ora, senza preoccuparci di specificare tale schema, pensiamo come realizzato questo lavoro e saltiamo addirittura al passo successivo, cioè alla rappresentazione dell’induzione completa. Secondo il nostro criterio essa si esprimerebbe finalmente con:

(A,(*,0*,)*,e*,∀*, x*, …,→*,∀*, x*,(*, A,(*, x*,)*,)*)∈T, ∀A∈P(U)

dove P(U), essendo l’universo U identificabile con N, è un insieme innumerabile (ovvero più che numerabile[7]). Pertanto, prima ancora di specificare tutti i dettagli della riproduzione insiemistica dell’induzione completa, si può già affermare con certezza che l’originale Teoria AI non può essere formale. In ogni caso, l’innumerabilità degli enunciati induttivi, nella sua rappresentazione in TI, rivela l’uso di ineliminabile semantica per esprimerli. Possono allora seguire tutte le altre conclusioni riferite nel libro.

Il punto è che se poi si cerca di specificare tali dettagli, ovvero di formalizzare il suddetto schema assiomatico di comprensione, ci si imbatte in una difficoltà che adesso – a differenza di come affermo nel libro – giudico insormontabile. Che è proprio ciò che voglio rettificare. Non è che l’espressione dello schema assiomatico sia scorretta (o correggibile): l’abbaglio risiede proprio nel ritenere che un tale schema sia formalizzabile, cioè realizzabile nel rispetto della formalità.

Se si segue il testo, si scopre quale sia il punto chiave: TI dovrebbe essere in grado di associare alla generica sequenza di simboli-insieme “A*(x*)”, la corrispondente espressione insiemistica “A(x*)”. Per esempio, nel caso della proprietà parità del numero x, esprimibile nell’originale AI con: “∃y(x=2·y)”, bisogna associare all’insieme:

(∃*, y*, (*, x*, =*, 2*, ·*, y*,)*)

l’insieme che in notazione ingenua è:

P={x* : ∃y(x*=2*·y)}

Ora, ciò si può sempre fare di volta in volta. Ma noi dobbiamo farlo in tutti i casi mediante un unico schema assiomatico. Sulle prime, sembrerebbe che la cosa sia perfettamente realizzabile: prendiamo una macchina, facciamogli togliere gli asterischi e le virgole della generica sequenza e il gioco è fatto. Poichè TI riesce a riprodurre logicamente il comportamento di una qualsiasi macchina, anche TI sarebbe in grado di fare quest’associazione qualunque sia la sequenza; è appunto quanto affermo nella nota n. 31 del paragrafo in esame. Ma si sta trascurando il fatto che tale macchina dovrebbe trattare come oggetti gli stessi enti che definiscono il suo comportamento! Una tale macchina – da un’altra prospettiva – non comporrebbe frasi di TI ma di una Teoria necessariamente diversa: la rappresentazione di TI in seno allo stesso TI. Una tale rappresentazione non è certo proibita, ma se ne ricava una Teoria radicalmente diversa dall’originale. Ne è prova il semplice fatto che per la Teoria rappresentata le collezioni delle proposizioni e dei teoremi sono insiemi, a differenza dell’originale TI.

Lo dico in un altro modo: TI non può trattare che insiemi. Per stabilire la suddetta associazione generale, TI dovrebbe definire una funzione che associ ai simboli asteriscati (come “∃*”) quelli non asteriscati (come “∃”). Ma in TI ogni funzione (che è anch’essa un insieme) opera tra insiemi. Invece il simbolo “∃” del linguaggio di TI non è un insieme; in nessun caso può esserlo.

Nell’edizione Aracne del libro, questa inesattezza non è presente, malgrado si tratti di una versione più vecchia che è stata assai migliorata ed arricchita dalle successive edizioni Amazon, Bubok, Lulu e Scribd. In una nota del par. II.10 di quest’edizione affermo, infatti, a proposito della corrispondenza insiemistica in esame, che essa non può essere interamente formalizzabile in TI, in quanto <<contempla il Sistema TI “dal di fuori”>>. Il citato esempio della macchina, qualche tempo dopo, mi ha evidentemente distratto.

Non ritengo plausibile che il suddetto schema assiomatico di comprensione possa codificarsi in TI mediante una strategia alternativa, anche se non sono in grado di escluderlo.

Questa rettifica non comporta alcuna modifica ad alcuna conclusione del libro: tale informalizzabilità ribadisce che AI non è fedelmente rappresentabile all’interno del Sistema formale TI. Ma ciò può già dedursi dal fatto che AI è informale. Nel libro si è ammesso, scorrettamente, che in TI è formalizzabile una riproduzione parziale del principio; in ogni caso, è proprio da tale parzialità (che si evince dall’innumerabilità di P(U)) che discende l’informalità dell’originale Teoria AI. In questo articolo si è chiarito che perfino la suddetta riproduzione non totale del principio in TI è irrealizzabile senza l’uso di semantica.

Bisogna inoltre avvisare che neanche l’induzione parziale di PA può essere formalizzata in TI mediante la definizione alternativa descritta nello stesso paragrafo II.14, la quale ricalca in toto la soluzione ora giudicata incodificabile. Per rappresentare fedelmente il Sistema in TI non resta che la soluzione originaria, quella reiterata all’inizio di questo paragrafo.

Anche mediante la rappresentazione alternativa, comunque, si può concludere la formalità di PA, in base alla numerabilità e all’assenza di significato degli assiomi induttivi, come si descrive alla fine del paragrafo II.14. Ricordiamo, infatti, che la formalità per un Sistema richiede l’assenza di significato per i soli enunciati (come lo sono gli assiomi), mentre la regola per generarli (come uno schema assiomatico) può possedere significato. Se in un Sistema formale tale significato è ineliminabile, ne verrà una rappresentazione in TI necessariamente non fedele. Se è eliminabile (come nel caso di PA), la fedeltà può ottenersi con un’opportuna rappresentazione e il Sistema ha gli assiomi effettivamente numerabili (le due proprietà sono infatti equivalenti, par. III.3).

4 Una generalizzazione del Teorema d’incompletezza di Gödel

Malgrado la sua precedenza storica, il primo Teorema d’incompletezza di Gödel si può considerare come la formalizzazione del Metateorema di Church-Turing valido per le macchine. La stretta corrispondenza suggerisce che l’ipotesi di sola effettiva numerabilità per gli assiomi (par. III.4), invece che la più forte decidibilità, sia sufficiente all’applicabilità del Teorema; che è ciò che il libro si limita a suggerire (par. III.6). In verità, la dimostrazione è immediata.

Si consideri un Sistema matematico classico con assiomi effettivamente numerabili. Ricordando l’ipotesi basilare che le uniche regole deduttive della Teoria siano quelle del Calcolo logico classico (che è l’ipotesi fondamentale tacitamente convenuta per ogni Sistema definito come classico), segue facilmente che anche tutti i teoremi sono effettivamente numerabili (par. III.3). Si supponga allora che esso soddisfi a tutte le ipotesi del Teorema d’incompletezza, eccetto alla decidibilità degli assiomi (ovvero all’effettiva assiomatizzabilità). Dal considerarlo, per assurdo, come sintatticamente completo segue direttamente la decidibilità dei suoi assiomi (e in generale di tutte le proposizioni): ogni enunciato che non è un assioma sarà il negato di un teorema (o assioma) e la Teoria saprà riconoscerlo. A questo punto si può applicare il Teorema d’incompletezza nelle sue usuali ipotesi e concludere che il Sistema è incompleto: assurdo.

Benchè le mie ricerche siano state infruttuose, è improbabile che questa elementare proprietà sia sfuggita a chiunque abbia analizzato il tema dell’incompletezza con sufficiente profondità. In ogni caso non ritengo opportuna la decisione di sorvolare su questa generalizzazione (anche se fosse destinata a risultare priva di importanti conseguenze) data la rilevanza dell’argomento. La stessa definizione di effettiva assiomatizzabilità per un Sistema, di origine, per così dire, “storica”, potrebbe essere alleggerita o sostituita da un’altra più debole.

5 Esempi di Aritmetiche formali del secondo ordine

Nell’Aritmetica integrale (AI) il principio di induzione è generalizzato “a qualsiasi proprietà” dei numeri naturali. Se si lascia che sia tale espressione metamatematica del tutto generale a definire l’induzione, AI può ammettere espressioni di qualunque ordine espressivo. Ma normalmente l’induzione completa viene espressa mediante l’assioma:

∀A((A(0) e ∀x((A(x) e S(x,y))→A(y))) → ∀x A(x))

in cui A rappresenta un generico predicato. Si tratta pertanto di una espressione del secondo ordine. Se non viene aggiunto nessun altro assioma, l’espressione è informale e, come abbiamo anche qui rilevato, la rappresentazione in TI del Sistema mostra che i teoremi induttivi sono più che numerabili. Pertanto tale informalità è ineliminabile. Questo intendere così generale (full) dell’espressione “∀A” obbedisce all’interpretazione della cosiddetta Semantica Standard.

Per ripristinare la formalità si possono aggiungere al precedente schema induttivo degli opportuni schemi assiomatici che limitano la variabilità dei predicati[8]. Si possono così ottenere diverse Aritmetiche formali del secondo ordine che hanno suscitato un certo interesse e che nel libro sono state ignorate. Ne faró, qui, il brevissimo accenno che meritavano. La materia è nota come Matematica inversa per il fatto che tali Teorie vengono costruite in modo opposto rispetto al metodo tradizionale: si parte da ciò che si vorrebbe, cioè dal desiderato ambito deduttivo e si cercano i minimi assiomi che lo permettono. Un altro fattore di interesse si deve al fatto che questi Sistemi rappresentano un chiarimento, dalla medesima prospettiva del secondo ordine espressivo, della stessa tradizionale Aritmetica informale.

Per ottenere la formalità, in modo analogo a quanto fatto nel libro per rappresentare l’induzione mediante insiemi (par. II.14), si stabiliscono degli schemi assiomatici di comprensione per far corrispondere alle proprietà gli insiemi dei naturali che le soddisfano. Come si è ricordato alla fine del precedente paragrafo, non è detto che tali schemi debbano essere necessariamente formalizzabili in TI, ovvero con un contenuto semantico eliminabile. Quando succede, il Sistema è fedelmente rappresentabile in TI, ovvero dotato di assiomi effettivamente numerabili (par. III.3).

Questo è il caso di RCA₀ , cui può infatti applicarsi una versione debole del Primo Teorema d’incompletezza. RCA₀ rappresenta la “Matematica computazionale”, ovvero tutto il calcolabile. Il suo criterio deduttivo è di tipo costruttivista: in essa ogni ente esistente è effettivamente individuabile. Tuttavia essa raggiunge questo risultato mantenendo la prospettiva della Logica classica (con il principio del terzo escluso ancora valido, mentre in Logica costruttivista questo viene esplicitamente rifiutato).

La Teoria indicata con ACA₀  rappresenta l’Aritmetica formale del secondo ordine “più vicina” a PA. Si costruisce con uno schema assiomatico di comprensione limitato alle sole formule aritmetiche (che coincidono con le proposizioni del primo ordine) con almeno una variabile libera. Tale schema è quindi identico a quello che abbiamo cercato di formalizzare in TI – senza successo – per rappresentare AI (e PA nella definizione alternativa). Se non esistono alternative per riprodurlo formalmente in TI (cosa che riteniamo assai probabile), allora gli assiomi di ACA₀ non possono essere effettivamente numerabili e pertanto non è possibile applicare il Primo Teorema d’incompletezza.

Solo al secondo ordine, ACA₀ permette di considerare proprietà non predicabili in PA, comunque non calcolabili: si può infatti dimostrare che ACA₀ e PA sono equivalenti dal punto di vista computazionale.

Generalizzando lo schema assiomatico di comprensione a formule anche non aritmetiche, si possono ottenere altri Sistemi formali via via più forti, cioè più vicini ad AI.

6 Paradossi e Teorema di incompletezza

In quest’ultimo paragrafo desidero puntualizzare l’esatta connessione tra alcuni noti paradossi e il Teorema d’incompletezza. Si legge troppo spesso che l’originale dimostrazione di Gödel si basa sul paradosso del mentitore, la versione di Boolos sul paradosso di Richard e quella informatica, di Chaitin, sul paradosso di Berry[9]. Il verbo basare suggerisce una connessione logica di tipo causale che non ha da essere.

Le tecniche dimostrative di riduzione all’assurdo sono senza dubbio le più impiegate nei teoremi più complessi. Ma nel caso di una loro completa codificazione all’interno di una Teoria assiomatica formale, esse perdono ogni carattere peculiare e si trasformano sempre in normali dimostrazioni “dirette” (par. I.10). Lo stesso deve accadere, dunque, per una qualsiasi versione del Teorema di incompletezza che venga formalizzata all’interno della Teoria formale degli insiemi (TI). Questo solo fatto è già eloquente; ma la riduzione all’assurdo ricompare nelle versioni informali del Teorema, cioè nell’applicarlo allo stesso TI e nei metateoremi di Church-Turing e di Chaitin, che impiegano, rispettivamente, il concetto informale di “macchina” e di “programma”. Ma qui l’assurdo, e la conseguente fine della dimostrazione, deriva – come in ogni corretta conclusione per assurdo – dalle ipotesi che si sono fatte; è basata solo su di esse e sull’ammessa logica deduttiva. Il tipo di assurdo che si può ottenere è invece una questione esclusivamente tecnica; e in quanto tale, la circostanza che assomigli a un classico paradosso, dal punto di vista logico è una sorta di questione di probabilità. Ne è indicativa la stessa varietà dei paradossi ottenibili con le diverse metadimostrazioni. Per inciso, l’assurdo che si ottiene nel Metateorema di Church-Turing è una semplice contraddizione circolare e non assomiglia a nessun paradosso classico (par. III.4). D’altra parte è sufficiente ricordare che da un assurdo si può derivare realmente tutto, in particolare anche ogni altro tipo di assurdo.

È probabile che il carattere sconvolgente (e spesso considerato, a torto, paradossale o al limite del paradossale) del Teorema di incompletezza giochi un ruolo cruciale in questo equivoco. In verità l’affinità con il paradosso di Richard si può osservare in ogni teorema che impiega l’argomento diagonale, come nella stessa dimostrazione di Cantor dell’innumerabilità dei numeri reali: la prima in assoluto di questo tipo. Eppure nessuno si sogna di affermare che tale teorema si basa sul paradosso di Richard, anche perché in questo caso è stato il paradosso ad ispirarsi al teorema e non viceversa.

Ecco dunque di che cosa si dovrebbe correttamente parlare circa la relazione tra certi teoremi e certi paradossi: di ispirazione, di suggerimento, senza alcun dubbio in grado di aiutare i matematici e i logici nella ricerca di nuove dimostrazioni e metadimostrazioni. Ma non di legame causale.

La descritta confusione è infelice anche e soprattutto perchè distoglie dal significato intrinseco degli stessi paradossi semantici. Se c’è un certo paradosso, questo paradosso ci dice già qualcosa: può essere letto come una metadimostrazione per assurdo; mentre la sua affinità o fonte d’ispirazione per un teorema è un risvolto considerevole ma circostanziale. Il paradosso del mentitore ci informa che nessuna Teoria coerente può definire un concetto di verità universale (Metateorema di Tarski, par. III.6). Il paradosso di Berry può essere letto come una prova del fatto che un numero finito di espressioni semantiche può denotare un numero infinito di oggetti; quello di Richard come una prova del fatto che le definizioni semantiche non sono numerabili (par. II.13). Questi due ultimi fatti che scopro (per la prima volta?) nel libro, sono stati finora ignorati o almeno profondamente trascurati dalla Logica ufficiale. E il fatto che si tratti di conclusioni puramente metamatematiche, cioè irriducibilmente semantiche, non è forse casuale ma in linea con quanto commentato nel secondo paragrafo.

7 Referenze