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 -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 -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 -system lemma) Let with uncountable. Then there is an uncountable , and such that .
Here is called the root, which is a (possibly empty) finite subset of . The lemma says we can refine any uncountable family of finite subsets of so that the elements of the family agree precisely on the root.
Note that the “countable -system lemma” is false. Letting is a countable subset of such that no finite subset of could possibly be a root for any refinement of .
Proof of the -system lemma using CESM. Ok, so we are actually going to show something a little bit stronger.
(Lemma) Let with uncountable. There is a countable such that every , with is contained in an uncountable -system with root .
(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 , as we can throw those away in the refining process. Now the lemma says that can be refined to a -system. What about this condition that is a countable subset of ? It doesn’t really matter.)
To the proof of the lemma!
Let be a CESM of set theory with . Now let , which we know is a countable ordinal, . This will turn out to satisfy the conditions of the lemma.
Note that such that , because is uncountable but is countable. We define , and this will turn out to be the root of an uncountable -system that is contained in .
So for any given ,
In order to use the elementarity of we change that statement to include an existential quantifier instead of refering to , which isn’t in . Remember that cannot refer to things that are outside of it:
(We use elementarity now)
The statement above references only things in , so by elementarity, we must have:
Remember we let be arbitrary so:
(Yeah, so what?)
Well recall that , so infact:
So now because is an elementary submodel of set theory,
So it is true that for any there is an such that , and . From here we can easily construct an uncountable sequence of elements in with root . [QED]
Did you notice how important it was that was a countable ordinal? Because of that we were able to find an element of sufficiently far out in 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 that was larger than both and ‘s copy of which was . Then elementarity said: “Finding a further than was the important part, I don’t care that it was bigger than ‘s as long as this is less than the real ; I’ll take care of making it less than ‘s “. We did that, but we ended up only finding b’s that were greater than countably many . Elementarity jumps in with “Don’t worry, checking it for the countably many is fine, I’ll make sure it works for all “.
A more standard proof of the -system lemma.
Here is the more
elementary basic proof of the lemma: Let with uncountable. Since , there is an such that .
(We reduced to the case where all elements of have the same length).
We now prove the lemma by induction on .
If it is clear that itself is a -system with root .
Suppose the statement is true for . Write , with each having cardinality . We would like to apply the induction hypothesis to , which could only happen if was uncountable. (If it was countable, then there are uncountably many elements of that all share the same , then all of the must be different, so we have our uncountable -system which is a subset of ).
Now suppose is uncountable. Apply the induction hypothesis to to get . (Here we are just changing the ‘A’s to ‘C’s and ‘x’s to ‘y’s as we have taken a refinement). Now is either countable (in which there are uncountably many that share the same , so we can add that to the root).
Otherwise if 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 -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.