[FOM] Re: Addition with Primality

[H. Enderton]

Karim Zahidid pointed out that
>there is a paper  proving the undecidability of addition and primality
>assuming Schinzel's Hypothesis.  It appeared in the Journal of Symbolic
>Logic in the mid nineties.  The authors include Alan Woods and
>Jockusch.

And the third author is P. T. Bateman.  JSL, vol. 58 no. 2 (1993),
pp. 672-687.  The paper shows that -- given Schinzel's Hypothesis
from number theory -- multiplication is definable from addition and
primality.

As that paper notes, Semenov has shown that the theory of the natural
numbers with addition and the set of factorials is decidable.

--Herb Enderton