[FOM] PA Incompleteness

[bjstande@artsci.wustl.edu]

> Date: Mon, 15 Oct 2007 12:39:30 -0400
> From: Harvey Friedman <friedman at math.ohio-state.edu>
> Subject: Re: [FOM] PA Incompleteness
> To: fom <fom at cs.nyu.edu>
> Message-ID: <C3391002.19223%friedman at math.ohio-state.edu>
> Content-Type: text/plain; charset="US-ASCII"
>
> On 10/14/07 8:03 PM, "Feng Ye" <yefeng at phil.pku.edu.cn> wrote:
>
>> I am always wondering what will be the answer if 'normal mathematics' is
>> replaced by 'mathematics with potential applications in sciences', or
>> 'mathematics relevant to this physical universe'. The problem is that
>> all
>> current independent propositions are related to fast growing functions,
>> but
>> the scope of the physical universe that sciences are dealing with is so
>> 'ridiculously small' from the mathematical point of view.
>>
> I have a couple of remarks about this.
>
> 1. The idea that time may never end, or may go on for a very long time, is
> now present in a lot of discussions by cosmologists. In particular, I have
> seen numbers indicating how long all of the black holes will take to
> evaporate, etcetera, and if I recall properly, those numbers were
> something
> like 10^(10^100), considerably larger than what you usually see in
> cosmology.
>

I think this is actually the timescale for protons to turn into black
holes, assuming all other mechanisms of proton decay are suppressed. The
timescale for black hole evaporation is "only" about 10^80.

> 2. I now work on Pi01 independence results. I can sometimes show, or hope
> to
> show, that for somewhat reasonable n, if we restrict the Pi01 statement to
> [1,2,...,n], thereby getting a Pi00 sentence, the sentence is
> "independent"
> of ZFC in the sense that it can be proved with large cardinals, but has no
> proof in ZFC with fewer than 2^1000 symbols. Numbers like 10^(10^100) may
> give me enough wiggle room to accomplish this.
>

It seems to me that this is the opposite of what you would need to do, to
get "relevant" results. You would get a simple proof of some "irrelevant"
combinatorial result (since the witnesses are bounded by 2^(2^1000), far
greater than the number of elementary particles in the universe) from
large cardinals, and any proof of the result from ZFC must be of
immense-but-still-relevant length (if the Universe continues to exist for
2^(2^1000) years, it doesn't really matter that a proof contains 2^1000
symbols; you still have plenty of time to mull it over).
But what you want is a simple proof of some "relevant" combinatorial
result (so the witnesses should be at most 2^1000 or so, preferably even
less) but the shortest proof in ZFC needs at least 2^2^1000 symbols, and
hence is not really "relevant" even in this hypothetical eternal universe.

The latter has a more "pure mathematics" interpretation as well: it
amounts to showing that ZFC can't prove the result by any means more
efficient than a brute force search for solutions, assuming the theorem
involves subsets of cardinal equal to the witness.

--Bennett Standeven, Washington University in Saint Louis.