Towards forcing: Non-well-founded models of Foundation

(An earlier version of this had a terribly false statement about transitive models of ZF. It has been fixed.)

My goal with the next few posts is to present one of my favorite forcing arguments:

Let \mathbb{C}_\omega be the \omega-product of the Cohen forcing \mathbb{C} with full support. Forcing with \mathbb{C}_\omega collapses the reals.

We need a fair bit of background to get there. Instead of dumping a bunch of unmotivated information about forcing and collapsing cardinals on you just to get this one result, I’m going to take a more circuitous route and see some cool things along the way. Today, we’re talking about models of set theory. In particular:

(Assuming ZF is consistent,) there are non-well-founded models of ZF.

If you’re familiar with the ZF axioms, this may seem strange, since the axiom of foundation seems to say that the universe is well-founded. A bit of model theory will show us what’s going on.

A brief technical point: for all of the posts “Towards forcing”, the metasystem is ZF, so a theorem like “All foos are bar” really means ZF\models \text{"all foos are bar"}. This distinction may seem pedantic, but it does become important when discussing models of set theory. Since we’re discussing the model theory of ZF, using ZF as the metasystem brings certain technical problems: we cannot prove in ZF that ZF has any models. There are lots of ways around this; the easy (albeit unsatisfying) way is: Assume ZF is consistent. From here on, I’ll leave this implicit most of the time, so our theorem “all foos are bar” should be read ZF\models Con(ZF)\Rightarrow \text{"all foos are bar"}.

If you haven’t studied much logic or set theory, I may be starting to lose you. So let’s back up a bit: what’s a “model of set theory” anyway? First,

Definition. A relational structure is a set U together with a binary relation R^{V}\subseteq U\times U.

The idea is that a “set theory” will be a set of rules governing a binary relation; ZF, for example is simply such a set of rules. A model of set theory is a relational structure: a set which represents the universe, together with the relation we consider membership. Of course, there are certain things we expect from sets, certain axioms we expect our membership relation to satisfy.

In order to talk about a “theory”, we need these axioms to be properties of the theory, rather than properties of the model; that is, they need to be first order. A first-order property is one which can be written as a (set of) first order formulas. A formula is first order if it only uses variables, logical symbols (\wedge, \forall, etc.) and whatever “extra symbols” we’ve added to our language. In this case, our only extra symbol is R. Then, given a (first order) formula \varphi, we can interpret \varphi in a structure (V,R^V) by replacing a quantifier \forall x with \forall x\in V, and replacing the symbol R with the relation R^V, to get a statement which the structure either satisfies or doesn’t.

With a first order theory, anything which has meaning “in the theory” can be interpreted in the same way as a formula.. For example, if I can define some set S in ZF, then in any model M of ZF (that is, in any relational structure satisfying all the ZF axioms), there is some “set” (object of M) S^M, called the interpretation of S. A convenient intuition is that “M thinks that S^M is S.”

We’ll be very liberal with what is required to call a relational structure a “model of set theory” and only impose the axiom of extensionality:

Definition. A model of set theory is a relational structure (V,\in^V) which satisfies the axiom of extensionality. That is, \forall x,y (\forall z (z\in^V x\leftrightarrow z\in^V y) \leftrightarrow x=y). In English: x is equal to y if and only if z\in^V x precisely when z\in^V y.

This relation \in^V doesn’t have to be “real” membership–it can be anything we like, so long as it’s extensional. Here’s an example: Let the universe be \mathbb{N} and the “membership relation” be the usual ordering <. This is extensional, since for any n,m\in\mathbb{N} we have either n<m or m<n, but not both.

And a non-example: Let V be the Cantor tree (the complete binary tree), and for two vertices u,v, say u\in^V v iff v is a child of u. This is a relational structure, but it's not a model of set theory, since the left and right child of any node have the same "elements".

You’re probably familiar with induction for numbers, and perhaps “structural induction” on, say, the structure of formulas or graphs. Very often you can do induction over a relational structure in much the same way: Given a relational structure (V,R) and a property P, we can prove $\forall x\in V, P(x)$ by proving for each x that (\forall y (yRx\rightarrow P(y))\rightarrow P(x). However, we need to impose a condition called “well-foundedness” on R to avoid “infinite loops”.

Definition. A relational structure (V,R) is called well-founded if for every subset U\subseteq V, there is an element s\subseteq U such that xRs \rightarrow x\not\in U.

If we think of R as being “order-like”, this is just saying that every subset of V has an R-least element. The condition of well-foundedness ensures that there is no infinite descent in V. But notice, we make critical use of V in the definition of well-foundedness. In fact, well-foundedness is not a first order property! In other words, we can’t say “V is well-founded” as an axiom.

To get around this, we need to come up with a local version of well-foundedness. Instead of taking all subsets of V, what if we only take the subsets \{ y : yRx\} for some x? This allows us to write

Definition. The Axiom of Foundation is the formula \forall x (\exists zRx \rightarrow (\exists yRx \forall z (\neg zRy\wedge zRx))). Again in English: For every element x in our structure, if x isn’t “empty”, then x contains an element y “disjoint” from x.

The example structure (\mathbb{N},<) above satisfies the axiom of foundation. In fact, this structure is well-founded. An example which satisfies the axiom of foundation, but isn’t well-founded is the set \mathbb{Z}^- of negative integers, with x\in^{\mathbb{Z}^-}y iff y=x+1 (the predecessor relation). Here, every “set” has exactly one element, which is clearly disjoint from it so foundation is satisfied, but any x\in\mathbb{Z}^- is the successor of some other non-negative integer, so the structure is not well-founded.

From the title of the post, we can stop there, but really, we’re interested in non-well-founded models of ZF, so we have to do a little more work.

A more interesting model of foundation is the structure (V_\omega,\in). If you aren’t familiar with the cumulative hierarchy, V_\omega is the set \{x : x\in \mathcal{P}^n(\emptyset)\text{ for some }n\in\mathbb{N}\}, and \in is the real, actual membership relation (in our metasystem), just restricted to V_\omega. Besides being a model of all ZFC axioms except infinity, this structure has two very interesting properties:

  • V_\omega is a transitive set, meaning that every element v\in V_\omega is a subset of V_\omega.
  • The relation \in is, well, actually the membership relation.

Such models are called transitive models. Transitive models are important because,

Theorem. (Mostowski Collapse). Let (U,R) be an extensional, well-founded relational structure (i.e., a well-founded model of set theory). Then (U,R) is canonically isomorphic to a unique transitive model. (“canonically isomorphic” means there is a unique isomorphism.)

I won’t go into the proof, but the sketch is: Define \varphi:U\rightarrow V (where V is the universe of sets) recursively by \varphi(x)= \{\varphi(y) : yRx\}. Some simple induction (and the axiom of replacement) gives us that the image of \varphi is a transitive set, and the isomorphism follows directly. Uniqueness is proved by induction.

So far, we’ve been talking about models of set theory in general. Now let’s jump all the way to models of ZF: that is, relational structures that satisfy all the ZFC axioms. We can finally prove

Theorem. (If ZF is consistent), then ZF has non-well-founded models.

Proof. Suppose ZF is consistent. If there are no well-founded models then we are done. Otherwise, by Mostowski’s collapse, we may consider only those well-founded models which are transitive. The ordering given by \in on transitive models is well-founded, so we have a minimal transitive model, M.

The interpretation of M internal to M must also be a model of ZF. But it cannot be transitive, as M is the minimal transitive model. That is M^M is a non-well-founded model of ZF.

There are several other ways to prove that ZF has non-well-founded models. Most of them are actually more intuitive, but they don’t hit the points I want to hit.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s