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.

17 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 homogeneous 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$?

    • 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$.

  4. Shir Sivroni says:

    In the second part of the induction step:
    If $|\mathcal A_\tau| < \kappa$ can't we just define a regressive function $f:\mathcal A\rightarrow\kappa$ where $f(A) = \min(A)$?
    And then, by fodor's Lemma and the regularity of $\kappa$, 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.

  5. Isaac Gorelic says:

    Actually, there is an easier proof (of the Induction step): Either we have a disjoint system of size $\kappa$, or take any maximal disjoint system and some point in its union will belong to $\kappa$ many (other) members of $\mathcal A$ (that’s where the regularity of $\kappa$ is needed).

  6. Carlos López says:

    Hi Assaf,

    Do you know if there is any Ramsey-type theorem that has as consequence the delta system lemma?

    Thanks.

    • saf says:

      Hi Carlos,

      Indeed. Given $\mathcal A\subseteq[\kappa]^n$, for each $a\in\mathcal A$, let $\langle a(i)\mid i<n\rangle$ denote the increasing enumeration of the elements of $a$. Let us also fix some well-ordering $\lhd$ of $\mathcal A$. Now define a coloring $c:[\mathcal A]^2\rightarrow\mathcal P(n)$ by letting $c(a,b):=\{ i<n\mid a(i)\in b\}$ for all $a\lhd b$ from $\mathcal A$. Let us observe that any $\mathcal B\subseteq\mathcal A$ that is $c$-homogeneous will form a $\Delta$-system. Indeed, if $c$ is constant over $\mathcal B$ with value, say, $I$, and $a$ denotes its $\lhd$-least element, consider the set $r:=\{ a(i)\mid i\in I\}$.
      Now, given any set $b$ in $\mathcal B$ that is distinct from $a$, since $c(a,b)=I$, it is the case that $r=a\cap b$. Therefore, $r\subseteq\bigcap\mathcal B$. In addition, for all $x\neq y$ from $\mathcal B$, $|x\cap y|=|c(x,y)|=|I|=|r|$, so, in fact, $x\cap y=r$.

Leave a Reply

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