The Free Set Lemma

Question

The statement of the lemma is as follows: if $$f: \omega_1 \rightarrow \{x\ :\ x\ \textrm{is finite}\}$$ then there is an uncountable $S \subseteq \omega_1$ such that for all distinct $\alpha,\ \beta \in S$, we have $\alpha \notin f(\beta)$.

My initial attempts at a proof by contradiction didn't get me anywhere because I'm given no information about $f$ at all. Any ideas on what to try next would be great!

Edit: A (particularly misleading) typo was fixed; $S$ is meant to be uncountable, not countable.

Answer 1

By applying the Pressing Down Lemma to the regressive function $\alpha\mapsto\sup f(\alpha)\cap\alpha$, we can get an ordinal $\gamma\lt\omega_1$ and an uncountable (in fact stationary but that doesn't matter) set $A\subseteq\omega_1\setminus\gamma$ such that $f(\alpha)\cap\alpha\subseteq\gamma$ for all $\alpha\in A$. Hence, for distinct ordinals $\alpha,\beta\in A$, $\beta\in f(\alpha)$ implies $\beta\gt\alpha$. Now all we have to do is define a strictly increasing sequence $\langle\alpha_\xi:\xi\lt\omega_1\rangle$ so that $\alpha_\xi\in A\setminus\bigcup_{\eta\lt\xi}f(\alpha_\eta)$.

Answer 2

I assume you mean $$f:\omega_1\to\{x\subseteq\omega_1:|x|\lt\omega\}.$$ For some $n\lt\omega$, there is an uncountable set $V\subseteq\omega_1$ such that $|f(\beta)|\lt n$ for all $\beta\in V$. Now consider the graph $G$ with vertex set $V$ and edge set $E=\{\{\alpha,\beta\}:\alpha\lt\beta\text{ and }\alpha\in f(\beta)\}$. You can easily show (by transfinite induction) that the graph $G$ is $n$-colorable, i.e., the vertex set $V$ is the union of $n$ independent sets; so there is an uncountable independent set $W\subseteq V$. For each $\beta\in W$, the set $f(\beta)\cap W$ contains only ordinals greater than (or equal to) $\beta$. Now it's easy to see that there is an uncountable free set $S\subseteq W$.

Answer 3

Here is a proof using the Erdős-Rado partition theorem $\omega_1\to(\omega+1,\,\omega_1)^2$, or rather its corollary $\omega_1\to(\omega+1,\,\omega,\,\omega_1)^2$. For $\alpha,\beta\in\omega_1,\,\alpha\lt\beta$, put the pair $\{\alpha,\beta\}$ in $C_1$ if $\alpha\in f(\beta)$, in $C_2$ if $\beta\in f(\alpha)$, in $C_3$ if $\alpha\notin f(\beta)$ and $\beta\notin f(\alpha)$; so $[\omega_1]^2=C_1\cup C_2\cup C_3$. Then there is a set $S\subseteq\omega_1$ such that, writing $\operatorname{tp}S$ for the order type of $S$, either (1) $[S]^2\subseteq C_1$ and $\operatorname{tp}S=\omega+1$, or (2) $[S]^2\subseteq C_2$ and $\operatorname{tp}S=\omega$, or (3) $[S]^2\subseteq C_3$ and $\operatorname{tp}S=\omega_1$. But (1) and (2) are impossible because of the finiteness assumption on $f$, so (3) holds and $S$ is an uncountable free set.