Aritmetica di Robinson
Da Wikipedia, l'enciclopedia libera.
Questa voce è solo un abbozzo (stub). Se puoi, contribuisci adesso a migliorarla secondo le convenzioni di Wikipedia. Per l'elenco completo degli stub di matematica, vedi la relativa categoria.
L' Aritmetica di Robinson, denotata solitamente con Q in logica matematica, è una teoria del primo ordine 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 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 siano applicabili i teoremi di incompletezza di Gödel.
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)
- (Q2)
- (Q3)
- (Q4)
- (Q5)
- (Q6)
- (Q7)
[modifica] Incompletezza di Q
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 della somma
- .
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):=b
- S(b):=a
è 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), ma in effetti non è importante come ciò venga fatto: 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.