A note on definability in fragments of arithmetic with free unary predicates
From MaRDI portal
Publication:365661
DOI10.1007/s00153-013-0328-9zbMath1279.03066MaRDI QIDQ365661
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
computational complexity; decidability; definability; expressiveness; Presburger arithmetic; Skolem arithmetic
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 Π11 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