title: Aritmetica di Robinson
text: # Aritmetica di Robinson
  
  L'aritmetica di Robinson, denotata solitamente con Q in logica matematica, è una teoria del primo ordine, definita per la prima volta da Raphael M. Robinson nel 1950 che ha come assiomi propri una versione ridotta degli assiomi di Peano in cui è assente il principio di induzione e c'è l'aggiunta di un assioma che afferma che ogni numero naturale diverso da zero è successore di qualche altro numero (cosa che nell'aritmetica di Peano è dimostrabile per induzione). L'interesse dell'aritmetica di Robinson per la logica risiede nel fatto che è la teoria più debole in cui è possibile rappresentare tutte le funzioni ricorsive primitive e di conseguenza è anche la teoria più debole a cui sia applicabile il primo dei teoremi di incompletezza di Gödel.
  
  ## Definizione
  
  Il linguaggio di Q è il linguaggio dell'aritmetica del primo ordine.
  
  Gli assiomi di Q sono costituiti dagli assiomi logici, gli assiomi per l'uguaglianza e i seguenti assiomi propri:
  
  (Q1) $\forall x\neg (S(x)=0)$
  
  * esprime il fatto che 0 non è il successore di alcun numero;
  
  (Q2) $\forall x\forall y(S(x)=S(y)\rightarrow x=y)$
  
  * esprime il fatto che numeri diversi hanno successori diversi, cioè la funzione successore è una funzione iniettiva;
  
  (Q3) $\forall x(\neg (x=0)\to \exists y(x=S(y)))$
  
  * esprime il fatto che ogni numero diverso da 0 è il successore di qualche altro numero;
  
  (Q4) $\forall x(x+0=x)$ (Q5) $\forall x\forall y(x+S(y)=S(x+y))$
  
  * questa coppia di assiomi definisce ricorsivamente l'addizione;
  
  (Q6) $\forall x(x\times 0=0)$ (Q7) $\forall x\forall y(x\times S(y)=(x\times y)+x)$
  
  * questa coppia di assiomi definisce ricorsivamente la moltiplicazione.
  
  ## Incompletezza di Q
  
  Come accennato, Q è una teoria incompleta. Questo fatto si può vedere senza bisogno di invocare i teoremi di Gödel, dal momento che esiste un semplice enunciato indecidibile in Q: che è quello che afferma la proprietà commutativa dell'addizione
  
      $\forall x\forall y(x+y=y+x).$
  
  Per mostrare che è indecidibile si costruisce un modello non standard di Q che non rispetti la proprietà commutativa dell'addizione: consideriamo ad esempio un modello composto dall'unione dell'insieme dei numeri naturali N con un insieme di due elementi "estranei" {a,b}. Definiamo la funzione "successore" per a e b come
  
      S(a):=a
      S(b):=b
  
  è facile verificare che S rispetta gli assiomi (Q1), (Q2) e (Q3) sui successori; a questo punto, estendiamo all'insieme N∪{a,b} l'operazione +, compatibilmente con S e gli assiomi (Q4) e (Q5), ponendo:
  
      a+n:=a per ogni n pari in N
      a+n:=b per ogni n dispari in N
      b+n:=b per ogni n pari in N
      b+n:=a per ogni n dispari in N
      n+a:=b per ogni n in N
      n+b:=a per ogni n in N
      a+a:=b
      b+b:=a
      a+b:=a
      b+a:=b
  
  si può verificare che l'operazione definita rispetta gli assiomi (Q4) e (Q5). È possibile anche estendere la moltiplicazione in N∪{a,b} in modo da verificare gli assiomi (Q6) e (Q7): quello che è rilevante invece è che l'operazione "+" appena definita non commuta: a+b=a mentre b+a=b. Deduciamo che in Q non è possibile, partendo dagli assiomi, dimostrare la formula che afferma la proprietà commutativa della somma. D'altra parte, in Q non è possibile nemmeno dimostrare la sua negazione perché l'enunciato è vero nel modello standard dei numeri naturali. Concludiamo che l'enunciato che esprime la proprietà commutativa è indecidibile in Q.
  
  