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 $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$.
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}$
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 homogeneous 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:\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$.
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?
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.
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).
Hi Assaf,
Do you know if there is any Ramsey-type theorem that has as consequence the delta system lemma?
Thanks.
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$.