Decidability and undecidability of theories with a predicate for the primes

DOI10.2307/2275227zbMath0785.03002OpenAlexW2036224946MaRDI QIDQ3138021

Carl G. jun. Jockusch, Paul T. Bateman, Alan R. Woods

Publication date: 24 October 1993

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2275227

zbMATH Keywords

primesmultiplication of natural numbersdecidabilitysuccessor functionmonadic second-order theorylinear case of Schinzel's hypothesis

Mathematics Subject Classification ID

Decidability (number-theoretic aspects) (11U05) Decidability of theories and sets of sentences (03B25)

Related Items (7)

DECIDABILITY AND CLASSIFICATION OF THE THEORY OF INTEGERS WITH PRIMES ⋮ Positive existential definability of multiplication from addition and the range of a polynomial ⋮ More on an undecidability result of Bateman, Jockusch and Woods ⋮ On Monadic Theories of Monadic Predicates ⋮ A list of arithmetical structures complete with respect to the first-order definability ⋮ The monadic theory of morphic infinite words and generalizations ⋮ THE ADDITIVE GROUPS OF AND WITH PREDICATES FOR BEING SQUARE-FREE

Cites Work

• Unnamed Item
• Unnamed Item
• Relations between table-type degrees
• Theories of automata on \(\omega\)-tapes: a simplified approach
• The theory of successor with an extra predicate
• On the additive properties of numbers
• Weak Second‐Order Arithmetic and Finite Automata
• On the bounded monadic theory of well-ordered structures
• A combinatorial approach to the theory of ω-automata
• Definability in the monadic second-order theory of successor
• Testing and generating infinite sequences by a finite automaton

This page was built for publication: Decidability and undecidability of theories with a predicate for the primes