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?

The Nile.

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

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

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

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.

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

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.

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

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

You can define $g:kapparightarrowkappa$ by recursion on $alpha

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?

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.