Welcome to MathOverflow

Question

4

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?

edited Apr 6 2010 at 18:25

Joel David Hamkins
75k●7●187●343

asked Apr 6 2010 at 18:12

Justin
1,336●3●13●25

Theo Johnson-Freyd · Accepted Answer · 2010-04-06 20:19:49Z UTC

10

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.

edited Apr 6 2010 at 20:19

Theo Johnson-Freyd

answered Apr 6 2010 at 18:22

Joel David Hamkins
75k●7●187●343

Thanks for confirming. – Justin Apr 6 2010 at 18:24

4

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 2010 at 18:35

2

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 2010 at 20:23

1

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 2010 at 20:31

1

You can also write \lbrace and \rbrace instead of \\{, for example $\lbrace x \mid x \not\in x\rbrace$. – Andrej Bauer Apr 6 2010 at 22:43

show 3 more comments

Contradiction to axiom of foundation

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.