A Practical Guide to Using Countable Elementary Submodels

doll-house

So, you may have heard about these things called countable elementary submodels. You may have heard that they work like magic and do all sorts of amazing things. “Mathematical voodoo” some might say. “Witchcraft!” others declare. Hearing this you become intrigued and set out to harness this black power. You quickly realize that there are very few places to learn this dark art; the protectors of this knowledge don’t want it leaking out.

Here I hope to lay out the essential things you need to know (and omit the things you don’t need to know) so that you can start using countable elementary submodels. I am going to lay out as little of the machinery as possible and display only the relevant applicable facts you will need for most proofs involving elementary submodels.

1. A Countable Submodel of What?

The universe of all sets $V$ is a ‘model’ for set theory, but it is too big. If we did have a model for set theory we would know that there is a countable submodel of it, by Lowenheim-Skolem. Of course we can’t assert that set theory has a model as this would be equivalent to asserting the consistency of set theory. The clever way around this is to realize that any proof in mathematics only ever uses finitely many axioms of set theory and references only finitely many specific sets. It is always possible to find a model $H$ of those finitely many axioms and special sets. (Aside, for those of you who have seen this before, why doesn’t this violate the compactness theorem? It’s tricky.) Here $H$ will be our copy of the universe, just for a given proof, and we will take a countable submodel of $H$ , not $V$ . This is where the language “Take a large enough fragment of ZFC” comes from.

As it turns out there is a class of sets that we usually draw $H$ from. We usually take $H$ to be a set $H(\alpha)$ , where $\alpha$ is a cardinal and $H(\alpha)$ is the set of all sets hereditarily of cardinality less than $\alpha$ . This doesn’t really matter at all. So don’t fret about this.

2. What does the word ‘elementary’ in CESM mean?

A submodel $M$ of $H$ is an elementary submodel (denoted $M \prec H$ ) if any statement true in $H$ is true in $M$ (given that we have relatavized the statement to $M$ ). Basically, if $H$ and $M$ have the same language and we can express a statement in that language it should be true in $H$ iff it is true in $M$ . Relativizing a statement to $M$ means that we only quantify over things in $M$ , not all of $H$ . Also, we are not allowed to reference things outside of $M$ .

For example, as dense linear orders $M := \mathbb{Q} \cap (0, \infty) \prec \mathbb{Q}$ . We know that in $\mathbb{Q}$ the following statement $\phi$ is true:
$\displaystyle (\forall x)( \exists y )[x<y]$
Well what convention did we just use? We just assumed that the $\forall$ only quantifies over rational numbers (and not say over complex numbers, or sets). Relatavizing this statement to $\mathbb{Q} \cap (0, \infty)$ we see that it is also true, and now the statement $\phi^M$ is
$\displaystyle (\forall x \in \mathbb{Q} \cap (0, \infty))( \exists y \in \mathbb{Q} \cap (0, \infty))[x<y]$
Notationally we say $\mathbb{Q} \models \phi$ and $\mathbb{Q} \cap (0, \infty) \models \phi$ . (See Chris Eagle’s comment below)

Basically relativizing makes sure that a model can actually say something about the statement.

3. What does it mean for a model to “think something is true”?

Saying that $M$ thinks that a statement $\phi$ is true is simply shorthand for $M \models \phi$ . So what? First of all we get paradoxical conclusions like $M \models 2^\omega$ is uncountable. How can this be because $M$ is countable?

Well, a model thinks that $2^\omega$ is uncountable because all of the injective functions $f: \mathbb{N} \rightarrow 2^\omega$ that are in $M$ are not onto. So even though $M$ actually has only countably many elements of $2 ^\omega$ , the model also doesn’t have any way to check that. Even though from the outside we see that there is a bijection $f: \mathbb{N} \rightarrow 2^\omega$ , this function is not in $M$ .

The thing to be careful about here is that $M$ ‘s copy of $2^\omega$ is not the real copy of $2^\omega$ . (How could it be?! $M$ ‘s copy has only countably many elements!)

4. How do I determine when something is in $M$ ?

SUPER USEFUL FACT: Any set definable from parameters in $M$ is actually a member of $M$ .

Remember that sets in $M$ sometimes have the form $\{x \in M : \phi(x_1, x_2)\}$ where $x_1, x_2$ are free variables in the statement $\phi$ . If the objects in $\phi$ are all in $M$ , then $\phi$ is definable from parameters in $M$ .

For example, back in $\mathbb{Q} \cap (0, \infty) \prec \mathbb{Q}$ , $\{x : x<-1\}$ is definable in $\mathbb{Q}$ , but not in $\mathbb{Q} \cap (0, \infty)$ .

This is kind of like super useful fact from forcing that asserts that I am allowed to define sets in the ground model even if I use the forcing symbol in definition, so long as all the other parameters are in the ground model.

5. What is the big difference between $A \in M$ and $A \subseteq M$ ?

During a proof using CESM you will be using the super useful fact over and over. Why does it matter? Think about how sets work with respect to set operations (Power set, intersection, union, image of a function, etc.). In that case you want to know that applying these operations to a set will produce a set. In symbols, $A\in V$ asserts that $A$ is a set, but $A \subseteq V$ does not assert that. For example the class of all ordinals ON $``\subseteq" V$ and is not a set, so we can’t do things like take $\mathcal{P}(\textbf{ON})$ .

If $A \in M$ then the model “knows about A” and we can use the super useful fact.

6. What is the really important thing I need to know about finite and countable subsets of $M$ ?

For sets of small cardinality sometimes we automatically get information about them.

FACT: Any finite subset of $M$ is actually a member of $M$ .

FACT: Any countable member of $M$ is actually a subset of $M$ .

7. What are the really important things I need to know about ordinals?

Many theorems using CESM start of by considering $M \cap \omega_1 := \delta$ .

FACT 1: $\delta$ is a countable ordinal. That is, $\delta \in \omega_1$ .

FACT 2: If $A\in M$ , $A\subseteq \omega_1$ and $\delta \in A$ then $A$ is a stationary set in $\omega_1$ . In particular, $A$ is uncountable.

Moreover we get the folowing (quite general) fact:

Assaf’s FACT: If $A\in M$ and there exists some $x\in A$ which is not in $M$ , then $A$ is uncountable.

Proof. Recall that any countable $A\in M$ is also a subset of $M$ .

What else?

This should give you the basics that you need to know in order to read a proof using CESM. For more information about CESM see chapter 24 in Just & Weese’s book “Discovering Modern Set Theory; Volume 2”. I hope that this was helpful and please let me know if there is anything that needs changing.

Next week I will tackle two proofs using CESM.

7 thoughts on “A Practical Guide to Using Countable Elementary Submodels”

saf says:

January 26, 2012 at 6:13 pm

Very nice, Mike!
You pointed out that if $M$ is CESM, $A\in M$ and $M\cap\omega_1\in A$ , then $A$ is stationary. Since $M\cap\omega_1$ is not in $M$ , I think it is worth also mentioning the following useful fact:
Fact. If $M$ is CESM, $A\in M$ and there exists some $x\in A$ which is not in $M$ , then $A$ is uncountable.
Proof. Recall that any countable $A\in M$ is also a subset of $M$ .

LikeLike
Samuel Coskey says:

February 1, 2012 at 2:09 pm

This is pretty sweet. I hope all the graduate students (and in my case, former graduate students) in set theory out there find it useful!

LikeLike
Peter Krautzberger says:

February 3, 2012 at 1:13 pm

Excellent piece!

LikeLike
Chris Eagle says:

February 4, 2012 at 11:17 pm

Hey Mike,

It’s very handy to have the useful facts all in one place! The thing I mentioned to you the other day is that in section 2, it isn’t technically true that $\mathbb{Q} \cap (0, \infty) \models \phi^M$ . For one thing, $\phi^M$ includes symbols for which $\mathbb{Q} \cap (0, \infty)$ doesn’t have an interpretation, namely $\in$ (assuming that you intended the underlying language of orderings to only have the symbol $<$ ). What is true is that $\mathbb{Q} \cap (0, \infty) \models \phi$ , since any quantifier (in any formula) is always interpreted as ranging over the elements of whatever structure you're in when you interpret it.

What is almost true is that $\phi^M$ is true (in $V$ ) if and only if $(M, \in) \models \phi$ , where $\in$ here denotes the "real" membership relation. I say "almost" because formally the definition of structures requires them to have universes which are sets, and hence $(M, \in) \models \phi$ only makes sense if $M$ is a set, whereas $\phi^M$ makes sense even if $M$ is a proper class.

I hope that made sense. Thanks again for the useful post!

LikeLike
Pingback: c.c.c. forcing without combinatorics | Assaf Rinot
Pingback: The Delta-System Lemma
Pingback: Stevo’s Forcing Class Fall 2012 – Class 9