Aritmetica di Peano

L'aritmetica di Peano, denotata anche con l'acronimo PA (Peano Arithmetic) in logica matematica è una teoria del primo ordine che ha come assiomi propri una versione degli assiomi di Peano espressi nel linguaggio del primo ordine.

Definizione

Il linguaggio di PA è il linguaggio dell'aritmetica del primo ordine, ovvero è costituito dai seguenti simboli:

• simboli per variabili: $x$, $y$, $z$, $x_{1}$, $x_{2}$, $x_{3}$, $x_{4}$, ...
• costanti individuali: $0$
• simboli per funzioni unarie: $S$
• simboli per funzioni binarie: $+$, $\times$
• simboli per relazioni binarie: $=$
• simboli per connettivi logici, quantificatori e parentesi

Nella sintassi di PA per indicare la funzione binaria $+$ calcolata sui termini $t_{1}$ e $t_{2}$ anziché scrivere $+(t_{1},t_{2})$ si è soliti scrivere $t_{1}+t_{2}$. Una convenzione analoga vale per la funzione binaria $\times$.

Gli assiomi di PA sono costituiti dagli assiomi logici, gli assiomi per l'uguaglianza e i seguenti assiomi propri:

(PA1) $\forall x\neg (S(x)=0)$

(PA2) $\forall x\forall y(S(x)=S(y)\rightarrow x=y)$

(PA3) $\forall x(x+0=x)$

(PA4) $\forall x\forall y(x+S(y)=S(x+y))$

(PA5) $\forall x(x\times 0=0)$

(PA6) $\forall x\forall y(x\times S(y)=(x\times y)+x)$

(PA7) la chiusura universale di

$\varphi (0,x_{1},...x_{n})\land (\forall x(\varphi (x,x_{1},...,x_{n})\rightarrow \varphi (S(x),x_{1},...,x_{n})))\rightarrow \forall x\varphi (x,x_{1},...,x_{n})$

per ogni fbf $\varphi (x,x_{1},...,x_{n})$ in cui $x,x_{1},...,x_{n}$ sono variabili libere.

(PA7) è uno schema di assiomi chiamato schema di induzione, si ha un assioma distinto per ogni fbf $\varphi$.

L'idea che c'è dietro gli assiomi è la seguente:

• (PA1) traduce formalmente l'affermazione "zero non è il successore di alcun numero" (il quarto degli assiomi di Peano),
• (PA2) traduce formalmente l'affermazione "numeri diversi hanno successori diversi" (il terzo degli assiomi di Peano),
• (PA3) e (PA4) danno insieme una definizione ricorsiva dell'operazione di addizione a partire dalla funzione successore,
• (PA5) e (PA6) definiscono ricorsivamente la moltiplicazione a partire dall'addizione,
• (PA7) racchiude le formulazioni di tutte le possibili istanze del principio di induzione (il quinto degli assiomi di Peano) su tutte le possibili formule.

Il modello "standard"

Gli assiomi di PA sono stati elaborati con un preciso modello in mente:

• l'insieme di riferimento per le variabili è l'insieme dei numeri naturali
• il simbolo $0$ vorrebbe rappresentare il numero naturale 0
• il simbolo $S$ rappresenta la funzione "successore" che associa ad un numero n il numero n+1
• i simboli $+,\times$ rappresentano le operazioni binarie di addizione e moltiplicazione
• il simbolo $=$ rappresenta la relazione di uguaglianza

I primi due assiomi (PA1) e (PA2) sono le traduzioni nel linguaggio formale dei primi due assiomi di Peano, esprimono il fatto che lo 0 non è successore di nessun numero e la funzione "successore" è una funzione iniettiva. Gli assiomi (PA3), (PA4), (PA5) e (PA6) definiscono induttivamente le operazioni di somma e moltiplicazione, la seconda in termini della prima e la prima in termini del "successore". Ci si potrebbe chiedere perché non sono stati introdotti anche assiomi per la potenza, in realtà si dimostra che gli assiomi dati sono sufficienti per rappresentare l'operazione di elevamento a potenza. (PA7) è un modo per tradurre in una teoria del primo ordine il principio di induzione mediante uno schema di assiomi. Il principio di induzione afferma che qualsiasi sottoinsieme di numeri naturali che abbia le proprietà di contenere lo 0 e di contenere i successori dei suoi elementi coincide con l'insieme dei numeri naturali, formalmente dovremmo scrivere:

$\forall U[((0\in U)\land \forall x((x\in U)\to (S(x)\in U)))\to \forall x(x\in U)]$

questa formula non è però espressa nel linguaggio del primo ordine poiché contiene quantificatori su insiemi oltre che su elementi. L'idea per aggirare l'ostacolo è di rappresentare insiemi di numeri naturali mediante fbf con una variabile libera. Anziché scrivere che $x\in U$ scriviamo $\varphi (x)$ dove $\varphi$ è una fbf che esprime le proprietà che deve avere un numero per appartenere all'insieme $U$. Quindi la traduzione della formula di sopra diventa

per ogni fbf $\varphi (x)$ con una variabile libera $(\varphi (0)\land \forall x(\varphi (x)\to \varphi (S(x)))\to \forall x\varphi (x)$

(PA7) è una naturale generalizzazione di questo schema di assiomi. Ora il problema è che non tutti gli insiemi di numeri naturali si possono rappresentare con un'opportuna fbf, per rendersene conto è sufficiente osservare che l'insieme delle parti di $\mathbb {N}$ ha la cardinalità del continuo, mentre l'insieme delle formule ben formate è numerabile. La conseguenza principale di questo fatto è l'esistenza di modelli tra loro non isomorfi, ovvero l'incapacità degli assiomi di PA di caratterizzare univocamente una struttura.

Modelli non-standard

Oltre al modello standard dei numeri naturali esistono altri modelli in cui gli assiomi (PA1)-(PA7) sono tutti verificati e che non sono isomorfi a quello standard. Definire esplicitamente uno di questi modelli è qualcosa di molto complesso, tuttavia l'esistenza di modelli non standard è dimostrabile percorrendo molte strade differenti. La dimostrazione più semplice è quella che si serve del teorema di compattezza: si aggiunge al linguaggio un nuovo simbolo di costante individuale $e$ che vorrebbe indicare un elemento "esterno" all'insieme dei numeri naturali, e si considera la teoria PA* che oltre agli assiomi di PA ha in aggiunta i seguenti infiniti assiomi:

(NS0) $e>0$

(NS1) $e>S(0)$

(NS2) $e>S(S(0))$

...

si osserva quindi che ogni sottoinsieme finito $\Phi$ di assiomi di PA^* ha un modello: infatti ci sarà un k massimo tale che l'assioma (NSi) non è in $\Phi$ per i>k, pertanto si può considerare come modello il modello standard dei numeri naturali associando al simbolo $e$ il numero naturale k+1. Chiaramente la scelta di k dipenderà dall'insieme $\Phi$, quindi questo procedimento non ci fornisce un metodo per trovare un modello verificato da tutti gli assiomi di PA^*, tuttavia il già citato teorema di compattezza a questo punto ci garantisce che tale modello esiste. È evidente che questo modello non può essere isomorfo al modello standard perché contiene un elemento (e) che, stando a quanto dicono gli assiomi, è maggiore di ogni numero naturale. Concludiamo osservando che poiché il modello soddisfa tutti gli assiomi di PA^* dovrà soddisfare tutti gli assiomi di PA, che sono anche assiomi di PA^*, dunque abbiamo dimostrato l'esistenza di un modello di PA che non è isomorfo al modello standard.

Si può dimostrare che tutti i modelli numerabili di PA sono strutturalmente isomorfi all'insieme $\mathbb {N} +\mathbb {Q} \times \mathbb {Z}$. Si dimostra anche che in un modello non-standard le operazioni di "addizione" e "moltiplicazione" (cioè le operazioni corrispondenti ai rispettivi simboli) non possono essere entrambe ricorsive.

Bibliografia

• Giuseppe Peano, Arithmetices principia, nova methodo exposita, Torino, 1889.

Voci correlate

• Assiomi di Peano
• Teoria del primo ordine
• Teorema di Goodstein
• Aritmetica di Robinson