[FOM] First Order Logic/status
joeshipman at aol.com
Sat Oct 28 19:04:35 EDT 2006
From: friedman at math.ohio-state.edu
> Here is what is generally believed:
>***Under any reasonable measure of complexity of sentences in the
>of PA, any sentence or scheme in the language of PA of modest
>either provable or refutable in PA.***
Do you believe this? It's not true for ZFC, as you showed ("There
exists a set containing all transitive sets not containing a 4-element
chain" is equivalent to the existence of a subtle cardinal and is
certainly of "modest complexity").
Can you give an example of a well-known statement in PA which is close
to the border between "modest complexity" and "immodest complexity"? I
assume you would regard the twin prime conjecture as being of "modest
complexity" and P=NP as not being so.
Suppose we replace PA with "ZF plus the negation of the axiom of
infinity", the theory of hereditarily finite sets. This is an
equivalent theory in a very strong sense, but is able to express many
statements much more compactly than PA can. For this system, would you
still assert that any sentence or scheme of modest complexity is
provable or refutable?
If your answer to this is "no", then you are saying the representation
of exponentiation is a fundamental obstacle to representing statements
in PA simply, because if you add exponentiation to the language of PA
with the obvious defining axioms, then you can immediately and
concisely interpret the theory of hereditarily finite sets.
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