$$ \text{Axiom of Choice $\Rightarrow$ Zorn's Lemma } $$ $$\text{Axiom of Choice $\Leftarrow$ Zorn's Lemma } $$ I feel mathmatically immature to go through these proofs now. My quesiton therefore is:
Is there an intuitive way/example/ausiliary proof/exercise to grasp their being-the-sameness?

(I have seen many questions regarding this topic but could not find one quite like mine, so, if it exists, just link it and I will delete this one.)

  • 1
    $\begingroup$ There is a third player in the game, that every (say non-empty) set can be well-ordered. Call this assertion WO. My intuition is that WO is fairly naturally equivalent to AC, and fairly naturally equivalent to Zorn's Lemma. $\endgroup$ – André Nicolas Mar 18 '14 at 12:39
  • $\begingroup$ Sorry can you be a bit clearer on the role of well ordering or give a link about its role on the matter. Thank you. $\endgroup$ – Rgkpdx Mar 18 '14 at 12:50
  • $\begingroup$ Sorry, no time for link searching, and certainly no time to sketch the proofs. $\endgroup$ – André Nicolas Mar 18 '14 at 12:54

The intuition is that both give the existence of an intangible object.

The axiom of choice gives us a choice function, which is a way to choose an element from each set of a certain family; whereas Zorn's lemma gives us the existence of a maximal element, given the partial order satisfies some property.

The idea behind the proof is not very difficult if you are familiar with how are functions represented in set theory, and with transfinite recursion (which requires you to be at least a little bit comfortable around ordinals).

Assuming the axiom of choice, we essentially traverse the partial order in search for a maximal element. The choice function is a guide on how to proceed at each step. And we can prove that it is impossible that we never find a maximal element.

Assuming Zorn's lemma, and given some family of non-empty sets, we consider the partial order of partial choice functions (functions which choose from a subfamily) ordered by extension (or set inclusion). We can quite easily prove that this partial order satisfies the condition for Zorn's lemma, and a maximal element is necessarily a choice function itself.

As Andre noted, and in fact much more, there are many, many equivalents to the axiom of choice. Wherever intangible objects come into play, the axiom of choice is likely to be found, and some equivalent is likely to be formulated.

The most common equivalent is the well-ordering principle. We say that a linear order is a well-order if every non-empty set has a minimal element. Like the natural numbers. It turns out that the axiom of choice is equivalent to the statement "Every set can be well-ordered", that is to say that for every given set, there is a linear order on that set which is a well-order.


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.