Godel #3 - Aritmetizzazione della metamatematica

Il primo passaggio fondamentale per preparare la strada ai successivi ragionamenti è capire la codificazione aritmetica che Godel fa del mondo che vuole analizzare.
Questo primo gradino può sembrare solo un passaggio propedeutico ma costituisce a quanto posso capire un vero colpo di genio: Godel ha intenzione di dimostrare matematicamente cosa si può dimostrare o non dimostrare in matematica; fa il passaggio ad un livello superiore di analisi, non sta più facendo matematica ma metamatematica, un po' come quei personaggi pirandelliani che all'interno della commedia parlano della stessa commedia che stanno interpretando e fanno così "metateatro"; per fare questo passaggio ad un livello superiore Godel ha bisogno di creare un vero e proprio sistema, un edificio rigoroso e computabile. Vuole analizzare la matematica dei numeri naturali, e per farlo si avvale degli strumenti della stessa matematica dei naturali.
Visto che per parlare di matematica si usano dei simboli, la prima cosa di cui ha bisogno è tradurre in numeri questi simboli. E' necessario prendere le mosse da un sistema di rappresentazione dell'aritmetica estremamente rigoroso ma allo stesso tempo semplice e con pochi segni; questo è il calcolo proposizionale. Si tratta di un sistema di assiomi e regole di trasformazione in cui è possibile esprimere enunciati e dedurre le loro conseguenze logiche in modo del tutto formale e meccanico. Il calcolo proposizionale si basa su pochi simboli e regole ma è capace di esprimere tutti i concetti della matematica dei numeri naturali.
I simboli sono molto basilari e semplici e si suddividono in costanti e variabili.
Le costanti sono i simboli per scrivere i numeri e i segni necessari per mettere in relazione questi e le variabili ("~" che significa "non", "V" che sta per "oppure", "É" che signica "implica", o "se..., allora...", "." che significa "e", "$" che significa "esiste", "=" che sta per "è uguale a", e poi le parentesi tonde e altre poche cose). I numeri si scrivono con "0" per zero e con "S" dopo lo zero per ogni suo successore (quindi il numero 3 si scrive "SSS0", ossia il successore del successore del successore di zero). In questo modo si riducono moltissimo i simboli da tradurre e il lavoro di Godel è in parte più semplice. Poi ci sono le variabili, ossia simboli che possono rappresentare numeri, proposizioni o predicati. esistono le variabili numeriche (che rappresentano numeri, come SSS0), le variabili proposizionali (che rappresentano proposizioni tipo 0=0), le variabili predicative (che rappresentano predicati come "è maggiore di" o "è un numero primo"). Un esempio di formula o proposizione scritta con questo linguaggio potrebbe essere "($x)(x=S0)", che significa "esiste un x tale che x è il successore immediato di zero", quindi in pratica esiste il numero 1.
Le regole di trasformazione sono necessarie per passare dagli assiomi ad altre formule corrette e coerenti del sistema, quindi per fare tutti i "passaggi" delle dimostrazioni. Queste regole sono ad esempio la "regola di sostituzione" (è possibile sostituire delle formule alle variabili conservando la correttezza della proposizione) o la "regola di separazione" o "modus ponens" (che dice che se abbiamo X e X É Y, allora possiamo dedurre Y)

Quindi un teorema, ossia una dimostrazione all'interno del sistema, è qualsiasi passaggio che rispetta le regole interne del sistema e che quindi arriva a una formula partendo dagli assiomi di base e passando solo attraverso le regole di trasformazione correttamente applicate. Un po' come abbiamo imparato tutti a scuola, ed in modo completamente meccanico e tipografico (nel senso che i simboli possono essere anche del tutto scissi dal significato che rappresentano, e le regole sono solo dei meccanismi ciechi e astratti, applicabili in maniera automatica).
Godel come dicevo sopra ha bisogno di trasformare ogni simbolo in numero, ed è importante che lo faccia in modo che ad un munero corrisponda un simbolo e viceversa, e che ad una formula corrisponda un numero e viceversa, un rapporto biunivoco tra formule del sistema e numeri senza possibilità di errori o confusioni.
Potrebbe scegliere vari modi, ma opta per uno che a mio parere è elegantissimo. Parte dal facile e traduce le costanti con i primi numeri naturali:

Costante	Numero di Godel	Significato
~	1	non
V	2	oppure
É	3	implica
$	4	esiste
=	5	uguale
0	6	zero
S	7	immediato successore
(	8	aperta parentesi
)	9	chiusa parentesi
,	10	segno di separazione

Poi traduce le variabili numeriche con i numeri primi maggiori di 10.

Variabile numerica	Numero di Godel	Esempio
x	11	S0
y	13	SSSS0
z	17	0

Ovviamente altre variabili seguono come numerazione i numeri primi superiori a 17.

Alle variabili proposizionali attribuisce i numeri primi maggiori di 10 elevati al quadrato (scriverò 11^2 per intendere 11 elevato alla seconda, non conosco altri modi).

Variabile proposizionale	Numero di Godel	Esempio
t	11^2	0=0
r	13^2	($x)(x=S0)

Per le variabili predicative Godel sceglie i numeri primi maggiori di 10 elevati al cubo.

Variabile predicative	Numero di Godel	Esempio
A	11^3	numero primo
B	13^3	maggiore di

Con questo meccanismo la formuletta di prima ($x)(x=S0) diventa, sostituendo quanto nelle tabelle, 8, 4, 11, 9, 8, 11, 5, 7, 13, 9 (ho ricontrollato, è così). Questi però sono tanti numeri, è troppo complicato, pensa Godel. Quindi elabora un semplice modo per tirarne fuori uno solo: i primi numeri primi in ordine di grandezza elevati ai numeri trovati sopra e poi moltiplicati tra loro:2^8 x 3^4 x 5^11 x 7^9 x 11^8 x 13^11 x 17^5 x 19^7 x 23^13 x 29^9
Questo è il numero di Godel della formula. E' davvero grande ma, a parte la difficoltà di scriverlo per esteso, è perfettamente calcolabile con un algoritmo semplicissimo. Ai tempi di Godel il computer non esisteva nemmeno in teoria, Alan Turing solo pochi anni dopo teorizzò la sua macchina per calcolare, ma oggi il concetto di facile computabilità tramite un algoritmo è immediato da comprendere, ed è quindi ancora più apprezzabile la semplicità del metodo di Godel.Il concetto fondamentale è che esiste una corrispondenza biunivoca tra ogni formula e il suo numero di Godel, data un'espressione numerica esiste ed è semplicemente calcolabile il suo numero di Godel, e dato un numero di Godel è semplice trovare la formula a cui corrisponde.
E' chiaro che non tutti i numeri sono numeri di Godel, per essere tale il numero deve essere scomponibile in fattori primi che hanno un significato in base alle tabelle scritte sopra, altrimenti niente da fare.Esempio facile: prendiamo il numero 243.000.000 (duecentoquarantatre milioni). Come ogni altro numero (vedi il teorema fondamentale dell'aritmetica, affrontato anche in un altro post) ha una scomposizioni in fattori primi che è unica, e che in questo caso è 64 x 243 x 15625 = 2^6 x 3^5 x 5^6, ossia i primi tre numeri primi (2, 3, 5) elevati a 6, 5, 6, quindi controllando le tabelle sopra si ha che 243.000.000 è il numero di Godel dell'espressione "0=0". Non facilissimo ma semplicissimo.Un'altra cosa importante: consideriamo la dimostrazione di un teorema all'interno del calcolo proposizionale.
Ad esempio:
1)                             ($x)(x=Sy)
2)                             ($x)(x=S0)

ossia, dato che esiste un x tale che x è il successore immediato di y, se sostituiamo 0 a y (applicando la regola di sostituzione), ne consegue che esiste un x successore immediato di 0 (il famoso numero 1 di prima).
Supponiamo che il numero di Godel della prima parte sia A e supponiamo che il numero di Godel della seconda sia B; ebbene, il numero di Godel della intera dimostrazione è i primi numeri primi in ordine di grandezza elevati ai numeri di Godel delle singole espressioni e poi moltiplicati tra loro, ossia:
2^A x 3^B
questo è il numero di Godel dell'intera dimostrazione. E' enorme ma semplice da calcolare.
Ogni simbolo, ogni espressione numerica, ogni formula qualunque sia la sua complessità, ogni dimostrazione lunga quanto ti pare ha il suo specifico numero di Godel, e dato un qualsiasi numero di Godel è possibile con semplici passaggi algoritmici capire qual'è l'espressione matematica che rappresenta.
Questo metodo lo trovo fantastico.
E' il fulcro dell'intera dimostrazione, sul quale poi si basa l'intero ragionamento. Dal poco che ne so Kurt Godel è stato il primo ad ideare un meccanismo del genere, è questo che gli ha permesso il salto del livello interpretativo, dalla matematica alla metamatematica.
Io vado a nanna. Spero di non sognare numeri primi che vogliono godelizzarmi.
Alla prossima.