I try to prove that every ordinal number $(\alpha,\in)$ is well-ordered, where an ordinal number is defined as a transitive $\in$-linearly ordered set.

So all I have to show is, that every non-empty subset of $\alpha$ has an $\in$-minimal element. That follows quite simple by axiom of foundation, but how can I prove this without foundation?

  • $\begingroup$ Don't you need foundation for this definition of ordinal to work? $\endgroup$ – Henno Brandsma Jun 17 '16 at 16:34
  • $\begingroup$ See en.wikipedia.org/wiki/…, under "other definitions", which assumes regularity (foundation) for the equivalence. $\endgroup$ – Henno Brandsma Jun 17 '16 at 16:36
  • $\begingroup$ @Henno: I guess I do need foundation to receive an equivalent definition to yours. Just consider it to be a transitive and linearly ordered set then without calling it ordinal. $\endgroup$ – E. Noether Jun 17 '16 at 16:41

There's a good reason you're having trouble - this is not provable without Foundation: it is consistent with $ZFC^-$ (that is, $ZFC$ without Foundation) that there is a sequence of sets $a_i$ ($i\in\omega$) such that $a_i=\{a_j: j>i\}$. Then $a_0$ is transitive and linearly ordered by "$\in$," but is clearly not well-ordered by "$\in$".

The existence of such a sequence is a consequence of Boffa's Antifoundation Axiom. This axiom is less popular than Aczel's Antifoundation Axiom (AFA), and it seems harder to get a good exposition of it. If you can read French, Boffa's original paper is http://www.ams.org/mathscinet-getitem?mr=476514; otherwise section 1 of the paper Standard foundations for nonstandard analysis has a good exposition.

I suspect that AFA also provides counterexamples to your claim. However, this is a bit trickier; in fact, AFA disproves the existence of the counterexample I describe above! (In AFA we have $a_0=a_1=...$, so the result is a singleton - a (in fact, the) Quine atom.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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