MathOverflow is a question and answer site for professional mathematicians. 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 usual language and axioms of ZF. Now add constants $x_1, x_2, \dots$ to the language together with the axioms $x_2\in x_1, x_3\in x_2, \dots$ to form a new theory. Then by the compactness theorem, since every finite subset of the axioms has a model, the new theory has a model. But doesn't the set {$x_1, x_2, \dots$} have no $\in$-minimal element, contradicting the axiom of foundation?

I'm thinking that maybe {$x_1, x_2, \dots$} is not necessarily a set in the model, but isn't it by replacement? Maybe not, since we don't necessarily have a copy of $\mathbb{N}$ in our model... Could someone clarify this please?

share|cite|improve this question
up vote 10 down vote accepted

You have already answered your question yourself: the set $\{x_1, x_2, \ldots\}$ cannot exist in the model, since this would violate the Foundation Axiom. You cannot get this set from Replacement, since there is no definable function having this set as its range, required to invoke the Replacement Axiom.

What you have done is exactly to prove that if ZF is consistent, then there are non-wellfounded models of set theory. Your proof is one way to justify nonstandard analysis.

Note that the ordinals of any model of your theory will have a non-wellfounded collection of ordinals, since the Levy rank of the sets x_n will be decreasing.

share|cite|improve this answer
Actually, two questions: Isn't any set of ordinals wellfounded? What is the Levy rank (googled it, didn't find it)? – Randomblue Apr 6 '10 at 18:26
The model thinks its ordinals are well-founded, of course, but externally, they are not. This is the essence of nonstandardness. The Levy rank of a set x is the smallest ordinal alpha such that x is in V_alpha. If x is an element of y, then the rank of x is strictly smaller than the rank of y, so your sets give rise to a decreasing sequence of ordinals of the model. But the model does not, and cannot have this sequence, since it thinks its own ordinals are well-ordered. – Joel David Hamkins Apr 6 '10 at 18:35
I went in and fixed some TeX. At issue is that Markdown, which processes the page before jsMath gets to it, thinks that { is a special character, and that \{ is what you'd type to escape it. So Markdown dutifully strips off the ` but does no further processing to the {` before passing the text to the webbrowser. Then jsMath (which runs in the browser) comes along and sees just an open brace, so ignores it when rendering the code as LaTeX. There are two fixes: either use \\{, which looks bad in TeX, or protect any string of code by back-ticks, so that Markdown knows that it's code. – Theo Johnson-Freyd Apr 6 '10 at 20:23
Theo, thanks for fixing that. Actually, jsmath doesn't work for me at all on most of the machines I use regularly, and my usual MO experience is to be looking at a lot of $'s and \'s, which I don't really like. I suspect that a significant but silent fraction of the MO user population is in my situation, and that MO should discourage excessive TeX usage for this reason. – Joel David Hamkins Apr 6 '10 at 20:31
You can also write \lbrace and \rbrace instead of \\{, for example $\lbrace x \mid x \not\in x\rbrace$. – Andrej Bauer Apr 6 '10 at 22:43

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.