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

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!

-
What if there’s a function $f:\omega\to M$ such that $\langle f(n+1),f(n)\rangle\in E$ for each $n\in\omega$ that has no counterpart in $\langle M,E\rangle$? –  Brian M. Scott Nov 21 '12 at 11:04
What's the definition of "strictly wellfounded"? It is easy to produce non-standard models of ZFC in which there are externally infinite descending chains. –  Zhen Lin Nov 21 '12 at 11:38
@ZhenLin But externally would be the real $\in$, not $E$, right? –  Rudy the Reindeer Nov 21 '12 at 12:57
@BrianM.Scott Then $E$ is not wellfounded and is therefore not a model of ZFC? –  Rudy the Reindeer Nov 21 '12 at 13:16
@BrianM.Scott Now after reading Arthur's comments and answer a few times: Then nothing. $\mathrm{im}f$ is a subset of $M$ but not an element of $M$. And the elements of $M$ are the things in the model. –  Rudy the Reindeer Nov 21 '12 at 15:17

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.)

-
@Matt: I'm quite confused by your comment. If $\langle M , E \rangle \models \text{“}\mathord{\in} \text{ is strictly well-founded”}$ this means (in a common façon de parler) that $M$ thinks that $E$ is strictly well-founded. But in order to determine what this actually means we must translate "$\in$ is strictly well-founded" into the language of set theory. Doing this naively gives us something like $$( \forall x ) ( x \notin x ) \wedge ( \forall x ) ( ( \exists y ) ( y \in x ) \rightarrow ( \exists y ) ( y \in x \wedge ( \forall z ) ( z \in x \rightarrow z \notin y ) )).$$ (cont...) –  Arthur Fischer Nov 21 '12 at 14:57
(...inued) Now if $\langle M , E \rangle$ models the above sentence, this means that given any $a \in M$ we must have that $a \not\mathrel{E} a$ (so $E$ is irreflexive). Also, given $a \in M$ if $b \mathrel{E} a$ holds for some $b \in M$, then there is a $b \in M$ such that $b \mathrel{E} a$ and $c \not\mathrel{E} b$ for any $c \in M$ such that $c \mathrel{E} a$. (cont...) –  Arthur Fischer Nov 21 '12 at 14:58
(...inued) In the manner described in my answer (and originating in your previous question), this means that given any $a \in M$, if the set $\{ b \in M : b \mathrel{E} a \}$ is nonempty, then this set has an $E$-minimal element. But, again, this does not mean that every nonempty subset of $M$ has an $E$-minimal element. And it has absolutely nothing to do with how the real $\in$-relation looks with respect to the set $M$. –  Arthur Fischer Nov 21 '12 at 14:58
Dear @Arthur, thank you so much for your patience! I finally understand what I was confused about. –  Rudy the Reindeer Nov 21 '12 at 15:17
@Matt: Yes, exactly. The answers of both Asaf and myself contained explicit methods of "constructing" such models of ZFC and such functions. –  Arthur Fischer Nov 21 '12 at 15:23

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).

-