[FOM] What's so hard about addition?

by way of Martin Davis <martin@eipye.com> joeshipman at aol.com
Tue Nov 21 14:44:50 EST 2006

Not having gotten any response to my previous post, let me simplify 
it and get right to the point.

We know there are sentences of Presburger arithmetic (the theory of 
addition in the natural numbers) that require double-exponentially 
long proofs (this is true even if you allow constants for natural 
numbers, the successor function, and the < relation).

Can anyone state a proposition about addition which is easy to 
understand and does not appear to have any short proofs or disproofs?

-- JS
Check out the new AOL.  Most comprehensive set of free safety and 
security tools, free access to millions of high-quality videos from 
across the web, free AOL Mail and more.

More information about the FOM mailing list