The Delta-System Lemma

colorado_river_delta

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

Zone

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”

  3. Pingback: Special uncountable trees
  4. Pingback: The P-Ideal Dichotomy and the Souslin Hypothesis | Assaf Rinot

Comments are closed.