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!

  • 3
    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$?2012-11-21
  • 1
    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.2012-11-21
  • 0
    @ZhenLin But _externally_ would be the real $\in$, not $E$, right?2012-11-21
  • 0
    @BrianM.Scott Then $E$ is not wellfounded and is therefore not a model of ZFC?2012-11-21
  • 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.)

  • 1
    @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...)2012-11-21
  • 1
    (...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...)2012-11-21
  • 1
    (...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$.2012-11-21
  • 0
    Dear @Arthur, thank you so much for your patience! I finally understand what I was confused about.2012-11-21
  • 0
    The answer to the exercise is basically Brian's comment: No, $E$ does not have to be a wellfounded relation on $M$. We can have $f: \omega \to M$ as in Brian's comment. But $\mathrm{im}f$ (which is a subset of $M$) is not necessarily an element of $M$ and the elements of $M$ are the things that model things.2012-11-21
  • 1
    @Matt: Yes, exactly. The answers of both Asaf and myself contained explicit methods of "constructing" such models of ZFC and such functions.2012-11-21
  • 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).