Well Ordering Principle, Zorn's Lemma, Induction, etc.

Question

I know there are plenty of proofs online that show Induction implies well ordering, well ordering implies induction, zorn's lemma implies induction, etc. and what I seem to be getting is that in most courses professors introduce these by assuming one and proving the others from it, but is there an accessible proof of one that does not assume the others and is self-contained? I don't seem to be finding any. I hate the idea that you more or less have to assume one because the proof of any one of them without using the others is too unaccessible to undergraduate students. Thanks!

Answer 1

It's not that the proof of any one of them without the others is inaccessible; it's that there isn't one. Asking for a proof of Zorn's Lemma without depending on the Well-Ordering Principle (or something similar) is a lot like asking for a proof that even numbers $>2$ are composite without making use of the fact that even numbers are divisible by $2$; it can't be done. Zorn's Lemma is simply not true in a universe in which Well-Ordering fails, and there are mathematical "universes" in which exactly this happens.

In Zermelo-Frankel set theory, all three of these principles are equivalent to the Axiom of Choice, which is an additional axiom that is independent of the other axioms. Most people wouldn't say that Zorn's Lemma/Well-Ordering/induction are "axiomatic", but they are equivalent to an axiom. A proof of each one from the Axiom of Choice is fairly straightforward, but Well-Ordering is easiest to prove.

Answer 2

All three are variations of the Axiom of Choice: https://en.wikipedia.org/wiki/Axiom_of_choice

There is no ultimate proof because it is an independent axiom.

Answer 3

One needs to start from somewhere.

You some some axioms to prove that $0\neq 1$, because syntactically speaking these are just two constant symbols without any meaning to them. Once you start with some context—some axioms, or structure—then you can prove or disprove that $0\neq 1$ depending on your context.

In set theory, naively we work in a theory which has some semblance to $\sf ZF$ with or without choice. But choice is not very "obvious" or "naive" anymore. And we motivate it by proving the following theorem:

The following are equivalent over $\sf ZF$:

1. The Axiom of Choice;
2. Every set can be well-ordered;
3. Zorn's Lemma.

(And there are many other variants and equivalents which you might have met.)

But to prove three things are equivalent, we first assume the first and prove the second; then assume the second and prove the third; and finally assume the third and prove the first.

So to your question, you cannot prove Zorn's lemma without assuming the axiom of choice, in one way or another. This is just how mathematics work. And their equivalence show that assuming one is the same as assuming any of them. So either one can be taken as your axiom, in which case you could prove the rest.

Answer 4

There are 3 well known equivalent statements:

1. Axiom of choice
2. Zorn's lemma
3. Well ordering principle

Further, there is a tool of the set theory which does not require any of these, it is called transfinite recursion.

But I see these three "equivalent" statements a bit differently. Of course, they are equivalent, but you do not need anything advanced (I mean transfinite recursion, ordinals, etc.) to prove 1 from 2 or from 3. On the other hand, you need the transfinite recursion for proving 2 or 3 from 1. Moreover, 1 is really intuitive, there is a reason why to consider it as an axiom.

So in my view, 2 and 3 are just theorems of set theory which can be proved using the axiom of choice (as well as other axioms) and the transfinite recursion. And these two theorems happened to be so strong and general that they can prove each other and the original axiom.