How can there be genuine models of set theory?

Question

I know that this a beginner's question asked too many times, but I still didn't get an answer which lets me quit asking:

Given that a model/interpretation of a theory (in the Tarskian sense) is a set with some structure, how can there be models of set theory, since we know, that the class of all sets (the range of the quantifiers of set theory) is not a set?

I especially wonder why

a) it is stressed so often and so strongly that models must be sets?

b) nevertheless sometimes proper classes are allowed? (see Wikipedia's Inner Model Theory: "models are transitive subsets or subclasses")

Answer 1

I especially wonder why

a) it is stressed so often and so strongly that models must be sets?

There are several reasons why model theory texts only look at models that are sets. These reasons are all related to the fact that model theory is itself studied using some (usually informal) set theory.

One benefit of sticking with set-sized models is this makes it possible to perform algebraic operations on models, such as taking products and ultrapowers, without any set-theoretic worries.

Another benefit of requiring models to be sets is this makes it possible to define the satisfaction relation $\vDash$ for each model. In other words, given a model $M$ in a language $L(M)$, we want to form $T(M) = \{ \phi \in L(M) : M \vDash \phi\}$. This can be done when $M$ is a set, by going through Skolem normal form. But it cannot be done, in general, when $M$ is a proper class, because of Tarski's undefinability theorem. In particular, if we let $M$ be the class-sized model $V$ of the language of set theory then Tarski's theorem shows that $T(M)$ is not definable in $V$. We can define the truth of each individual formula (using the formula itself) but in general there may be no global definition of truth in a proper-class-sized model.

Moreover, in model theory, there is no real need to look at proper-class-sized models, because there is already enough interesting behavior from set-sized models. The motivating examples are all sets (algebraic structures, partial orders, etc). And the completeness theorem shows that any consistent theory has a set-sized model (this includes ZFC). So model theorists generally restrict themselves to set-sized models.

b) nevertheless sometimes proper classes are allowed?

Generally, people are only interested in proper-class-sized models in the context of set theory. The reason for the interest is that ZFC can't prove that there is a set model of ZFC (because ZFC can't prove Con(ZFC)), but it is possible to form proper-class-sized models of ZFC from a given proper-class-sized model of ZFC (e.g. the inner model $L$). This allows for some model-theoretic results about set theory, but many things that are taken for granted in model theory have to be re-checked when we move to proper-class-sized models. In general the re-checking is often routine, and it only comes up in advanced settings, where an author is not likely to make a big fuss about it. The benefit of this labor is that we can sometimes avoid having to assume Con(ZFC) as a hypothesis for a theorem about models of set theory.

In summary, in any non-set-theoretic context, "model" will mean "set-sized model". In the context of set theory, this is still what "model" usually means; they usually say "inner model" or "class model" for a proper-class-sized model. But some attention to context is needed when you are working with "models" of set theory to make sure you read what the author intended.

Answer 2

This is a question I wonder about too! I made this CW because I'm not sure this constitutes a satisfactory answer, and I do not attempt to answer questions $(a)$ and $(b)$.

Suppose you have a model of set theory $(U,\in_0)$ : this allows you to define $\subset_0$ inclusion of sets and products of sets $A\times_0 B$, intersections $\cap_0$ etc$\dots$ in the sense of $\in_0$. One illuminating way to picture $(U,\in_0)$ is as an infinite oriented graph (Théorie des Ensembles by J.-L. Krivine takes that stance).

If $M$ is a model of set theory (that is $M$ is a set of $U$, i.e. a point in the infinite graph $U$, with a binary relation $\in_M\subset_0 M\times_0 M$, another point in the infinite graph $U$, that together obey all the axioms of $\mathsf{ZF}$), the interpretation $\in_M$ of the binary relation $\in$ of the language of $\mathsf{ZF}$ need not be the same as $\in_0$ : it may be (maybe it has to be) that $\in_M\neq (M\times_0 M)\cap_0\in_0$.

Anyway, sets in the model $(M,\in_M)$ are by definition the $\in_0$ elements of $M$. Since by foundation $M\notin_0 M$, $M$ is not a set in the sense of $\in_M$, that is, $M$ is not a set in the model $(M,\in_M)$. So the $(U,\in_0)$ set $M$ constitutes the class of sets of the model $(M,\in_M)$, yet it is not a set in that new model.

I think this boils down to "sets in one model need not be sets in another".

Answer 3

Some comments. The basic distinction you need to make is between the external and internal notions of set. Let me take as granted a primitive and unspecified notion of set: this will be our external notion of set. For any first-order theory $T$ in a language $L$, a model of $T$ is a set (in this external sense) equipped with functions and relations satisfying the appropriate axioms, etc. In particular, a model of, say, ZFC is a set $M$ equipped with a binary relation satisfying etc. etc.

(Requiring that models themselves be sets is likely a matter of convenience. In category theory this requirement can be restrictive, and one way to get around it is the notion of a Grothendieck universe. But I won't say more about this; it isn't central to your misunderstanding.)

Now the elements $m \in M$ of a model of set theory are themselves supposed to be interpreted as sets, but the word "set" here means something different: it is an internal notion specified by $T$ (and $L$). To prevent confusion here it would really be best to replace "set" with some other word, such as "foo." Thus we should speak of foo theory and the class of all foos, which is not a foo. (A class is just an external subset of $M$ specified by some formula.)

When we say that the class of all sets is not a set, what we mean is that there does not exist an element of $M$ which contains all other elements of $M$ (by the axiom of regularity). We don't mean that $M$ is itself not an external set, because it is by definition an external set.

I believe the Wikipedia article on inner models is talking about internal classes (which are still just elements of $M$, an external set), but I'm not sure.

One last thing: ZFC is not capable of provably exhibiting a model of ZFC (since this proves that ZFC is consistent) unless it is inconsistent by the incompleteness theorem.

Answer 4

The use of the word ‘genuine’ the question title makes me wonder if there are also ‘fake’ models of set theory. There are various candidates. Let us say that a model of set theory is standard just if the $\in$ relation of that model corresponds exactly to the $\in$ relation of the universe we are working in. Otherwise, we say the model is non-standard.

Do standard models exist? Well, the answer depends on various technical points. For a start, if a consistent set theory $T$ is powerful enough to interpret arithmetic, then Gödel's incompleteness theorem tells us that $T$ cannot prove that there is a set model of $T$, either standard or non-standard. This is because a proof of the existence of such a model would imply that $T$ proves its own consistency. (On the other hand, if our universe obeys the axioms of $T$, it obviously does contain a standard class model of $T$, namely itself.) Suppose instead that we are working in a universe which satisfies the axioms of a different set theory $T'$. (Yes, there are inequivalent set theories!) Could we then prove the existence of a standard set model of some (necessarily weaker) set theory $T$? Sometimes, yes: for example, from the axioms of ZFC we can prove that there is a standard set model for Zermelo set theory, namely $V_{\omega + \omega}$. This can also be turned into a model for Lawvere's elementary theory of the category of sets (ETCS), which is equivalent to a variant of Zermelo set theory where the axiom of separation is restricted to predicates with bounded quantifiers.

As mentioned in the comments, if $T'$ is ZFC augmented with a suitable large cardinal axiom, then it will be provable from $T'$ that there is a standard set model of ZFC. This is not so mysterious when you think about it. Let us define the rank of a set inductively as follows: the rank of $\emptyset$ is $0$; if $x$ has rank $\alpha$, then $\mathcal{P}(x)$ has rank $\alpha + 1$; and in general the rank of $x$ is the least ordinal number greater than the ranks of all its members. By structural induction, every set has a rank, and it is not hard to show that the rank of a von Neumann ordinal $\alpha$ is again $\alpha$. This immediately implies that a collection of sets of unbounded rank cannot be a set. So if a set $M$ is a standard model of ZFC, it can only contain the ordinals less than its rank. But $M$ must contain every set that ZFC can prove to exist, and so that means our universe must contain ordinals, and hence, cardinals, the existence of which is not guaranteed by ZFC. [But does every large cardinal axiom imply the existence of such a standard model $M$?]

What about non-standard models? Well, things are a lot easier here. For example, Gödel's completeness theorem tells us that if a first-order theory $T$ is consistent, then there is a set model for it. Moreover, if $T$ is a theory over a countable language, then the downward Löwenheim–Skolem theorem tells us that $T$ has a countable model. It is useful to contemplate what this means when $T$ is a set theory, because it forces us to be absolutely clear about the distinction between the universe the model lives in and the universe inside the model. So let $M$ be a countable model of set theory. Since $M$ is countable, we may as well assume it is $\mathbb{N}$. So how can the set of natural numbers be a model of set theory? Well, the key is that $M$ is equipped with a relation $\in_M$ as well. In effect, what we are doing is indexing the sets (but not ‘all’ of them!) by natural numbers, and $\in_M$ is tracking their membership relations. Because $M$ is a model of set theory, it contains a set of natural numbers $\mathbb{N}_M$. It is not hard to show that the internal structure of $\mathbb{N}_M$, according to $\in_M$, corresponds exactly to the internal structure of the ‘genuine’ $\mathbb{N}$. (Well, with some added consistency assumptions.) And of course there is a power set $\mathcal{P}_M(\mathbb{N}_M)$, which according to $M$ is uncountable. Obviously, $\mathcal{P}_M(\mathbb{N}_M)$ is ‘actually’ countable, because $M$ is. How can this be? Well, if we look at how $M$ is constructed, we notice that $M$ is only required to have the sets that must be there. But since the language of set theory is only countable, we can only name countably many sets, and in particular $\mathcal{P}_M(\mathbb{N}_M)$ only contains those subsets of $\mathbb{N}_M$ which necessarily ‘exist’. Similarly, since set theory proves that there is no bijection between $\mathbb{N}$ and its power set, there cannot be any such bijection inside $M$, even though the sets are ‘actually’ equinumerous. (To be precise, even though we can see externally that there ought to be a bijection, the graph of any bijection we can dream up will fail to be a set in $M$.)

Perhaps the moral to take away from all this is that the universe of sets is a subtle beast to be treated with care.