aritmetica di Presburger
aritmetica di Presburger
Versione semplificata dell’aritmetica di Peano, ottenuta da quest’ultima eliminando l’operazione di moltiplicazione. Più precisamente, l’aritmetica di Presburger si ottiene da quella di Peano conservando invariati tutti gli assiomi con l’eccezione di quelli della moltiplicazione, rimossi dal sistema con il simbolo stesso dell’operazione (×) ed è per questa ragione meno potente. Restano quindi: (a) gli assiomi che definiscono il successore s(n) di un numero intero n e escludono che lo 0 sia il successore di un qualche numero; (b) gli assiomi che definiscono le proprietà elementari dell’addizione, ossia che (per ogni n e m) n+0=n e n+s(m)=s(n+m); (c) l’assioma di induzione, secondo il quale ogni proprietà P dei numeri naturali esprimibile nell’aritmetica tale che P è soddisfatta da 0 e da s(n) qualora sia soddisfatta da n allora essa è soddisfatta per ogni intero m. Come è evidente, la formulazione di quest’ultimo assioma si fonda su una quantificazione nella classe delle proprietà esprimibili nell’aritmetica (si parla di ogni proprietà P) e fa dunque intervenire la logica al secondo livello (quella appunto che ‘parla’ dei teoremi della logica al primo). Nell’aritmetica di Peano, per formulare l’assioma di induzione al primo livello della logica si paga un prezzo molto alto: esso è sostituito da un insieme infinito di assiomi, uno per ciascuna proprietà P. La caratteristica fondamentale dell’aritmetica di Presburger è proprio di poter essere finitamente assiomatizzata, ossia in essa è possibile sostituire gli infiniti ‘assiomi di induzione’ di cui sopra con un numero finito di altri assiomi ottenendo una teoria con gli stessi identici teoremi. Un’importante conseguenza di questo fatto è la completezza della teoria nel senso di Hilbert-Gödel, dimostrata dal matematico polacco Mojzesz Presburger nel 1929: differentemente dall’aritmetica di Peano, in quella di Presburger ogni proposizione vera (ossia che non ammette controesempi) è anche dimostrabile (in un numero finito di passi). In altri termini, nell’aritmetica di Presburger ogni proposizione è decidibile.
→ Programmazione, algoritmi di