backup del Post

Aritmetica di Robinson

Qui sul Post ho già raccontato dei teoremi di incompletezza di Gödel, e ho persino postato una dimostrazione. (Non preoccupatevi se non ve la ricordate: riesco a seguirla, ma nemmeno io mi ricordo mai come funziona). Un punto fondamentale del teorema è che possiamo costruire delle proposizioni indecidibili se abbiamo un sistema formale con cui è possibile fare dell’aritmetica. Dopo la bomba iniziale gödeliana, i matematici hanno iniziato come di loro abitudine a vedere se era proprio necessario tutto l’armamentario dell’aritmetica o si poteva evitare qualcosa. Che ne è uscito?

Beh, si è scoperto che non serve proprio tutta l’aritmetica di base, e si può togliere qualcosina, anche se non molto. L’aritmetica può essere definita con gli assiomi di Peano: non so se ve ne ricordate, però ho già parlato anche di essi. Negli assiomi di Peano abbiamo che esiste un numero che si chiama 0 e una funzione S (“successore”) che crea nuovi numeri a partire da quelli già esistenti; sappiamo inoltre che numeri diversi hanno successori diversi e che 0 non è il successore di nessun altro numero. Infine c’è la parte più rognosa, quella dell’induzione matematica: se un sottoinsieme dei naturali contiene 0 e il successore di ciascun numero contenuto nell’insieme, allora contiene tutti i numeri naturali. Da qui si prosegue definendo la somma e il prodotto (per ricorsione, cioè usando somme e prodotti con numeri “più piccoli”)

Raphael Robinson (che mi hanno fatto notare che non è quello dell’analisi non standard che ha creato gli infinitesimi) ci pensò un po’ su e nel 1950 scoprì che l’induzione matematica non è necessaria per finire sotto le grinfie dei teoremi di Gödel, ma ci si può accontentare di qualcosa di meno. Definì così quella che ora chiamiamo Aritmetica di Robinson e denotiamo di solito con Q. In formule abbiamo questi assiomi (più tutta una serie di assiomi per così dire “di base”, come dire che esiste un simbolo 0 e così via):

Q1: ∀ x (S(x) ≠ 0)
Q2: ∀ x ∀ y (S(x) = S(y)) → (x = y))
Q3: ∀ x ((x ≠ 0) → (∃ y (x = S(y))))
Q4: ∀ x (x+0 = x)
Q5: ∀ x ∀ y (x+S(y) = S(x+y))
Q6: ∀ x (x*0 = 0)
Q7: ∀ x ∀ y (x*S(y) = (x*y)+x))

L’unica piccola differenza con l’aritmetica di Peano è che lo schema di assiomi che definisce l’induzione è sostituito dall’assioma Q3, che afferma che ciascun numero diverso da zero è successore di un altro numero, affermazione che con gli assiomi di Peano è un teorema (partendo da zero otteniamo con l’induzione tutti i numeri…) Questa minima differenza ha però grandi effetti: per dire, un’affermazione a prima vista banale come il dire che nessun numero è successore di sé stesso un’asserzione indecidibile nel sistema Q. Come mostrarlo? Semplice: inventandoci un modello apposito di Q! Ora lo spiego con qualche parola in più, non preoccupatevi…

Per prima cosa, ricordo che gli assiomi non hanno nulla a che fare con la realtà. Quello che succede è che abbiamo tra le nostre mani qualcosa, per esempio i numeri naturali con le regole dell’aritmetica, e verifichiamo che essi rispettino le regole formali date dagli assiomi: in questo caso possiamo dire che quello che abbiamo tra le mani è un modello di quella teoria assiomatica. Detto in altro modo, i numeri naturali con le regole dell’aritmetica sono un modello per mettere in pratica sia gli assiomi di Peano che gli assiomi di Robinson; chiamiamo quel modello “standard” perché ce l’abbiamo sempre tra i piedi. Ma esistono anche altri modelli, proprio come in geometria si può dare un significato diverso a punti, rette e piani e trovare un modello per cui non valga il quinto postulato di Euclide.

Prendiamo ora i numeri naturali più un “nuovo numero” Ω. I numeri naturali hanno le solite regole per somma e prodotto tra di loro; per quanto riguarda Ω abbiamo che S(Ω)=Ω, che n+Ω = Ω+n = Ω per ogni n, e n*Ω = Ω*n = Ω per ogni n diverso da 0, altrimenti il prodotto è 0. Potete vedere facilmente che gli assiomi da Q1 a Q7 sono soddisfatti: abbiamo insomma costruito un modello che sta in piedi per l’aritmetica di Robinson. Però l’affermazione “nessun numero è successore di sé stesso” è evidentemente falsa, visto che il successore di Ω è Ω stesso. D’altra parte con i numeri naturali (che – ribadisco – sono un altro modello di aritmetica di Robinson) quell’affermazione è vera; pertanto nell’aritmetica di Robinson quell’affermazione è indecidibile. Ma c’è di peggio! Tra le affermazioni indecidibili ci sono “banalità” tipo la associatività e commutatitivà dell’addizione e distributività della moltiplicazione rispetto all’addizione. Insomma, con l’aritmetica di Robinson, a parte questi scherzetti, si può fare ben poco.

Morale di tutto questo? Ce ne sono almeno due. La prima è che abbiamo una dimostrazione molto semplice del primo teorema di incompletezza di Gödel: e dite niente! La seconda è invece un po’ più sottile, e ne ho già accennato qui sopra. Noi usiamo tranquillamente i numeri naturali, e siamo intimamente convinti che non possano essere che così: non sono forse “naturali”? Invece non è proprio così, come abbiamo visto. Per meglio dire, i numeri naturali sono sì naturali, ma bisogna essere molto attenti a come li si definisce, cioè a definire il modello sottostante. Peggio ancora, il modello dei numeri naturali sembra proprio richiedere necessariamente l’infinito preso tutto assieme; Robinson ha provato a mettere un infinito potenziale dove i numeri sono sì infiniti, ma li controlliamo a uno a uno, e il risultato è stato questo qua. (Intendiamoci: dal suo punto di vista quello è stato un risultato positivo!). Lo so, io di solito dico che la matematica è facile: sono convinto che si possa facilmente fare tanta matematica, ma quello che sta dietro può essere davvero complicato… come del resto tutti gli altri campi del sapere.