[FOM] Re: Addition with Primality

[Dmytro Taranovsky]

Thank you for pointing out the paper about decidability and primality.  It is
interesting to note (and is proven in that paper) that under reasonable
hypotheses (the special case of Schinzel's Hypothesis presented in my posting
suffices) the monadic second order theory of natural numbers with successor and
primality predicate is decidable, so we have a natural decidable theory in
which some prominent open mathematical problems are expressible.

Multiplication of natural numbers is definable from addition and any set that is
the range of a polynomial on integers of degree at least two.  However, the
theory of natural numbers under addition and exponentiation base 2 is
decidable.

Dmytro Taranovsky