[FOM] A question on Natural Arithmetical Independence

Dmytro Taranovsky dmytro at mit.edu
Fri Nov 14 20:53:39 EST 2003


Consider the following statement:
The sum of the binary digits of the number of functions (from sequences
of 100 integers to integers) that are polynomial in 100 variables with
degree less than 1000 (note: x*y is a polynomial of degree 2) and
coefficients that are integers of absolute value less than 2^1000, and
have no zeroes   is even.

Is the statement independent of Peano Arithmetic?  If so, how do you
prove it?  Is it independent of ZFC+(there exists a supercompact
cardinal)?  If so, how do you prove the independence under the
assumption that there is a countable transitive model of ZFC+(there
exists a supercompact cardinal)?

If the statement is decidable in ZFC, would a simple modification (which
one?) make it undecidable?


Dmytro Taranovsky
http://web.mit.edu/dmytro/www/main.htm



More information about the FOM mailing list