Archive for Mathematical Logic 52 (5-6):507-516 (2013)

We carry out a study of definability issues in the standard models of Presburger and Skolem arithmetics (henceforth referred to simply as Presburger and Skolem arithmetics, for short, because we only deal with these models, not the theories, thus there is no risk of confusion) supplied with free unary predicates—which are strongly related to definability in the monadic SOA (second-order arithmetic) without × or + , respectively. As a consequence, we obtain a very direct proof for ${\Pi^1_1}$ -completeness of Presburger, and also Skolem, arithmetic with a free unary predicate, generalize it to all ${\Pi^1_n}$ -levels, and give an alternative description of the analytical hierarchy without × or + . Here ‘direct’ means that one explicitly m-reduces the truth of ${\Pi^1_1}$ -formulae in SOA to the truth in the extended structures. Notice that for the case of Presburger arithmetic, the ${\Pi^1_1}$ -completeness was already known, but the proof was indirect and exploited some special ${\Pi^1_1}$ -completeness results on so-called recurrent nondeterministic Turing machines—for these reasons, it was hardly able to shed any light on definability issues or possible generalizations
Keywords Definability  Expressiveness  Decidability  Computational complexity  Presburger arithmetic  Skolem arithmetic
Categories (categorize this paper)
DOI 10.1007/s00153-013-0328-9
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 64,159
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Definability and Decision Problems in Arithmetic.Julia Robinson - 1949 - Journal of Symbolic Logic 14 (2):98-114.
Decidability and Essential Undecidability.Hilary Putnam - 1957 - Journal of Symbolic Logic 22 (1):39-54.
Undecidable Extensions of Skolem Arithmetic.Alexis Bès & Denis Richard - 1998 - Journal of Symbolic Logic 63 (2):379-401.

View all 8 references / Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Presburger Arithmetic with Unary Predicates is Π11 Complete.Joseph Y. Halpern - 1991 - Journal of Symbolic Logic 56 (2):637 - 642.
Definability of Initial Segments.Akito Tsuboi & Saharon Shelah - 2002 - Notre Dame Journal of Formal Logic 43 (2):65-73.
Theories of Arithmetics in Finite Models.Michał Krynicki & Konrad Zdanowski - 2005 - Journal of Symbolic Logic 70 (1):1-28.
On First-Order Theories with Provability Operator.Sergei Artëmov & Franco Montagna - 1994 - Journal of Symbolic Logic 59 (4):1139-1153.
An Algebraic Treatment of Quantifier-Free Systems of Arithmetic.Franco Montagna - 1996 - Archive for Mathematical Logic 35 (4):209-224.
Presburger Sets and P-Minimal Fields.Raf Cluckers - 2003 - Journal of Symbolic Logic 68 (1):153-162.


Added to PP index

Total views
32 ( #342,463 of 2,454,901 )

Recent downloads (6 months)
1 ( #449,233 of 2,454,901 )

How can I increase my downloads?


My notes