Show that there are non-well-founded models of Zermelo Fraenkel set theory

Question

I have been working on this problem for several hours, and my understanding just isn't there. Here's what I've gathered:

Using downward Lowenheim-Skolem theorem, we know that any consistent set of sentences has a countable model, and for the sake of this problem we are assuming that ZF is indeed consistent.

The axiom of foundation in ZF seems to eliminate the possibility that there is a non-well-founded model, because it says that there is no infinitely descending membership sequence.

I believe I may need to employ compactness in the approach. Not sure what I need to proceed. TIA

Answer 1

Add constant symbols $c_0,c_1,c_2,\dots,c_n,\dots$ to the language of set theory. Let $\sf T$ be the theory obtained by adding sentences $c_1\in c_0,c_2\in c_1,\dots,c_{n+1}\in c_n,\dots$ to the $\sf{ZF}$ axioms. If $\sf{ZF}$ is consistent, then every finite subset of $\sf T$ is consistent, and so $\sf T$ is consistent by the compactness theorem. Any model of $\sf T$ is a non-well-founded model of $\sf{ZF}$.

The fact that the axiom of foundation holds in the model does not mean that there is no infinite descending $\in$-sequence of elements of the model, it just means that such an infinite sequence can not itself be an element of the model. The model "thinks" it is well-founded (so to speak), but viewed from outside it is not well-founded. Of course the $\in$ relation of the model is not real set-membership (at least if we assume that infinite descending $\in$-sequences do not exist in "the real world").

Answer 2

Of course that we need to assume that $\sf ZFC$ is consistent for these arguments, since if there are no models of $\sf ZFC$, then all the models are well-founded.

The usual answer is given by compactness, as bof writes in a very good answer. Here is a different argument, which relies on absoluteness and incompleteness (or well-foundedness, the last remark) instead.

---

The idea is that if $(M,\in)$ is a well-founded (and without loss of generality, transitive) model of $\sf ZFC$, then $V$ and $M$ agree on arithmetic statements, in particular they agree on what are the rules of first-order logic, the axioms $\sf ZFC$ have, and whether or not these axioms are consistent. Since $V$ is aware of $M$ being a model of $\sf ZFC$, it means that every well-founded model of $\sf ZFC$ must also agree that $\sf ZFC$ is consistent and has a model.

But by the incompleteness theorem we know that $\sf ZFC$ cannot possibly prove that it is consistent, so there must be a model $(N,E)$ which thinks that $\sf ZFC$ is inconsistent, and by the above it cannot be well-founded.

Caveats.

1. When we talk about $\sf ZFC$ being consistent as an arithmetic statement, we mean that there is a recursively definable predicate on the natural numbers which encodes the axioms of $\sf ZFC$. So when I say that $V$ and $M$ agree on what is first-order logic and what are the axioms of $\sf ZFC$, I mean that they interpret that predicate in the same way.

   Of course, the model which thinks that $\sf ZFC$ is inconsistent will have non-standard integers, which means that he will think that $\sf ZFC$ is a larger theory and includes more axioms than it really has and the logic will have more inference rules and longer proofs, which is where the contradiction comes from.

2. The absoluteness argument shows that in fact if $N$ is non-well founded but still agrees on what $\omega$ might be (this is called an $\omega$-model), then $N$ still agrees on what is $\sf ZFC$ and whether or not it is consistent.

   So the existence of $\omega$-models is itself stronger than just the existence of models of $\sf ZFC$. But it is weaker than the existence of transitive models, since those can be non-well founded.

3. You can get the model $N$ using well-foundedness instead. Order the transitive models of $\sf ZFC$ by $\in$, since it's a non-empty class (otherwise all models are non-well founded; or there are no models at all) it has a minimal element, $M$. But now $M$ agrees that $\sf ZFC$ is consistent, so there is some $(N,E)\in M$ such that $M\models(N,E)\text{ is a model of }\sf ZFC$. Now we know the fact that the satisfaction relation is absolute between transitive models, $(N,E)$ is a model of $\sf ZFC$. But since $M$ was a minimal transitive model, $N$ cannot be transitive.

Answer 3

This is really the compactness argument, but disguised as an ultrapower instead.

Let $U$ be any ultrafilter on $\omega$ extending the cofinite filter (a.k.a. the Fréchet filter), let $(M, \epsilon)$ be any model of ZFC, and let $(M^U, \epsilon^U)$ be the ultrapower of $(M, \epsilon)$ with respect to $U$. For each $n \in \omega$, let $n^M$ be the corresponding element of $M$. Define the following sequences $x_n : \omega \to M$: $$x_n (i) = \begin{cases} 0 & i < n \\ (i - n)^M & i \ge n \end{cases}$$ By construction, if $m < n$, then $[x_n] \mathrel{\epsilon^U} [x_m]$, because the set of $i$ such that $x_n (i) \mathrel{\epsilon} x_m (i)$ is cofinite. Thus, we have an infinite descending sequence $$\cdots \mathrel{\epsilon^U} [x_2] \mathrel{\epsilon^U} [x_1] \mathrel{\epsilon^U} [x_0]$$ and in particular $\epsilon^U$ is not well founded.

Of course, $(M^U, \epsilon^U)$ is also a model of ZFC, because it is elementarily equivalent to $(M, \epsilon)$. In particular, $(M^U, \epsilon^U)$ believes itself to be well founded, so that must imply there is no element $[y]$ of $M^U$ such that $[x] \mathrel{\epsilon^U} [y]$ if and only if $[x] = [x_n]$ for some $n \in \omega$. This highlights the subtle difference between sets inside the model and sets outside the model.

Answer 4

You can get this directly from the incompleteness theorem, without compactness. Let $M$ be a model of $\text{ZFC} + \lnot\text{Con}(\text{ZFC})$.

Then:

1) $\omega^M$ is a model of Peano arithmetic, because ZFC proves that $\omega$ satisfies each axioms of Peano arithmetic.

2) $\omega^M$ is not the standard model of Peano arithmetic, because $\omega^M$ satisfies $\lnot\text{Con}(\text{ZFC})$, and the standard model does not.

3) $\omega^M$ is not well founded, because no nonstandard model of Peano arithmetic is well founded. If $x$ is a nonstandard element, then in particular it is a successor, and it follows that there is an infinite decreasing sequence of predecessors beginning at $x$.