Models of Set Theory

You may have noticed that, when introducing the axioms of $\ZFC$, we never really answered the question “What is a set?” Instead, we developed a formal theory of axioms for a binary relation that somehow describe “how sets work”, that is, how we can obtain sets from given ones using well-known operations like power set and union.

We have then seen how we can develop a lot of standard mathematical objects (like $\Nat$, $\Real$) and techniques (like induction and definition by recursion) inside this formal system. In fact, most of mathematics can be developed formally inside this system. Almost all proofs you find in any standard math book are proofs that can be formalized in $\ZFC$. It is very tedious to do this for us humans, but there is little doubt it can be done, and in fact, looking at the recent work on proof assistants (like Coq or Lean), many parts of mathematics have been formalized (albeit not directly in $\ZFC$).

This expressiveness gives $\ZFC$ its foundational importance, but it is also the cause for much confusion for someone who first studies set theory.

From a pedagogical point of view, in what follows it is helpful to assume a “Platonist” perspective of mathematics, and set theory in particular, namely that sets and the relations between exist independently (and outside) of the $\ZFC$ axioms. The set of real numbers exists, and our development of $\Real$ inside $\ZFC$ is just a formal way to describe them. From this perspective, the axioms of $\ZF$ ($\AC$ is a little different) are just obvious truths about sets, just like the Peano axioms are obvious truths about natural numbers.

Among other things, this perspective allows us to treat $\ZF$ just like any other mathematical theory, like group theory or the theory of algebraically closed fields. In particular, we can think about models of set theory the way we would think about models of group theory, in the sense of model theory.

A model would simply be a set $M$ together with a binary relation $E$ on $S$ such that

that is, all axioms hold when interpreted in $(M,E)$. Note that we use “set” in this context not in the formal sense, but in the “meta”-sense (the Platonist world of sets).

Working in the meta-theory (“that what is mathematically true”), we know by Gödel’s completeness theorem that

if $\ZF$ is consistent, then it has a model.

This model should be seen as a set-theoretic universe: Its elements can be seen as sets, and the interpretation $E$ of the $\in$-symbol will tell us how these sets are connected via the element-relation.

Note that $E$ does not have to be the actual element relation on a set (of sets), but just some binary relation so that the axioms are satisfied.

In the meta-world, there are, of course, sets other than $M$, but that does not matter here, since all we are interested in is giving some universe in which our axioms hold. (Timothy Chow has suggested that set theory should rather be called "universe theory. He is right in the sense that what axiomatic set theory does is to define such universes of sets, rather than what a set is.)

In the meta-theory, we can then follow the usual techniques to show provability or non-provability results.

If we want to prove that $\CH$ is consistent with $\ZF$ (assuming $\ZF$ is consistent), we need to find a model in which both hold.

One difficulty in working with models of set theory is that they can look very different depending on whether you look at a model “from the inside” or “from the outside”.

To illustrate this, assume $\ZF$ is consistent. Then, by the Löwenheim-Skolem theorem, there exists a countable model for $\ZF$. Yet it is a theorem of $\ZF$ that there exists an uncountable set. This is often referred to as Skolem’s paradox, although it is not really an antinomy.

If we break this down a bit, we see that the apparent paradox is really just a matter of perspective (inside or outside). Assume $(M,E)$ is a countable model of $\ZF$. Then there exists $x \in M$ such that there is no injection from $x$ to the natural numbers. Since $M$ is countable, $x$ can have at most countably many elements. So why is this not a contradiction? We should really read the statement above as

there is no injection in $M$ from $x$ to $M$’s version of the natural numbers.

In other words, even though $x$ is countable from the outside, $x$ appears uncountable inside $M$ since a mapping witnessing its countability does not exist in $M$.

This is a first warning sign that models of $\ZF$ can behave in very unexpected ways. For another example, recall the axiom of Foundation asserts that the $\in$-relation is well-founded. But again, this means only “from the inside”.

Since, as mentioned above, the model $(M^*,E^*)$ satisfies Foundation, the set $\{c_n \colon n \in \Nat\}$ is actually not in the model (and neither can be any other set with an infinite descending $\in$-chain).

Mostowski collapse¶

If we restrict ourselves to models on which the $E$-relation is actually well-founded (i.e. from the outside), then interestingly these models look, in a way, “natural”: They can be assumed to be the $\in$-relation on a set. Such models are also called standard.

Given a set theoretic structure $(M,E)$ (not necessarily a model of $\ZF$), for each $x \in M$ let

If $E$ behaves “set-like”, then it will respect the axiom of Extensionality, i.e. two sets are identical if and only if they have the same elements. Therefore we say that $E$ is extensional if

Furthermore, as stated above, we want to exclude infinite descending $E$-chains. Recall we say that $E$ is well-founded if

every non-empty set $Y \subseteq X$ has an $E$-minimal element.

Absoluteness and transitive models¶

Even if we consider well-founded standard models, interpreting set-theoretic statements in them can still lead to very different results, even for very simple formulas.

In the example above, the set $M$ is not transitive, which allowed it to “hide” its elements. It turns out that if we require our model to be transitive, the truth of simple formulas cannot vary between the “inside” and the “outside” perspective. We call such properties absolute.

Given a formula ${}\varphi$ and some class $M$, we can relativize ${}\varphi$ with respect to $M$ essentially by restricting all quantifiers in ${}\varphi$ to range over $M$, i.e. $\exists x$ becomes $\exists x \in M$ and $\forall x$ becomes $\forall x \in M$. Note that classes are defined by formulas, so the resulting formula, which we denote by $\varphi^M$, is still a formula of set theory.

We leave the proof as an exercise.

We can extend the previous absoluteness result to a slightly larger family of formulas.

The absoluteness property of “simple” formulas can be put to use to identify many “almost” models of $\ZF$.

What is the problem with Replacement? The axiom says that if ${}\varphi$ defines a function, then the image of any set under this function is a set. Relativized to some $M$, this means we need to find a set in $M$ that contains the image. Here we run into a cardinality problem. The cardinality of $V_\alpha$ can be much bigger than the cardinality of ${}\alpha$. For example, $\Pow(\omega) \in V_{\omega+\omega}$ but $\omega+\omega$ is countable. We could have a function that maps $\Pow(\omega)$ to sets of rank cofinal in $\omega+\omega$, which implies that the image cannot be in $V_{\omega+\omega}$.

For $V_\alpha$ to be a model, we would need ${}\alpha$ to be “unreachable” by such mappings. This gives rise to the notion of inaccessible cardinals, which we will introduce in the next section.