[FOM] Re: Addition with Primality

Dmytro Taranovsky dmytro at mit.edu
Tue Aug 10 14:48:37 EDT 2004

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

Dmytro Taranovsky

More information about the FOM mailing list