I teoremi di incompletezza di Gödel

Kurt Gödel

I teoremi di incompletezza

Introduzione

In questa nota saranno descritti i due teoremi di incompletezza di Gödel

Innanzitutto introduciamo alcuni concetti di base, senza dei quali sarebbe impossibile enunciare e spiegare i due teoremi.

Logica matematica

La logica matematica è la scienza che si occupa di studiare il modo di codificare i calcoli e le dimostrazioni  effettuate nell'ambito di una logica formale

Ma cos'è una logica formale? è un insieme di

• un alfabeto utilizzato
• una grammatica che specifica quali sequenze sono costituiscono "formule" del sistema
• un insieme di "assiomi", ossia, intuitivamente, "formule" che nel sistema si assumono vere
• un insieme di regole di inferenza, ognuna delle quali associa a N formule del sistema (premesse) ad una nuova formula (conseguenza)

In  un  sistema formale si definisce l'insieme dei teoremi come l'insieme degli assiomi unito a tutte le formule che si possono ottenere dall'applicazione delle regole di inferenze agli assiomi stessi e alle altre formule ottenute, ricorsivamente.

 

Logica proposizionale

E' un linguaggio formale che consente di esprimere proposizioni booleane elementari o composte, basato sui connettivi logici (and, or, not, implica, se e solo se) ed un  insieme di simboli.

Possiamo quindi dire che è una logica formale avente, per alfabeto utilizzato: le lettere dell'alfabeto, unito ai connettori logici ¬ (NOT),  (AND),  (OR), → (implicazione), ↔ (doppia implicazione), e le parentesi tonde, usate per evitare ambiguità sull'applicazione dei connettori.
Per insieme regole di inferenza abbiamo:

1. una proposizione è una formula ben formata (fbf)
2. se A è una fbf allora anche ￢A è una fbf
3. se A e B sono fbf allora anche (A ⋁ B) , (A⋀B), (A↔️B), (A➡️B) sono fbf
4. tutto il resto non è una fbf

Alle fbf della logica proposizionale è possibile associare una semantica mediante una funzione di valutazione.

Si definisce funzione di valutazione una funzione che va da L delle fbf  nell'insieme (vero, falso)

v: L ➡️ { vero, falso }

tale che:

v( ￢ x ) =V   se v(x) = F

v( ￢ x ) =F   se v(x) = V

v ( x ⋀ y ) = V se e solo se v(x) = V e v(Y)=V

v ( x ⋁ y ) = V se e solo se v(x) = V oppure  v(Y)=V

v ( x ➡️ y ) = V se e solo se v(x) = F oppure  v(Y)=V

v ( x ↔️ y ) = V se e solo se v(x) = v(Y)

che attribuiscono ai connettori logici il significato consueto.

Per attribuire il valore ad una fbf in base alla funzione di valutazione, si attribuisce alle proposizioni elementari un valore di vero/falso e poi a partire da quelle si calcolano, risalendo le parentesi a partire dalle più interne, tutte le altre.

Un limite della logica proposizionale è che se si vuole esprimere un concetto di (ogni A(i) è vero per i che va da 1 a n) lo si può fare solo esprimendo

A1 ⋀ A2 ⋀ A3 ⋀ .... An

ma se vogliamo esprimere lo stesso concetto per un numero imprecisato o infinito di termini non possiamo farlo, in sostanza mancano i "quantificatori", inoltre non abbiamo nella logica proposizionale la possibilità di riferirci a predicati o funzioni.

Linguaggio del primo ordine

Un linguaggio del primo ordine è una logica formale in cui l'alfabeto è composto da:

• simboli per variabili: x1, x2,..
• simboli per costanti: a1, a2,..
• simboli per predicati o relazioni, a ciascuno dei quali è associato il suo numero di argomenti: P¹,Q¹,P²,Q²,...
• simboli per funzioni, a ciascuna delle quali è associato il suo numero di argomenti:  f¹,g¹,f²,g²,...
• simboli ausiliari; parentesi tonde e virgola
• simboli per connettivi logici (come per la logica proposizionale)
• simboli per quantificatori: ∀ (quantificatore universale) e  ∃ (quantificatore esistenziale)

per le regole di inferenza si rimanda a wikipedia, "linguaggi del primo ordine", ma in sostanza sono le regole comuni con cui scriviamo in matematica le formule, tuttavia è bene osservare che:

• costanti e variabili si riferiscono ad un "universo del discorso" U
• le funzioni f, g,.. hanno per dominio Uⁿ e per codominio Uⁿ
• i predicati o relazioni sono sottoinsiemi di Uⁿ
• i quantificatori si riferiscono ad elementi di U

In sostanza con un linguaggio del primo ordine possiamo esprimere predicati su U, relazioni di implicazione di predicati su U. In base all'ultimo vincolo, non possiamo utilizzare i quantificatori su sottoinsiemi di U (variabili predicative). Si dimostra che una teoria del primo ordine è sufficiente a "contenere" l'aritmetica e la teoria degli insiemi.

Un esempio di linguaggio del primo ordine è l'aritmetica di peano

Linguaggi del secondo ordine

Se ammettiamo la possibilità di menzionare, nel linguaggio, anche variabili e costanti che rappresentino funzioni e predicati, otteniamo un linguaggio del secondo ordine. In un linguaggio del secondo ordine posso quindi esprimere concetti di esistenza o di universalità sui predicati oltre che sugli elementi di  U.

Per fare un esempio, si può esprimere che

∀R∀x(R(x) ∨ ¬R(x))

dove R è un predicato generico ed x è un elemento di U. Questa espressione non è ammessa in un linguaggio del primo ordine, poiché in tale linguaggio questo non è ammesso.

Consideriamo il principio del buon ordinamento dei numeri naturali, secondo il quale ogni sottoinsieme non vuoto dell'insieme dei numeri naturali ammette un minimo. Per esprimere questo principio occorre avere un quantificatore esistenziale sugli insiemi, e questo è ammesso in un linguaggio del secondo ordine, ma non del primo.

Se consideriamo il principio di induzione, che afferma che per una generica proprietà se P(0) è vera e se P(n) => P(n+1) allora P è vera per tutto N, è necessario utilizzare un quantificatore universale sui predicati, è questo è possibile solo in una teoria del secondo ordine.

Nel linguaggio di secondo ordine si possono esprimere e generalizzare relazioni  (proprietà) su U ma non relazioni tra relazioni, ossia le relazioni hanno sempre per dominio U e non l'insieme delle relazioni stesse. Questo richiederebbe un linguaggio di ordine superiore.

Tra i predicati è possibile esprimere delle relazioni logiche con connettori  propri del linguaggio del secondo ordine, e sono simili a quelli del primo ordine, ma si indicano solitamente con termini diversi per non generare confusione, e sono:

• not per il not di un predicato
• vel per l'or logico
• et per l'and logico
• seq per l'implicazione logica
• eeq per la doppia implicazione
• om per il quantificatore universale
• ex per il quantificatore esistenziale

Teoria, Metateoria

Si può considerare, in un linguaggio di ordine superiore al primo, "teoria" il sottoinsieme relativo alla logica proposizionale, e metateoria le proposizioni che si riferiscono ai predicati stessi. 

Intuitivamente, per "parlare" della teoria U abbiamo bisogno di una metateoria M, poiché U non contiene in sé i nomi e le proprie regole di inferenza intese in senso astratto.

Per parlare di come descriviamo la teoria, abbiamo bisogno di una meta-metateoria  e via dicendo.

Completezza di una teoria

In una logica del primo ordine tutto quel che è vero è dimostrabile, e questa proprietà si definisce di completezza. In una logica del secondo ordine o superiore, si acquista in espressività ma si perde la proprietà di completezza.

Detto più formalmente, una teoria è completa se per una qualsiasi formula ben formata φ (fbf) è possibile dimostrare formalmente φ se  φ è vera o dimostrare formalmente  ￢φ se φ è falsa.

Si può alternativamente dire che una una teoria è completa se non esistono formule indecidibili, ossia di cui non è possibile fornire una dimostrazione od una confutazione.

Coerenza di una teoria

Una teoria si dice coerente se non esiste alcuna formula ben formata φ (fbf)  di cui è possibile dimostrare formalmente sia  φ che   ￢φ.

La coerenza è un concetto importante poiché si può dimostrare che in una teoria incoerente si può dimostrare qualsiasi cosa, dunque perde di significato.

w-Coerenza di una teoria

Una teoria si dice w-coerente se non esiste nessuna formula ben formata φ tale che si possa dimostrare al contempo: ∀xφ(x)   e   ∃x¬φ(x).  

La w-coerenza è un concetto più forte della semplice coerenza.

Primo teorema di incompletezza di Goedel

In una teoria T sufficientemente espressiva da contenere l'aritmetica e coerente, esiste almeno una formula φ  che non può essere né dimostrata né confutata.

Dimostrazione 

La dimostrazione si basa sulla possibilità di definire una formula logica che neghi la propria dimostrabilità. A tal fine si codifica una formula "autoreferenziale", ossia che parla di se stessa.

Si associa ad ogni simbolo dell'alfabeto della teoria un numero naturale. Quindi ad una formula, che è data da un insieme di simboli, possiamo associare un "numero di goedel", pari a

p₁^s1 p₂^s2....p_n^sn 

ove p₁,..p_n sono i primi n numeri primi , e s1..sn sono i numeri associati ai simboli della formula considerata.

In sostanza abbiamo trasformato una generica formula della teoria in un numero naturale.

Chiamiamo G(φ) il Godeliano della formula ben formata φ.

Visto che per ipotesi T è abbastanza espressiva da contenere l'aritmetica, può trattare le formule al pari dei numeri stessi.

Gli assiomi di T devono essere almeno sufficienti a dimostrare alcuni enunciati fondamentali:

i) ogni numero naturale ha un numero di Goedel (che si ottiene ottenendo reiteratamente la funzione successore all'elemento 0)

ii) dato un qualsiasi numero di Goedel di una formula φ(x), con variabile libera x ed un qualsiasi numero naturale m, vi è un numero di Goedel associato alla formula φ(G(m)) ottenuto sostituendo le occorrenze di x in φ(x) con il numero di Goedel associato ad m.

Dette D1,..Dn le regole di deduzione della teoria, supponiamo che D1 consenta di passare dalle formule 1 e a2 di T ad una nuova formula a3, si avrà che il numero di Goedel della sequenza a1,a2, che chiamiamo n, ed il numero m associato alla formula a3, saranno in relazione R1 tra loro, ossia (n,m) ∈ R1, sarà pertanto meccanicamente verificare se una dimostrazione è corretta, verificando i vari passaggi sei i corrispondenti numeri naturali sono in relazione tra loro.

Definiamo H l'insieme dei numeri di Goedel di tutti gli enunciati dimostrabili. 

Per quanto detto H è chiuso relativamente alle relazioni binarie R1..Rn associate alle regole di deduzione D1..Dn, ossia se n è nell'insieme H e (n,m) è elemento di R(i) allora anche m appartiene ad H, ossia è dimostrabile.

Attraverso una serie di passi, Goedel costruisce un predicato metamatematico 

    Dim(y,x) 

che rappresenta la relazione  "y è il godeliano di una dimostrazione della formula di godeliano x"

ed una formula    Teor(x) della forma ∃y Dim(y,x)

si noti che Teor è una formula come tutte le altre

In sostanza Teor(x) è vera per tutti gli x goedeliani di qualche teorema.

Si possono dimostrare tre proprietà di Teor, ossia

1) se φ è dimostrabile allora  Teor(G(φ) è vera

2) se Teor( G(φ ⇒  θ) ) allora  Teor ( G(φ)  ) ⇒ Teor ( G ( θ ) ) 

3) se Teor( G(φ ) ) allora Teor ( G(  Teor ( G(φ)  ) )  )

Si considera la funzione sost(x, y) dove y è il godeliano di una formula con variabile libera  ed x un numero associa il risultato della sostituzione nella formula y di x ovunque appare la variabile libera.

sost aritmetizza la sostituzione di un numerale al posto di una variabile libera in una formula.

Si considera la funzione not(x) che al godeliano di una formula x associa il godeliano della negazione di quella formula.

Si considera la composizione di sost e not come 

sostnot(x)  = sost ( x, not(x) )

che ad una formula che ha una variabile libera, il cui godeliano è  x, fornisce il godeliano della formula che si ottiene sostituendo nella variabile libera il godeliano di x nella negazione della formula il cui godeliano è x. 

Ossia sostnot(x) nega la formula il cui godeliano è x, e sostituisce alla variabile libera in essa presente il godeliano di x stesso.

Queste funzioni sono rappresentabili numericamente secondo lo schema fornito da Goedel.

Fatte tali premesse, consideriamo il numero n godeliano della formula 

    Teor(sostnot(x))  (2)

Questa formula vuol dire data una formula di godeliano x avente una variabile libera, "sostnot(x) è dimostrabile"

Se sostituiamo il numerale di n alla variabile x nella negazione di questa formula otteniamo

 ￢Teor(sostnot(n))  (3)

il godeliano di questa formula, per le premesse fatte, è proprio sostnot(n)

Infatti sostituendo si ha:

sostnot(n) =  (dobbiamo negare la formula il cui godeliano è n (ossia Teor(sostnot(x)) e sostituire nella sua variabile libera il numerale n) =  G(￢Teor(sostnot(n)) )

Questa formula concettualmente vuol dire "io non sono dimostrabile" infatti Teor(x) vuol dire che esiste una dimostrazione y di x quindi ￢Teor vuol dire "non esiste una dimostrazione", di sostnot(n).

Vediamo cosa succede allora se per esempio (3) ￢Teor(sostnot(n)) sia dimostrabile e sia m il godeliano della dimostrazione.

Allora  sarebbe dimostrabile Dim(m, sostnot(n)),

pertanto ∃y Dim(y, sostnot(n))

quindi sarebbe dimostrabile Teor(sostnot(n)), che è la negazione della (3), quindi avremmo un'incoerenza.

Supponiamo invece che (2) Teor(sostnot(n)) sia dimostrabile. 

Se lo fosse esisterebbe m tale che Dim(m, sostnot(n))

Avendo già dimostrato che (3) non è dimostrabile allora non esiste y tale  Dim(y, sostnot(n))

quindi neanche m è tale che Dim(m, sostnot(n)), ossia si avrebbe ￢Dim(m, sostnot(n))

che contraddice l'assunto.

        

Secondo teorema di incompletezza di Goedel

In una teoria T sufficientemente espressiva da contenere l'aritmetica , non è possibile provare la coerenza di T all'interno di T.

Considerazioni

Il primo teorema di Goedel stabilisce che in una teoria sufficientemente espressiva, ci sono sempre teoremi che non possono essere dimostrati. Si potrebbe aggiungere degli assiomi per renderli veri, ma si otterrebbe una nuova teoria con gli stessi limiti della precedente, creando spazio per nuovi teoremi indimostrabili e cosi via.

La mia perplessità sulla dimostrazione del primo teorema non è di tipo prettamente matematico, ma sull'interpretazione del risultato.

La dimostrazione consiste principalmente nel costruire una formula, ossia Teor(sostnot(n)) autoreferenziale, che afferma di non essere dimostrabile.

Tuttavia nel farlo assimila una dimostrazione con la sua rappresentazione "tipografica" ben precisa.

Una prima perplessità sta proprio in questo, che potrebbe apparire un limite, tuttavia anche ammettendo che ci siano altri teoremi, tipograficamente diversi, attestanti lo stesso concetto, potrebbero essere usati in una catena di dimostrazioni per ottenere il teorema "indimostrabile", che diverrebbe pertanto "dimostrabile". Pertanto la scelta "tipografica" della dimostrazione, ossia i caratteri usati o l'ordine o persino una modalità di dimostrazione diversa non serve ad aggirare il vincolo dato dalla formula Teor.

bibliografia

http://www.recensionifilosofiche.info/2008/02/lolli-gabriele-sotto-il-segno-di-godel.html

https://docplayer.it/2837590-Il-primo-teorema-di-incompletezza-di-godel.html

https://www.treccani.it/enciclopedia/la-seconda-rivoluzione-scientifica-matematica-e-logica-i-teoremi-di-incompletezza-di-godel_%28Storia-della-Scienza%29/

http://fc.lazio.cgil.it/FOV1-0004C55E/S0417867B.66/Francesco%20Berto%20-%20Tutti%20pazzi%20per%20G%C3%B6del!.pdf

https://plato.stanford.edu/entries/goedel/#FirIncThe

https://it.wikibooks.org/wiki/Logica_matematica/Incompletezza/Teoremi_di_incompletezza_di_G%C3%B6del