Aritmetica di Presburger

Aritmetica di Presburger è la teoria del primo ordine dei numeri naturali con l'aggiunta introdotta nel 1929 da Mojżesz Presburger, da cui prende il nome. La firma dell'aritmetica Presburger contiene solo l'operazione di addizione e l'uguaglianza, omettendo completamente l'operazione di moltiplicazione. Gli assiomi includono uno schema di induzione.

L'aritmetica di Presburger è meno potente dell'aritmetica di Peano, che include sia le operazioni di addizione che di moltiplicazione. Diversamente dall'aritmetica di Peano, l'aritmetica di Presburger è una teoria decidibile.

Voci correlate

• Mojżesz Presburger
• Aritmetica di Peano

Collegamenti esterni

• aritmetica di Presburger, Luca Tomassini - Enciclopedia della Scienza e della Tecnica (2008)