Decidability and classification of the theory of integers with primes

DOI10.1017/JSL.2017.16MaRDI QIDQ5359574zbMATH OpenOpenAlexFDO

Authors Itay Kaplan, S. Shelah

Publication date 26 September 2017

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

Full work available at URL https://arxiv.org/abs/1601.07099

zbMATH Keywords

primesdecidabilitymodel theoryDickson's conjecture

Mathematics Subject Classification ID

Classification theory, stability, and related concepts in model theory (03C45) Decidability of theories and sets of sentences (03B25) First-order arithmetic and fragments (03F30) Primes (11A41) Decidability (number-theoretic aspects) (11U05)

Abstract: We show that under Dickson's conjecture about the distribution of primes in the natural numbers, the theory Th(Z,+,1,0,Pr) where Pr is a predicate for the prime numbers and their negations is decidable, unstable and supersimple. This is in contrast with Th(Z,+,0,Pr,<) which is known to be undecidable by the works of Jockusch, Bateman and Woods.

Recommendations

• Decidability and undecidability of theories with a predicate for the primes
• On the additive theory of prime numbers
• Universal theories of integers and the extended Bliznetsov hypothesis
• The theory of integer multiplication with order restricted to primes is decidable
• scientific article; zbMATH DE number 221693

Cites work

• scientific article; zbMATH DE number 4045816 (Why is no real title available?)
• scientific article; zbMATH DE number 1827828 (Why is no real title available?)
• A Guide to NIP Theories
• A course in model theory
• A list of arithmetical structures complete with respect to the first-order definability
• Classification theory and the number of non-isomorphic models.
• Decidability and undecidability of theories with a predicate for the primes
• Dp-minimality: basic facts and examples
• Every odd number greater than 1 is the sum of at most five primes
• Generic structures and simple theories
• Model Theory
• On dp-minimal ordered structures
• On dp-minimality, strong dependence and weight
• On superstable expansions of free abelian groups
• Some problems in logic and number theory, and their connections
• Supergenerix.
• The primes contain arbitrarily long arithmetic progressions

Cited in

(13)

• scientific article; zbMATH DE number 5901621 (Why is no real title available?)
• Model-completeness and decidability of the additive structure of integers expanded with a function for a Beatty sequence
• On the additive theory of prime numbers
• Decidability and undecidability of theories with a predicate for the primes
• THE ADDITIVE GROUPS OF AND WITH PREDICATES FOR BEING SQUARE-FREE
• A new dp-minimal expansion of the integers
• Irreducibles and Primes in Computable Integral Domains
• There are no intermediate structures between the group of integers and Presburger arithmetic
• On expansions of \((\mathbf{Z},+,0)\)
• Prime models and almost decidability
• Stability and sparsity in sets of natural numbers
• The additive structure of integers with the lower Wythoff sequence
• Decidability of extended theories of addition of the natural numbers and the integers

This page was built for publication: Decidability and classification of the theory of integers with primes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5359574)