Decidability and undecidability of theories with a predicate for the primes

Abstract

Abstract It is shown, assuming the linear case of Schinzel's Hypothesis, that the first-order theory of the structure 〈ω; +, P 〉, where P is the set of primes, is undecidable and, in fact, that multiplication of natural numbers is first-order definable in this structure. In the other direction, it is shown, from the same hypothesis, that the monadic second-order theory of 〈ω S , P 〉 is decidable, where S is the successor function. The latter result is proved using a general result of A. L. Semënov on decidability of monadic theories, and a proof of Semënov's result is presented.