Decidability and classification of the theory of integers with primes

DOI10.1017/JSL.2017.16zbMATH Open1422.03071arXiv1601.07099OpenAlexW2963542726MaRDI QIDQ5359574FDOQ5359574

Authors: Itay Kaplan, S. Shelah 

Publication date: 26 September 2017

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

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.

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

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

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)

Cites Work

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

Cited In (13)

• Title not available (Why is that?)
• 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)