# Proving the $\Delta$ lemma using Fodor's Theorem

Presently trying to solve Exercise $9.10$ from Jech's Set Theory (3rd Millenium edition):

Prove [the $\Delta$ lemma] using Fodor's Theorem.

which contains the following mysterious hint:

Let $W = \{X_\alpha: \alpha < \omega_1\}$ with $X_\alpha \subset \omega_1$. For each $\alpha$, let $f(\alpha) = X_\alpha \cap \alpha$. By Fodor's Theorem, $f$ is constant on a stationary set $S$; by induction construct a $\Delta$-system $W \subset \{X_\alpha: \alpha \in S\}.$

Recall the $\Delta$ lemma:

An uncountable collection $W$ of finite sets has an uncountable subset $Z$ such that for some fixed $S$, for all distinct $X, Y \in Z$, one has $X \cap Y = S$.

and Fodor's Theorem:

An ordinal-valued mapping $f$ on a stationary set $S \subseteq \kappa$ with the property that $f(\alpha)<\alpha$ for $\alpha > 0$, is constant on some stationary subset $T \subseteq S$.

Normally, I find the exercises in Jech quite doable -- sometimes the hints are rather superfluous. But in this case I struggle to see even what the global direction of the hint is.

I do get that we may restrict attention to $W$ as given (because it is WLOG of cardinality $\aleph_1$, whence there are only $\aleph_1$ different elements in $\bigcup W$; by AC we may embed both $W$ and $\bigcup W$ in $\omega_1$).

Any hints on what is meant with the second sentence are appreciated ($f$ seems not to define an ordinal-valued function to me).

• The function as defined does not only not map into the ordinals but also does not satisfy $f(\alpha) < \alpha$. It seems easy to fix though: define $f(\alpha) = \bigcup (X_\alpha \cap \alpha)$. Perhaps the definition as given is a typo in the book. Have you checked out any available lists of typos? Apr 15, 2013 at 15:25
• @Matt A good suggestion; I haven't been able to find any errata using obvious web search. Do you happen to know where I can find such lists? Apr 15, 2013 at 15:41
• No, sorry, I don't. Apr 15, 2013 at 16:35

Suppose $\langle W_{\alpha} : \alpha < \omega_1 \rangle$ is an $\omega_1$-sequence of finite subsets of $\omega_1$. WLOG, we can assume that size of each $W_{\alpha}$ is $n$ for some $n \geq 1$. By induction on $n$, we'll construct a $\Delta$-subsequence of length $\omega_1$. If $n = 1$, this is easy. So assume $n \geq 2$. Consider the function $f: \omega_1 \rightarrow \omega_1 \cup \{\infty\}$ defined by $f(\alpha) =$ least element of $W_{\alpha}$ below $\alpha$ (if any), otherwise $\infty$. If $f(\alpha) = \infty$ on uncountably many $\alpha$'s then we can very easily find a pairwise disjoint subsequence of $W_{\alpha}$'s which is therefore a $\Delta$-sequence with empty root. If not, by Fodor's lemma there is a stationary subsequence on which $f$ is constant, say $\beta$. But then $\beta \in W_{\alpha}$ for uncountably many $\alpha$'s and we apply inductive hypothesis to these $W_{\alpha} \backslash \{\beta\}$'s.