A note on definability in fragments of arithmetic with free unary predicates

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


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



    Upload a copy of this work     Papers currently archived: 94,659

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Presburger arithmetic with unary predicates is Π11 complete.Joseph Y. Halpern - 1991 - Journal of Symbolic Logic 56 (2):637 - 642.
Reflection ranks and ordinal analysis.Fedor Pakhomov & James Walsh - 2021 - Journal of Symbolic Logic 86 (4):1350-1384.
Strict $${\Pi^1_1}$$ -reflection in bounded arithmetic.António M. Fernandes - 2010 - Archive for Mathematical Logic 49 (1):17-34.
Rigid models of Presburger arithmetic.Emil Jeřábek - 2019 - Mathematical Logic Quarterly 65 (1):108-115.
An Incompleteness Theorem Via Ordinal Analysis.James Walsh - 2024 - Journal of Symbolic Logic 89 (1):80-96.
Bounding quantification in parametric expansions of Presburger arithmetic.John Goodrick - 2018 - Archive for Mathematical Logic 57 (5-6):577-591.
Definability of Initial Segments.Akito Tsuboi & Saharon Shelah - 2002 - Notre Dame Journal of Formal Logic 43 (2):65-73.
Subsystems of second-order arithmetic between RCA0 and WKL0.Carl Mummert - 2008 - Archive for Mathematical Logic 47 (3):205-210.


Added to PP

45 (#350,676)

6 months
10 (#396,711)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Stanislav Speranski
St. Petersburg State University