Document type
Bachelor thesisPublication date
Publication license
Please use this identifier to cite or link to this item: https://hdl.handle.net/2445/227579
Presburger Arithmetic & Other Fragments of Number Theory
Journal Title
Authors
Director/Tutor
Journal ISSN
Volume Title
Related resource
Abstract
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.
Description
Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2025, Director: Enrique Casanovas Ruiz-Fornells
Subject (English)
Citation
Collections
Citation
PONSDOMÈNECH FILIPPONI, Gioia. Presburger Arithmetic & Other Fragments of Number Theory. [consulted: 13 of June of 2026]. Available at: https://hdl.handle.net/2445/227579