3
$\begingroup$

Consider the following exercise from Just/Weese:

enter image description here

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:

enter image description here

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

  • 0
    @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.2012-11-21

2 Answers 2

5

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

  • 0
    I think it's worth adding that strictly well-founded models are *precisely* the models isomorphic to some transitive models (and in particular, any transitive model of $ZFC$ is strictly well founded). See [Mostowski's collapse lemma](http://en.wikipedia.org/wiki/Mostowski_collapse).2012-11-22
5

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