[FOM] What's so hard about addition?
by way of Martin Davis <firstname.lastname@example.org>
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?
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