[FOM] First Order Logic/status

[joeshipman@aol.com]

-----Original Message-----
From: friedman at math.ohio-state.edu
> Here is what is generally believed:

>***Under any reasonable measure of complexity of sentences in the 
language
>of PA, any sentence or scheme in the language of PA of modest 
complexity is
>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.

-- 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.