Aritmetica di Robinson

Da Wikipedia, l'enciclopedia libera.
Se riscontri problemi nella visualizzazione dei caratteri, clicca qui.

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[1] 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[modifica | modifica wikitesto]

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 \exist 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))

(Q6) \forall x (x\times 0=0)
(Q7) \forall x \forall y(x\times S(y)=(x\times y)+x)

Incompletezza di Q[modifica | modifica wikitesto]

Come accennato Q è una teoria incompleta. Questo fatto si può vedere senza bisogno di invocare i teoremi di Gödel: un semplice enunciato indecidibile in Q è quello che afferma la proprietà commutativa dell'addizione

\forall x \forall y (x+y=y+x).

Per mostrare che è indecidibile costruiamo 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); quindi estendiamo l'operazione + sull'insieme N∪{a,b} ponendo:

a+n:=a per ogni n in N
b+n:=b per ogni n 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)[2]: quello che è rilevante invece è che l'operazione "+" appena definita non commuta: a+b=a mentre b+a=b. Deduciamo che in Q non è possibile 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.

Riferimenti[modifica | modifica wikitesto]

  1. ^ R. M. Robinson, An Essentially Undecidable Axiom System in Proceedings of the International Congress of Mathematics, 1950, pp. 729-730.
  2. ^ Peter Smith, capitolo 10.5 in An Introduction to Gödel's Theorems, 2ª ed., pp. 69-70.

Voci correlate[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica