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

DOI10.1007/s00153-013-0328-9zbMath1279.03066MaRDI 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 complexity; decidability; definability; expressiveness; Presburger arithmetic; Skolem arithmetic

Mathematics Subject Classification ID

03D35: Undecidability and degrees of sets of sentences

03F30: First-order arithmetic and fragments

03C62: Models of arithmetic and set theory

03F35: Second- and higher-order arithmetic and fragments

03C40: Interpolation, preservation, definability

Related Items

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, Some new results in monadic second-order arithmetic

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