Linguaggio dell'aritmetica del primo ordine

In logica matematica il linguaggio dell'aritmetica del primo ordine è un linguaggio del primo ordine con cui è possibile sviluppare teorie formali dell'aritmetica elementare come l'aritmetica di Peano e l'aritmetica di Robinson.

L'alfabeto del linguaggio dell'aritmetica del primo ordine è costituito da:

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

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$.

Modello standard

Si chiama modello standard del linguaggio dell'aritmetica il modello che si ha considerando come universo del discorso l'insieme N dei numeri naturali e interpretando il simbolo S come la funzione successore che associa ad un numero n il numero n+1, il simbolo 0 con il numero zero (e di conseguenza il termine S(0) con il successore di 0, quindi 1, S(S(0)) con il numero 2 e così via), interpretando i simboli + e × come le operazioni di addizione e moltiplicazione e il simbolo = come la relazione di uguaglianza.

Capacità espressiva

Esprimere insiemi, proprietà e relazioni

Nel linguaggio dell'aritmetica del primo ordine non ci sono simboli per indicare insiemi di numeri naturali, tuttavia un insieme può essere individuato con una formula aperta che interpretata nel modello standard esprima la condizione necessaria e sufficiente che deve soddisfare un numero naturale per appartenere a quell'insieme. Ad esempio l'insieme dei numeri pari può essere espresso dalla proprietà "x è un multiplo di 2" che corrisponde alla fbf:

$\varphi (x):=\exists y(x=y\times S(S(0)))$

che interpretata nel modello standard afferma che x è tale che esiste un altro numero y che moltiplicato per 2 (che scriviamo (S(S(0)))) dà come risultato x.

Indichiamo con $S^{n}(0)$ il termine $S(S(S(...(((0)))...)))$ in cui il simbolo $S$ compare $n$ volte.

Diremo che una formula aperta φ(x) esprime un insieme di numeri naturali $U$ (o equivalentemente una proprietà) se accade che

• per ogni $n\in U$ la formula $\varphi (S^{n}(0))$ è vera nel modello standard
• per ogni $n\notin U$ la formula $\neg \varphi (S^{n}(0))$ è vera nel modello standard

Diremo quindi che un insieme (o una proprietà) è esprimibile nel linguaggio dell'aritmetica se esiste una formula aperta φ(x) che lo esprime.

La nozione di esprimibilità si può generalizzare a sottoinsiemi di N^k, in tal caso per esprimere un insieme sarà necessaria una formula aperta con k variabili libere φ(x₁,x₂,... ,x_k).

Osserviamo che non tutti i sottoinsiemi dell'insieme N dei numeri naturali o di N^k sono esprimibili dal momento che la totalità dei sottoinsiemi di N (o di N^k) ha la cardinalità del continuo mentre l'insieme delle formule è numerabile.

Si può dimostrare che tutti gli insiemi ricorsivi sono esprimibili.

La relazione ≤

Una relazione può essere identificata con l'insieme delle coppie ordinate di elementi che sono tra loro in relazione. La relazione ≤ ad esempio si può identificare con l'insieme delle coppie

$\{(x,y)\in \mathbb {N} ^{2}:x\leq y\}$

Esprimere la relazione ≤ quindi equivale a trovare una fbf che esprima questo insieme. Il modo più semplice di ottenere una fbf di questo tipo si ha con la formula

$\varphi (x,y):=\exists z(y=x+z)$.

Dunque la presenza dei simboli + e = rende superflua l'aggiunta nel linguaggio di un simbolo per la relazione ≤ in quanto esiste già una formula che la esprime.

Esprimere funzioni

Diremo che una funzione

$f:\mathbb {N} ^{k}\to \mathbb {N}$

è esprimibile nel linguaggio dell'aritmetica quando è esprimibile il suo grafico, ovvero l'insieme:

$\{(x_{1},...,x_{k},y)\in \mathbb {N} ^{k+1}:y=f(x_{1},...,x_{k})\}$.

Funzioni che si possono esprimere facilmente sono quelle per cui disponiamo di simboli appositi:

• la funzione successore, espressa dalla formula

$y=S(x)$

• l'addizione, che si può esprimere con la formula

$y=x_{1}+x_{2}$

• la moltiplicazione, che si esprime con la formula

$y=x_{1}\times x_{2}$.

Meno banale è capire se si possono esprimere altre funzioni come la sottrazione o la potenza. Di fatto si può dimostrare che tutte le funzioni ricorsive sono esprimibili nel linguaggio dell'aritmetica. In particolare lo è anche la potenza: questo significa che aggiungere al linguaggio dei simboli di operazione binaria per le potenze non avrebbe accresciuto la sua capacità espressiva. Viceversa se avessimo rinunciato al simbolo di addizione o di moltiplicazione non ci sarebbe stato modo di esprimerlo mediante gli altri simboli.

Voci correlate

• Linguaggio del primo ordine
• Aritmetica di Peano
• Aritmetica di Robinson
• Rappresentabilità (logica matematica)