## 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 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 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.)