Does $E$ in a model $\langle M, E\rangle$ of ZFC have to be wellfounded?

Question

Consider the following exercise from Just/Weese:

My first reaction was "Of course $E$ has to be strictly wellfounded otherwise it wouldn't model $\in$" but apparently I am missing something since I don't see why I should use Theorem 2.2:

Also, the exercise is rated "difficult" -- so: what is the correct answer? Thanks for your help!

Answer 1

This is basically fleshing out some ideas from Brian's comment. (But I must admit that I forget exactly where things are introduced in Just-Weese.)

The ZFC counterpart to "$\in$ is strictly wellfounded" is the Axiom of Foundation (or Regularity), expressed as follows: $$( \forall x ) ( x \neq \varnothing \rightarrow ( \exists z ) ( z \in x \wedge z \cap x = \emptyset ) ).$$ This says that every nonempty set $x$ has an element $z$ disjoint from it (and therefore there is no element of $x$ which is below $z$ in the $\in$-order).

Therefore, using the correspondence between elements of $M$ and (certain) subsets of $M$ (as described in a previous question) we see that given any $a \in M$ the subset $$\{ b \in M : b \mathrel{E} a \}$$ has an $E$-minimal element.

However, as noted in that previous question, not all subsets of $M$ correspond to elements of $M$, and you cannot use the fact that $\langle M, E \rangle$ satisfies the Axiom of Foundation to say that those subsets which do not correspond to elements of $M$ have $E$-minimal elements.

Indeed, introduce to the language of set theory countably many new constants $c_0 , c_1 , \ldots$, and add to ZFC all sentences of the form $c_{n+1} \in c_n$ to get a new theory $T$. Now proceed as follows:

1. Assuming that ZFC is consistent, prove that $T$ is also consistent. (Use Compactness.)
2. Show that if $\langle M , E, c_0 , c_1 , \ldots \rangle \models T$, then $E$ is not strictly well-founded.

(I'll leave the details for you.)

Answer 2

Of course that $E$ does not have to be well-founded. The decreasing sequence cannot be a member of $M$, though. In such case the $M$ does not know that $E$ is not well-founded.

For example, suppose that $\langle N,\in\rangle$ is a model of ZFC and $U$ is a free ultrafilter over $\omega$. Let $\langle M,E\rangle$ be the ultraproduct of $\langle N,\in\rangle$ by the ultrafilter $U$. By Los theorem $\langle M,E\rangle$ has to be a model of ZFC.

Namely $M=N^\omega/U$, and if $f\colon\omega\to N$ then $[f]_U = \{g\colon\omega\to N\mid f\equiv_U g\}$, where $f\equiv_U g\iff\{n\in\omega\mid f(n)=g(n)\}\in U$. And $E=\{\langle [f],[g]\rangle\mid f\in_U g\}$, where $f\in_U g\iff\{n\in\omega\mid f(n)\in g(n)\}\in U$.

Now I claim that $E$ is not well-founded. Let $f_n(k)=\max\{0,k-n\}$ (namely, $n$ zeros, and then start writing the natural numbers). I claim that $f_{n+1}\mathrel E f_n$ for all $n$, but that is obvious because on a final segment $f_{n+1}(k)=k-n-1\in k-n=f_n(k)$, therefore $\langle [f_n]\mid n\in\omega\rangle$ is a sequence showing that $E$ is not well-founded. This sequence, however, is not an element of $M$ (nor corresponds to one).