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

• saf says:

Indeed, we have $acap bsqsubseteq a$ for all $a,binmathcal 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 “$acapdelta=acap b=bcapdelta$ for all distinct $a,binmathcal 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{circspacecirc} {largesmile}$

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. yogut says:

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

• saf says:

You can define $g:kapparightarrowkappa$ by recursion on $alpha 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.