305 – Friedman’s theorem

I am sketching here a proof of Harvey Friedman‘s result mentioned in lecture. The proof will not be needed for the rest of the course, but it is a nice argument that you may enjoy reading.

Recall that a sequence has property iff there are no integers such that the sequence is a subsequence of .

Here, we are using the notion of subsequence where terms must appear in order but are not required to be consecutive: A sequence is a subsequence of iff there are indices such that

Theorem (H. Friedman, 2001). For any positive integer there is a longest finite sequence in letters with property .

(Of course, once we know that the theorem is true, we can proceed as in lecture and define as the length of this longest sequence.)

We will prove the theorem in two stages: Fix , and consider only sequences in letters.

• We will show that there is no infinite sequence with property , and
• We will show that this implies that there must be a longest finite sequence with property .

I. Finiteness implies a longest sequence.

I will start with the second stage, as it is easier. This is a typical application of König’s lemma. (Here are some notes I wrote on this result:

• Part I.
• Part II.

But I will present the argument in a self contained way.)

The idea is simple. Suppose towards a contradiction that there are arbitrarily large finite sequences with property . We use this to prove that there is an infinite such sequence. To simplify notation, “sequence” means “sequence with property ” throughout this section.

Clearly, if is a sequence, then any initial segment of is also a sequence (i.e., it has property as well). It follows that there are sequences of all finite lengths. Now, since each term in the sequences is one of only possible letters, the number of sequences of any fixed finite length must be finite. Introduce a (partial) order on sequences by saying that iff is a proper initial segment of .

Now we define an infinite sequence by a recursive argument: Since there are infinitely many sequences and only finitely many “sequences of length 1”, at least one of these sequences, say , must be smaller than infinitely many sequences. Otherwise, for each sequence of length 1 there are only finitely many larger sequences, but then there are only finitely many sequences in total, contradicting that there are sequences of arbitrarily large size.

Now restrict to the sequences that are larger than . Since there are infinitely many of them, and only finitely many have size 2, among them there must be at least one, say , that is smaller than infinitely many other sequences. Continue this way: Once we have identified smaller than infinitely many sequences, pick among these one of length , say , that itself is smaller than infinitely many other sequences.

This process generates an infinite sequence , and we are done: We have reached a contradiction. It follows that there cannot be arbitrarily large sequences, and therefore there must be some of largest possible size.

II. There are no infinite sequences with property

Now we must argue that no infinite sequence in letters can have property . The argument makes use of Higman’s lemma, a basic result from the theory of well-quasi-orders, or wqo theory but, again, I keep the presentation self contained.

It turns out that it pays off to prove a stronger result. What we show is the following:

Theorem. Let be a positive integer. Suppose we are given a infinite sequence where each is itself a finite sequence, all of its terms coming from . Then there are such that is a subsequence of .

Note that the theorem immediately implies that there is no infinite sequence in letters with property , because if is a sequence, and each is one of , we can define , and the theorem tells us precisely that does not have property .

To prove the theorem, we proceed by contradiction. Call a sequence a bad sequence iff it contradicts the theorem, i.e., iff each is a finite sequence where each term comes from , and no is a subsequence of a with . So, towards a contradiction, assume that there is a bad sequence. Note that in no bad sequence we can have an empty .

Define as a finite sequence of minimal length that starts a bad sequence. Now define as a finite sequence of minimal length among the second terms of bad sequences that begin with . Then define as a finite sequence of minimal length among the third terms of bad sequences that begin with . Continue this way, so that a “minimal bad sequence”

is produced.

Since the are non-empty, and their terms come from the finite set , it must be the case that there are infinitely many that begin with the same term, say

Define as the result of removing from this first term. Note that

is also a bad sequence: If and is a subsequence of , then it is also a subsequence of , contradicting that is a bad sequence. On the other hand, if is a subsequence of for some , then is a subsequence of , as their first term is the same, and again this contradicts that is a bad sequence.

But now we have a problem, as the -st term of is shorter than , contradicting the way the sequence was constructed. This contradiction completes the proof.

III. A closing remark

The results of Sections I and II prove Friedman’s theorem. Although the argument is very nice and actually simpler than one might have expected, it is also somewhat unsatisfactory, since the proof is highly nonconstructive. The problem with this is that, even though we now know that is a well defined finite number, the proof gives us no clue as to how large it must be, and it is not at all clear how to modify the argument in order to extract from it an upper bound for the size of

Friedman’s result comes from

• Harvey Friedman, Long finite sequences,  J. Combin. Theory Ser. A, 95 (1) (2001), 102–144.

Here is a link to the review of the paper on MathSciNet. As mentioned on Homework II, you may want to wait until after you have turned in your homework before looking at the paper (or the review), in order not to spoil problem 6.

Advertisement