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.

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

  1. The Nile.


    • saf says:

      Indeed, we have $a\cap b\sqsubseteq a$ for all $a,b\in\mathcal B$. I wonder why don’t they call it the $\nabla$-system lemma!


      • When you are looking at it from the Greek side of the globe, it’s really a $\Delta$.


        • saf says:

          According to the convention of drawing ordinals from bottom to up, the equation “$a\cap\delta=a\cap b=b\cap\delta$ for all distinct $a,b\in\mathcal B$” corresponds to $\nabla$.


          • But maybe this notation was conceived by the same people who decided that forcing should go up?

            Halfway backwards sort of approach…

            $\stackrel{\circ\space\circ} {\large\smile}$


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


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

  4. yogut says:

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


    • saf says:

      You can define $g:\kappa\rightarrow\kappa$ by recursion on $\alpha< \kappa$, stipulating that $g(\alpha):=\min\{\tau<\kappa\mid \mathcal A_\tau\neq\emptyset\}\setminus\sup(\bigcup\bigcup\{\mathcal A_i\mid i<\sup(g[\alpha])\})$.
      Since $\kappa$ is regular and $|\mathcal A_i|<\kappa$ for all $i<\kappa$, we have $\sup(\bigcup\bigcup\{\mathcal A_i\mid i<\theta\})<\kappa$ for all $\theta<\kappa$, and hence the function $g$ is well-defined.
      Finally, let $f(\alpha)$ be an arbitrary element of $\mathcal A_{g(\alpha)}$ for all $\alpha<\kappa$.


Leave a Reply

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

nine + 4 =

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>