Tipus de document
Treball de fi de grauData de publicació
Llicència de publicació
Si us plau utilitzeu sempre aquest identificador per citar o enllaçar aquest document: https://hdl.handle.net/2445/227579
Presburger Arithmetic & Other Fragments of Number Theory
Títol de la revista
Director/Tutor
ISSN de la revista
Títol del volum
Recurs relacionat
Resum
This work studies the decidability of different simplified versions of the firstorder theory of natural numbers, focusing on languages that include the successor function, the order relation, and addition. It begins by introducing the key concepts of first-order logic needed to understand the problem. Then, it looks at the natural numbers with just the successor function, and next with the addition of the order relation, showing that both of these theories are decidable using a technique called quantifier elimination. The work concludes with a proof of Presburger’s theorem, which proves that the first-order theory of natural numbers with addition, order, and successor is also decidable.
Descripció
Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2025, Director: Enrique Casanovas Ruiz-Fornells
Matèries (anglès)
Citació
Col·leccions
Citació
PONSDOMÈNECH FILIPPONI, Gioia. Presburger Arithmetic & Other Fragments of Number Theory. [consulted: 24 of May of 2026]. Available at: https://hdl.handle.net/2445/227579