# The Delta-System Lemma

Now that you know the basics of countable elementary submodels (CESM), you might think that you are in the clear. “Mike”, you say arrogantly, “I know all the most basic properties of CESMs, without proof I remind you, what else could I possibly want?”. I gently and patiently remind you that CESMs are worthless unless you know how to apply them properly.

So let’s do that.

Here are two theorems whose proofs you might already know, but that can be proved using elementary submodels. I will show you a proof of the $\Delta$-system lemma (a fundamental lemma in infinitary combinatorics) and a topological theorem of Arhangel’skii. Both of these proofs are taken from Just & Weese’s book “Discovering Modern Set Theory 2”, chapter 24.

The $\Delta$-system lemma.

This lemma is an extremely useful tool for dealing with uncountable families. It is the tool most often used to show that a partial order has the countable chain condition.

(The $\Delta$-system lemma) Let $B \subseteq [\omega_1]^{<\omega}$ with $B$ uncountable. Then there is an uncountable $A \subseteq B$, and $r \in [\omega_1]^{<\omega}$ such that $\forall a,b \in A, a\cap b = r$.

Here $r$ is called the root, which is a (possibly empty) finite subset of $\omega_1$. The lemma says we can refine any uncountable family of finite subsets of $\omega_1$ so that the elements of the family agree precisely on the root.

Note that the “countable $\Delta$-system lemma” is false. Letting $B := \{\{0,1,2,3, \dots, n\}: n\in \mathbb{N} \}$ is a countable subset of $\omega_1$ such that no finite subset of $\omega_1$ could possibly be a root for any refinement of $B$.

Proof of the $\Delta$-system lemma using CESM. Ok, so we are actually going to show something a little bit stronger.

(Lemma) Let $B \subseteq [\omega_1]^{<\omega}$ with $B$ uncountable. There is a countable $N \subseteq \omega_1$ such that every $b \in B$, with $b \not \subseteq N$ is contained in an uncountable $\Delta$-system $A \subseteq B$ with root $r \subseteq N$.

(Whoa, what is this saying?)

(Well it is using the fact that we don’t need to concern ourselves with the countably many finite subsets of $N$, as we can throw those away in the refining process. Now the lemma says that $B$ can be refined to a $\Delta$-system. What about this condition that $N$ is a countable subset of $\omega_1$? It doesn’t really matter.)

To the proof of the lemma!

Let $M$ be a CESM of set theory with $B\in M$. Now let $N := M \cap \omega_1$, which we know is a countable ordinal, $\delta$. This $N = \delta$ will turn out to satisfy the conditions of the lemma.

Note that $\exists b\in B$ such that $b \not\subseteq N$, because $B$ is uncountable but $N$ is countable. We define $r:= b \cap N$, and this will turn out to be the root of an uncountable $\Delta$-system that is contained in $B$.
So for any given $\alpha \alpha$

In order to use the elementarity of $M$ we change that statement to include an existential quantifier instead of refering to $b$, which isn’t in $M$. Remember that $M$ cannot refer to things that are outside of it:
$\displaystyle V \models \exists x \in B {(r \subseteq x \wedge x \setminus r \neq \emptyset \wedge \min(x\setminus r) > \alpha)}$

(We use elementarity now)

The statement above references only things in $M$, so by elementarity, we must have:
$\displaystyle M \models \exists x \in B {(r \subseteq x \wedge x \setminus r \neq \emptyset \wedge \min(x\setminus r) > \alpha)}$

(Magic time)

Remember we let $\alpha < \delta$ be arbitrary so:
$\displaystyle M \models \forall \alpha \alpha)}$

(Yeah, so what?)

Well recall that $\delta = M \cap \omega_1$, so infact:
$\displaystyle M \models \forall \alpha \alpha)}$

So now because $M$ is an elementary submodel of set theory,
$\displaystyle V \models \forall \alpha \alpha)}$

So it is true that for any $\alpha \alpha)$. From here we can easily construct an uncountable sequence of elements in $B$ with root $r$. [QED]

Did you notice how important it was that $M \cap \omega_1$ was a countable ordinal? Because of that we were able to find an element of $B$ sufficiently far out in $\omega_1$ that agrees with the root. We did this using only the fact that countable < uncountable.

Nothing fancy at all!

The unsettling part here is that we found this $b$ that was larger than both $\alpha$ and $M$'s copy of $\omega_1$ which was $\delta$. Then elementarity said: "Finding a $b$ further than $\alpha$ was the important part, I don't care that it was bigger than $M$'s $\omega_1$ as long as this $b$ is less than the real $\omega_1$; I'll take care of making it less than $M$'s $\omega_1$". We did that, but we ended up only finding b's that were greater than countably many $\alpha$. Elementarity jumps in with "Don't worry, checking it for the countably many $\alpha< \delta$ is fine, I'll make sure it works for all $\alpha<\omega_1$".

A more standard proof of the $\Delta$-system lemma.

Here is the more elementary basic proof of the lemma: Let $B \subseteq [\omega_1]^{<\omega}$ with $B$ uncountable. Since $B = \bigcup_{n<\omega} [\omega_1]^n$, there is an $N$ such that $B_1 := B \cap [\omega_1]^N$.

(We reduced to the case where all elements of $B$ have the same length).

We now prove the lemma by induction on $N$.

If $N=1$ it is clear that $B_1$ itself is a $\Delta$-system with root $r = \emptyset$.

Suppose the statement is true for $N=k$. Write $B_1 = \{ A_{\alpha}\cup\{x_\alpha\}: \alpha < \omega_1\}$, with each $A_\alpha$ having cardinality $k$. We would like to apply the induction hypothesis to $B_2 := \{A_\alpha : \alpha<\omega_1\}$, which could only happen if $B_2$ was uncountable. (If it was countable, then there are uncountably many elements of $B_1$ that all share the same $A_\alpha$, then all of the $x_\alpha$ must be different, so we have our uncountable $\Delta$-system which is a subset of $B_1$).

Now suppose $B_2$ is uncountable. Apply the induction hypothesis to $B_2$ to get $B_3 = \{C_\alpha \cup \{y_\alpha\}: \alpha < \omega_1\}$. (Here we are just changing the 'A's to 'C's and 'x's to 'y's as we have taken a refinement). Now $\{y_\alpha: \alpha<\omega_1\}$ is either countable (in which there are uncountably many $C_\alpha$ that share the same $y$, so we can add that $y$ to the root).

Otherwise if $\{y_\alpha: \alpha<\omega_1\}$ is uncountable…

You get the idea. The point being that this proof is just a lot of refining and using the pigeonhole principle.

It is interesting to note that Stevo Todorcevic insists that these two proofs of the $\Delta$-system are the "wrong" ones. He is convinced that the right one is the Ramsey-Theory tree proof.

Looks like I've written a lot already and will get to the topological proof later.

## 4 thoughts on “The Delta-System Lemma”

1. saf says:

Sweet!

Like

2. Carl Mummert says:

I’m interested to see the result by Arkhangel’skii you alluded to.

Like