FOM: script/can't run away

[Harvey Friedman]

>At 07:09 PM 9/14/98 -0400, Joe Shipman wrote:
>
>>A crisis of consensus will come again someday, and then it will be clear
>>to everybody why foundations are indispensable.

Martin Davis 5:30PM 9/14/98 responded:

>Yes indeed! It will come when a large cardinal axiom is used to settle a
>problem all mathemativcians know and care deeply about (e.g. the Riemann
>Hypothesis).

I have a new and relevant story to tell you concerning this.

In my posting 19:Long Finite Sequences of 9:42AM 7/31/98, I discussed the
following. Let k be a postiive integer. Define n(k) to be the length of the
longest finite sequence from {1,...,k} satisfying a very elementary
condition.

I claimed that for all k, n(k) exists. Also that n(2) = 11 and n(3) is
incomprehensibly large.
****

Back to the story. So far I talked to 7 mathematicians (profile included
below). Many of them are here, and classes haven't started yet. So I will
get more feedback.

The conversations all went like this. Try out this script on your friends
and tell me what happens.

HMF: Got something trivial looking and elementary to tell you. How long a
sequence in k letters can you write down satisfying a very simple condition?

VICTIM: OK, what's the condition?

HMF: Call the sequence x. That no consecutive block of the form
x_i,...,x_2i be a subsequence of another consecutive block x_j,...,x_2j.

VICTIM: Hmmmmmm. OK. That's simple enough.

HMF: Now in one letter - call it 1 - obviously the longest sequence is just
111.

VICTIM: Yeah, sure.

HMF: And in two letters - 1 and 2 - the longest sequence has length eleven.
Not so obvious.

VICTIM: Hmmmmmmmmmmm. I'll take your word for it.

HMF: Yeah, its elementary, but not immediate. Of course, a computer could
go through all sequences of length 11. But I do it by a proof.

VICTIM: Makes sense. OK. So what?

HMF: In k letters there is such a longest sequence.

VICTIM: Huh. Is that hard?

HMF: Well, it is fairly standard if you know a certain branch of combinatorics.

VICTIM: What branch?

HMF: Wqo theory.

VICTIM: Never heard of it.

HMF: Well, it's deep. If you don't know about it, it's not so easy to prove
there is a longest sequence. Ideas go back to Graham Higman. Anyways, let
me continue with my story.

VICTIM: OK.

HMF: In three letters, how long is the longest such sequence?

VICTIM: What's the condition again?

HMF: That no consecutive block of the form x_i,...,x_2i be a subsequence of
another consecutive block x_j,...,x_2j.

VICTIM: Right.

HMF: So, in three letters, how long is the longest such sequence?

VICTIM: You want ME to answer?

HMF: Yeah.

VICTIM: Hmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm. I'm not sure.

HMF: Guess.

VICTIM: Do I have to?

HMF: Absolutely.

VICTIM: Well, you say in one letter its .....

HMF: 3.

VICTIM: Of course. And in two letters, its ..........

HMF: Eleven, remember?

VICTIM: Yes.

HMF: And in three letters?

VICTIM: Hmmmmmmmmm. Certainly less than 200. Could be something like 60 or so.

HMF: Time's up.

VICTIM: 150.

HMF: Well, you are a little bit off.

VICTIM: Too high?

HMF: No, too low. Want to guess again?

VICTIM: No. Just tell me.

HMF: Well, here is a very very bad, small lower bound.

VICTIM: OK.

HMF: Let p be an exponential stack of 2's of height 1 trillion. That is a
small lower bound.

VICTIM: What???

HMF: Let p be an exponential stack of 2's of height 1 trillion. That is a
small lower bound.

VICTIM: Oh my God!!!!!!!!!!!!!!!!!!!!!

HMF: And now consider an exponential stack of 2's of height p.

VICTIM: Of what height??

HMF: Of height p. You know, p is itself an exponential stack of 2's of
height 1 trillion.

VICTIM: No!!!!!!! I can't take it any more. This is really surprising. Giggle.

HMF: It's bigger than 150.

VICTIM: Ouch!!!!!!!!!!!
**********

The first two I told this about are international experts in Ramsey theory.
They were somewhat surprised, but too sophisticated about such things to
express agony. One is considering mentioning it in an important upcoming
talk. They also were not naive enough to guess the three letter case, n(3),
fearing what was to come. Both are invited to talk to high school students
from time to time, and expressed interest in using this as an illustration
of the Ackerman hierarchy (the lower bound in the paper on this is
A_7(184), where A_7 is the 7-th level of the Ackerman hierarchy, where A_1
is doubling).

Then I talked to a well known core mathematician who also runs a high
school outreach program. He immediately said: "this is perfect material for
my high school program. I'm going to show it to them next week. They'll eat
it up."

And, sure enough. They ate it up. One of them reproved n(2) = 11; i.e., the
two letter case. Then they worked on n(3) and gave up.

The next victim was a very famous core mathematician. He did a little
better on the lower bound for n(3). He guessed 200 instead of 150. He also
said that he sometimes talks to high school students, and will consider
talking on this.

These two core mathematicians are in areas quite far removed from
logic/f.o.m. and combinatorics. So are the next two mathematicians I talked
to here - one in representation theory and one in classical analysis. Then
I talked to an algebraic combinatorist. The reactions were basically as
indicated.

**The point is that this problem is so elementary and so attractive and so
down to earth that the mathematicians all FEEL it.** This reaction does not
even require any familiarity with combinatorics or logic or f.o.m. It seems
universal - at least so far. And yet it is not something any of them ever
thought about. And not something they even expect to encounter in their own
research.

And now for some metamathematical results about this (claimed in 19:Long
Finite Sequences of 9:42AM 7/31/98).

THEOREM. The statement "for all k, n(k) exists" is a pi-0-2 sentence that
is provable in pi-0-3 induction but not in pi-0-2 induction. The function
n(k) eventually dominates every nested multirecursive function on the
integers (in, e.g., the sense of Tait). And n(3) >= A_7(184).

Now what if the correct theorem, instead, were the following (which is false)?

THEOREM (false). The statement "for all k, n(k) exists" is a pi-0-2
sentence that is provable in ZFC + "there exists a Mahlo cardinal" but not
in ZFC. The function n(k) eventually dominates every provably recursive
function of ZFC.

Then would we get the crisis that Shipman speaks about above?

I say YES, because they FEEL it.

So one goal for the program is to come up with something similar, that
mathematicians universally FEEL. Over the next month we shall see just how
close I have gotten. This is an evolutionary process, which is going to
yield the desired result - eventually.

When they really FEEL it, they can't run away.

PS: The manuscript on n(3) is now complete. Look for it on my website in
October, when I will have it updated.