The $\Delta$-system lemma: an elementary proof

Here is an elementary proof of (the finitary version of) the $\Delta$-system lemma. Thanks goes to Bill Weiss who showed me this proof!

Lemma. Suppose that $\kappa$ is a regular uncountable cardinal, and $\mathcal A$ is a $\kappa$-sized family of finite sets.
Then there exists a subcollection $\mathcal B\subseteq\mathcal A$ of size $\kappa$, together with a finite set $r$, such that $a\cap b=r$ for all distinct $a,b\in\mathcal B$.

Proof. Without loss of generality $\mathcal A\subseteq[\kappa]^{<\omega}$. Since $\kappa$ has uncountable cofinality, we may find a positive integer $n$ and $\mathcal A’\subseteq\mathcal A$ of size $\kappa$ such that $\mathcal A’\subseteq[\kappa]^n$. Thus, it suffices to prove the next statement: for every positive integer $n$ and every $\mathcal A\subseteq[\kappa]^{n}$ of size $\kappa$, there exists a subfamily $\mathcal B\subseteq\mathcal A$ of size $\kappa$, and an ordinal $\delta<\kappa$ such that $$a\cap\delta=a\cap b=b\cap\delta\text{ for all distinct }a,b\in\mathcal B.$$

The proof is by induction.

Induction base: The case $\mathcal A\subseteq[\kappa]^1$ is witnessed by $\mathcal B:=\mathcal A$ and $\delta:=0$.

Induction step: Suppose that $n$ is a positive integer, and that the assertion holds for $n$. Given $\mathcal A\subseteq[\kappa]^{n+1}$ of size $\kappa$, we consider two cases:

  • If there exists $\tau<\kappa$ such that $\mathcal A_\tau:=\{ a\in\mathcal A\mid \tau=\min(a)\}$ has size $\kappa$, then by the hypothesis, we may find $\mathcal B_\tau\subseteq\{ a\setminus\{\tau\}\mid a\in\mathcal A_\tau\}$ of size $\kappa$, and an ordinal $\delta_\tau$ such that $a\cap\delta_\tau=a\cap b=b\cap\delta_\tau$ for all $a,b\in\mathcal B_\tau$.
    Then, $\mathcal B:=\{ b\cup\{\tau\}\mid b\in\mathcal B_\tau\}$, and $\delta:=\delta_\tau\cup(\tau+1)$ are as needed.
  • If $|\mathcal A_\tau|<\kappa$ for all $\tau<\kappa$, then utilizing the regularity of $\kappa$, we can recursively construct a mapping $f:\kappa\rightarrow\mathcal A$ such that $(\bigcup f[\alpha])\subseteq \min(f(\alpha))$ for all $\alpha<\kappa$.
    Then, $\mathcal B:=f[\kappa]$ and $\delta:=0$ are as desired.

This completes the proof. $\square$

Bonus question: what’s the relation between the assertion we just proved by induction and the stunning photo above?

This entry was posted in Blog, Expository, Surprisingly short. Bookmark the permalink.

14 Responses to The $\Delta$-system lemma: an elementary proof

  1. This seems to be the proof in Shelah’s proper forcing book. Congratulations on the Bar-Ilan position, by the way.

    • saf says:

      Thanks, Andres.

      I see! Well, the first proof I’ve ever seen to this lemma was given in Gitik’s course in Tel-Aviv, following Hrbacek and Jech; their proof involves iterative applications of the pressing-down lemma. The other proof I know is the elementary submodel proof, which morally is the same as pressing-down. Thus, the above proof-by-induction came to me as a surprise!

      At some point, I thought it may be possible to find another proof that builds on the fact that $omega^{omega_1}$ is separable, yielding a color-by-type map $psi:[omega_1]^{<omega}rightarrow V_omega$ in a way that an homogenous set corresponds to a delta-system. However, a counting argument shows that this is impossible.

      • Henno Brandsma says:

        Isn’t this the proof used in Kunen’s “set theory” book? This I think predates Shelah’s book as well.

        • saf says:

          Thank you, Henno!
          The proof in Kunen’s book is for the general case of $Delta$-systems, and hence not of this form. However, you are right – Exercise 1 from Chapter II suggests the above proof.

  2. Pingback: An L-space from a syndetic coloring and a universal binary sequence | Assaf Rinot

  3. yogut says:

    It is a silly question but how do you construct the function $f$?

  4. Shir Sivroni says:

    In the second part of the induction step:
    If $|mathcal A_tau| < k$ can't we just define a regressive function $f:mathcal A rightarrow k$ where $f(A) = min(A)$?
    And then, by fodor's Lemma and the regularity of $k$, we get to the first part of the induction step?

    • saf says:

      The domain of $f$ is the (rather sparse) set $mathcal A$, so, while you can still think of $f$ as being regressive, the (generalized) Fodor lemma fails in this setup.

Leave a Reply

Your email address will not be published. Required fields are marked *