FOM: "Perfect" statements

[Harvey Friedman]

Here are some thoughts about the results in my posting 27:Finite
Trees/Impredicativity:Sketches  1/13/99  12:54PM.

Upon reflection, those independent statements cited there are "perfect."
Before going further, let me restate one of the several closely related
statements from there.

*) Let T be a sufficiently tall finite rooted tree with valence (splitting)
at most k. There exists 1 <= i <= hgt(T) and an inf preserving embedding
from T|<=i into T which maps T|i into T|>i.

(Here T|<=i is the subtree of vertices of height <=i above the root, where
T|<=0 consists of just the root. And T|i is the set of vertices of height
exactly i above the root. Also hgt(T) is the height of T, which is the
largest height of the vertices).

The results sketched there show that this statement is provable only from
fairly strong impredicative systems (pi-1-2-TI but not pi-1-2-TI_0, or from
TI on phi_capitalomega^littleomega(0) but not lower). And the tallness
needed in terms of k is a numerical function that grows faster than the
provably recursive functions in pi-1-2-TI_0, or TI on
<phi_capitalomega^littleomega(0).

Of course, I can't rigorously define "perfect", but here are some features:

1. All concepts involved are previously well studied in many contexts.
2. The concepts are well integrated.
3. There are no "defects"; i.e., ad hoc choices, awkward side definitions,
etcetera.
4. The statement is well motivated, and the motivation is autonomous in
that it does not depend on an infinitary statement.
5. You can't point to a place where something is brought in that causes the
logical strength to be jacked up.

Of course, these features are also informal and have some overlap.

Let's compare this, say, to the Paris/Harrington statement. I don't want to
take anything away from this breakthrough result which I have admired,
studied, and modified over the years in various contexts. And it was done
in 1977, over twenty years ago. And what I am about to say was gone over in
detail with a recent conversation I had with Leo.

It is a beautiful modification of the usual finite Ramsey theorem using the
additional concept of relatively large. Relatively large is an additional
concept that is not normally used in combinatorial studies, and is not well
integrated with the other concepts (colorings, homogenous sets). It is most
naturally motivated by the obvious fact that infinite sets are "relatively
large," and so the infinite Ramsey theorem is an integral part of the
motivation for the Paris/Harrington statement. Also, you can obviously
point to a place where something is brought in that causes the logical
strength to be jacked up - namely you point to relatively large. There are
slight defects in that 1) relatively large has obvious variants that
require the number of elements be related to the least element in various
ways (e.g., are there to be more elements than the least element, or at
least as many elements as the least element?); 2) there are slightly more
parameters used in the statement than is comfortable. E.g., you can't just
say relatively large; you also have to say relatively large and at least as
large as a parameter. [Of course, some of these points are perhaps of
questionable force  and/or perhaps curable].

In fact, clearly the original finite Ramsey theorem is "perfect" in a sense
that Paris/Harrington is not; this is of course widely acknowledged. But
also the above *) is also "perfect" in any sense that the original finite
Ramsey theorem is "perfect." Perhaps a case can even be made that *) is
"perfect" in ways that the original finite Ramsey theorem is not! But I am
not sure one way or the other about that; and, besides, that is going
farther than I need to, and perhaps represents overkill.

OK, so I am happy about *). It's a nice story. The first impredicative
finite statements were my original finite forms of Kruskal's theorem. They
are certainly not "perfect" in the sense that *) is "perfect." They were
more properly comparable to Paris/Harrington. Here the comparison was
unclear, and I think most people thought they were not as clean as
Paris/Harrington, but I was never sure one way or the other. Of course, I
always felt it was obvious that they were the first really convincing
examples of the necessary use of impredicativity in finite mathematics. But
"perfect"? No. That's why I spent 17 years from 1981 through 1998 thinking
about how to "perfect them." If I thought they were "perfect," I wouldn't
have come up with *).

As long as I am telling nice stories, here is another one. In 1982, I
jazzed up Kruskal's theorem by inventing the gap condition (my extended
Kruskal's theorem). I jazzed it up because I wanted a good statement
independent of pi-1-1-CA_0. I told Robertson and Seymour about it and the
proof. It did provide background information for the nonconstructive part
of their proof of the graph minor theorem. Then I hooked up with them to
prove that the graph minor theorem also cannot be proved in pi-1-1-CA_0 (in
1987). The graph minor theorem is a "perfect" theorem in the sense that my
extended Kruskal theorem is not.

*****

But now I come to a new main point. I have been working for decade after
decade on simpler and simpler necessary uses of large cardinals in
finite/dicrete mathematics. I can now state more clearly what I am after.

I am looking for a similarly "perfect" example for ZFC and higher. This is
harder, and is going to take longer. But I can now point to a clear example
of "perfection". Something not previously in the literature. Something I
cooked up after 17 years of effort from a quite convincing beginning.
Namely *) above - as a paradigm of what I am looking for.