DECIDABILITY AND UNDECIDABILITY OF THEORIES WITH A PREDICATE FOR THE PRIMES

It is shown, assuming the linear case of Schinzel's Hypothesis, that t he first-order theory of the structure <omega; +, P>, where P is the s et of primes, is undecidable and, in fact, that multiplication of natu ral numbers is first-order definable in this structure. In the other d irection, it is shown, from the same hypothesis, that the monadic seco nd-order theory of <omega; S, P> is decidable, where S is the successo r function. The latter result is proved using a general result of A. L . Semenov on decidability of monadic theories, and a proof of Semenov' s result is presented.