# 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. The Nile.

0 likes

• 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!

0 likes

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

0 likes

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

0 likes

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

0 likes

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

0 likes

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

0 likes

• Henno Brandsma says:

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

0 likes

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

0 likes

3. yogut says:

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

0 likes

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

1 likes

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?

0 likes

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

1 likes