Introduzione all'aritmetica di Peano.

 

Se intendiamo utilizzare la logica dei predicati per formalizzare affermazioni e dimostrazioni relative all'aritmetica e' facile capire che occorre utilizzare un linguaggio specifico, in particolare il linguaggio che avra' il seguente insieme di simboli di funzione:

{00, s1, +2, *2}

Per poter rappresentare tutti i numeri naturali e' sufficiente infatti avere una costante che rappresenti lo zero, ed una funzione unaria che rappresenti il successore di un numero. Per poter fare dei conti introduciamo anche i simboli di funzione per la somma e la moltiplicazione. Altre funzioni aritmetiche si potranno definire a partire da quelle che abbiamo.
Ovviamente avremo come insieme dei simboli di predicato l'uguaglianza:

{ = }

il nostro sara' quindi un linguaggio con uguaglianza.

Si potrebbe quindi pensare di poter dimostrare nella logica dei predicati che la somma di uno e due e' uguale a tre, cioe'

  |- s(0)+s(s(0)) = s(s(s(0)))

Ma cio' non e' possibile, poiche' il teorema di correttezza di dice che se possiamo dimostrare s(0)+s(s(0)) = s(s(s(0))), allora sarebbe anche il caso che

  |= s(0)+s(s(0)) = s(s(s(0)))

ma cosi' non e', poiche' significherebbe che s(0)+s(s(0)) = s(s(s(0))) sarebbe vero in ogni struttura. Infatti, prendiamo per esempio la struttura che abbia come supporto l'insieme {T,F} ed in cui il simbolo di costante 0 corrisponda a F, il simbolo di funzione s corrisponda alla funzione identita' ed il simbolo + alla funzione binaria che, per ogni coppia di elementi in {T,F} restituisce sempre T. Bene, in tale struttura abbiamo che l'interpretazione di s(0)+s(s(0)) = s(s(s(0))) e' 0, cioe'

  [[ s(0)+s(s(0)) = s(s(s(0))) ]] = 0

(vedi la definizione di interpretazione di formule ben formate su una struttura a pag 31 di [SM]).
Dov'e' il problema? Il problema sta nel fatto che noi abbiamo introdotto i nostri simboli funzionali pensando a loro come lo zero, la funzione successore ecc., ma non c'e' nulla che nella logica dei predicati imponga a questi simboli di "comportarsi" come intendiamo noi.
Per far questo occorre fare delle ipotesi, porre cioe' dei vincoli al loro comportamento. Tali ipotesi sono esattamente l'insieme di formule PA indicate nel testo [AAb].
Ed infatti, se vogliamo dimostrare una formula Q relativa all'aritmetica, dobbiamo dimostrare

PA |- Q

In questo modo dimostriamo che

PA |= Q

cioe' che Q e' conseguenza logica di PA, cioe' l'interpretazione di Q e' vera ([[Q]] =1) in tutte le strutture che sono modelli di PA, in cui cioe' le formule di PA sono vere (se Q non fosse una formula chiusa, occorrerebbe dire un po' meglio quanto scritto).

Si potrebbe essere indotti a pensare che l'unica struttura in cui le formule di PA sono vere sia quella che ha i numeri naturali come supporto, lo zero come interpretazione di 0, la funzione successore come interpretazione di s, la funzione somma per + e il prodotto per * (tale struttura e' chiamata "modello standard dell'aritmetica".
In realta' non e' cosi'. Uno dei teoremi di Goedel ci mostrera' che, anche aggiungendo altre formule a quelle di PA, e' impossibile fare in modo che PA abbia solo il modello standard come possibile modello.