The Delta-System Lemma

This is a delta system of rivers. I didn't know this until last year.

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 \sse [\omega_1]^{<\omega}$ with $B$ uncountable. Then there is an uncountable $A \sse 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 \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 \sse [\omega_1]^{<\omega}$ with $B$ uncountable. There is a countable $N \sse \omega_1$ such that every $b \in B$, with $b \not \sse N$ is contained in an uncountable $\Delta$-system $A \sse B$ with root $r \sse 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<\delta$, $$V \models r \sse b \wedge b \setminus r \neq \emptyset \wedge min(b\setminus r) > \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: $$V \models \exists x \in B \color{grey}{(r \sse 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: $$M \models \exists x \in B \color{grey}{(r \sse x \wedge x \setminus r \neq \emptyset \wedge min(x\setminus r) > \alpha)}$$

(Magic time)

Remember we let $\alpha < \delta$ be arbitrary so: $$M \models \forall \alpha < \delta (\exists x \in B) \color{grey}{(r \sse x \wedge x \setminus r \neq \emptyset \wedge min(x\setminus r) > \alpha)}$$

(Yeah, so what?)

Well recall that $\delta = M \cap \omega_1$, so infact: $$M \models \forall \alpha < \omega_1 (\exists x \in B) \color{grey}{(r \sse x \wedge x \setminus r \neq \emptyset \wedge min(x\setminus r) > \alpha)}$$

So now because $M$ is an elementary submodel of set theory, $$V \models \forall \alpha < \omega_1 (\exists x \in B) \color{grey}{(r \sse x \wedge x \setminus r \neq \emptyset \wedge min(x\setminus r) > \alpha)}$$

So it is true that for any $\alpha<\omega_1$ there is an $x\in B$ such that $r \sse x$, $x \setminus r \neq \emptyset$ and $min(x\setminus r) > \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$”.

Thanks Elementarity!

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

Here is the more elementary basic proof of the lemma: Let $B \sse [\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.

This entry was posted in Full Article, Uncategorized and tagged , , , , . Bookmark the permalink. Both comments and trackbacks are currently closed.

2 Comments

  1. saf
    Posted February 12, 2012 at 8:36 pm | Permalink

    Sweet!

  2. Carl Mummert
    Posted February 13, 2012 at 11:20 pm | Permalink

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

2 Trackbacks

  • By Special uncountable trees on February 23, 2012 at 11:50 pm

    […] we assume the reader is familiar with the $Delta$-system lemma, outlined in Mike’s post here, a standard tool for showing posets are […]

  • […] then let $B$ be an uncountable subset of $omega_1$ for which ${ x_betamid betain B}$ forms a $Delta$-system with root $r$. As the sets in ${ (x_betasetminus r)mid  betain B}$ are mutually disjoint, […]