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

DOI10.1007/s00153-013-0328-9zbMath1279.03066OpenAlexW2031648800MaRDI QIDQ365661

Stanislav O. Speranski

Publication date: 9 September 2013

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00153-013-0328-9

zbMATH Keywords

computational complexitydecidabilitydefinabilityexpressivenessPresburger arithmeticSkolem arithmetic

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) First-order arithmetic and fragments (03F30) Models of arithmetic and set theory (03C62) Second- and higher-order arithmetic and fragments (03F35) Interpolation, preservation, definability (03C40)

Related Items

Some new results in monadic second-order arithmetic ⋮ Quantifying over events in probability logic: an introduction ⋮ Elementary invariants for quantified probability logic ⋮ Universal first-order quantification over automata ⋮ Notes on the computational aspects of Kripke's theory of truth ⋮ Reasoning about arbitrary natural numbers from a Carnapian perspective

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Propositional dynamic logic of nonregular programs
• Decidability and expressiveness for first-order logics of probability
• Complexity for probability logic with quantifiers over propositions
• Decidability and essential undecidability
• Presburger arithmetic with unary predicates is Π₁¹ complete
• Undecidable extensions of Skolem arithmetic
• The Undecidability of Theories of Groupoids with an Extra Predicate
• Definability and decision problems in arithmetic
• A list of arithmetical structures complete with respect to the first-order definability

This page was built for publication: A note on definability in fragments of arithmetic with free unary predicates