Aritmetica di Robinson: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
ritocchi+incompletezza |
||
Riga 1:
{{stub matematica}}
L' '''Aritmetica di Robinson''', denotata solitamente con l'acronimo '''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 atro 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 [[funzione rappresentabile|rappresentare]] tutte le [[funzione ricorsiva primitiva|funzioni ricorsive primitive]] e di conseguenza è anche la teoria più debole a cui siano applicabili i [[teoremi di incompletezza di Gödel]].
Il [[linguaggio del primo ordine|linguaggio]] di '''Q''' è lo stesso
Gli assiomi di '''Q''' sono costituiti dagli [[assiomi logici]], gli [[assiomi per l'uguaglianza]] e i seguenti [[assiomi propri]]:
Riga 16:
</blockquote>
== Incompletezza di '''Q''' ==
Il fatto che '''Q''' sia una teoria [[completezza sintattica|incompleta]] si può vedere senza bisogno di invocare i [[teoremi di incompletezza di Gödel|teoremi di Gödel]]: un semplice [[enunciato indecidibile]] in '''Q''' è quello che afferma la proprietà commutativa della somma
:<math>\forall x \forall y (x+y=y+x)</math>.
Per mostrare che è indecidibile costruiamo un [[modello (logica matematica)|modello]] non standard di '''Q''' che non rispetti la [[proprietà commutativa]] dell'[[addizione]]: consideriamo ad esempio un modello composto dall'unione dell'insieme dei [[numero naturale|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 assioni (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). E' 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'''.
== Voci correlate ==
| |||