Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 5 down vote accepted

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

share|cite|improve this answer
@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...) – arjafi 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...) – arjafi 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$. – arjafi 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. – arjafi 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).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.