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

  • 1
    $\begingroup$ 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? $\endgroup$ – Rudy the Reindeer Apr 15 '13 at 15:25
  • $\begingroup$ @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? $\endgroup$ – Lord_Farin Apr 15 '13 at 15:41
  • $\begingroup$ No, sorry, I don't. $\endgroup$ – Rudy the Reindeer Apr 15 '13 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.

  • 1
    $\begingroup$ Thank you; your argument sparked the necessary insight. $\endgroup$ – Lord_Farin Apr 15 '13 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.