305 – Friedman’s theorem

February 4, 2012

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 x_0 x_1 \dots x_n has property * iff there are no integers i<j\le n/2 such that the sequence x_i x_{i+1}\dots x_{2i} is a subsequence of x_j x_{j+1}\dots x_{2j}.

Here, we are using the notion of subsequence where terms must appear in order but are not required to be consecutive: A sequence a_1 a_2\dots a_k is a subsequence of b_1 b_2\dots b_l iff there are indices 1\le i_1<i_2<\dots<i_k\le l such that

b_{i_1}=a_1,b_{i_2}=a_2,\dots,b_{i_k}=a_k.

Theorem (H. Friedman, 2001). For any positive integer k there is a longest finite sequence x_1 x_2\dots x_n in k letters with property *.

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

Read the rest of this entry »