[FOM] re Harvey on "a very exciting claim."

Gabriel Stolzenberg gstolzen at math.bu.edu
Sun Mar 26 13:17:43 EST 2006



   In "a very exciting claim" (Mar 21), I made the following comment
in response to part of a remark by Harvey Friedman that Andrej Bauer
quoted (Mar 20).

> >  All???  How can one know that all constructive proofs of some
> > statement are grotesque (in the sense described or any other)?
>
> >This is one of the most exciting claims I've ever heard.

   In what follows, I reply to part of Harvey's reply to this (Mar 22).

> Recall the famous Kruskal Theorem:

> I spoke to Bishop about this theorem, and sent him the simplest known
> proof, due to Nash-Williams. I think I sent it also to Stolzenberg,
> but I am not sure. In any case, Bishop (and Stolzenberg) confirmed
> that the proof is rather far from constructive.

   Harvey, I had the Nash-Williams proof of Kruskal's theorem in mind
when I made my remark.

   I'm not sure that you sent it to me.  (I recall something you wrote
with a copyright at the top.)  More important, I was introduced to all
this stuff by you, mainly in telephone conversations.  Starting, as I
recall, with Paris-Harrington.

   I have no recollection of ever thinking that the proof is "rather
far from constructive."  (But I see a deep issue here, which I'll
take up in a separate message.)  Indeed, about 15 years ago, I spent
a long time working with someone who constructed a (constructive)
argument along the general lines of Nash-Williams but, IMHO, more
beautiful.

   As for Bishop, you may be right but I have to wonder whether you
remember correctly.  (In the memorial volume for Bishop, Nerode
vividly remembered *exactly backwards* something Bishop said in a
lecture and even recalled discussing it with him during the question
period!)  It doesn't sound like Bishop to me.  Also, as I recall,
my contact with you about this was several years after Bishop had
died.  (I'll try to check.)  Do you recall having two discussions
about Kruskal and constructivity spaced this far apart?


> THEOREM 8. Corollary 7 can be proved in strictly finite mathematics.
> However, any such proof in Pi12-TI_0 must use at least 2^[1000]
> symbols.

>  Here 2^[1000] is an exponential stack of 2's of height 1000.

   Harvey, I don't understand what this has to do with my remark about
your claim.

   With best regards,

   Gabe Stolzenberg






More information about the FOM mailing list