“The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn’s lemma?” — Jerry Bona This is a joke: although the three are all mathematically equivalent, many mathematicians find the axiom of choice to be intuitive, the well-ordering principle to be counterintuitive, and Zorn’s lemma to be too complex for any intuition.
It might be worth saying explicitly what these three (equivalent) axioms say.
Axiom of choice: if you have a set A of nonempty sets, then there’s a function that maps each element a of A to an element of a. (I.e., a way of choosing one element f(a) from each set a in A.)
Well-ordering principle: every set can be well-ordered: that is, you can put a (total) ordering on it with the property that there are no infinite descending sequences. E.g., < is a well-ordering on the positive integers but not on all the integers, but you can replace it with an ordering where 0 < −1 < 1 < −2 < 2 < −3 < 3 < −4 < 4 < … which is a well-ordering. The well-ordering principle implies, e.g., that there’s a well-ordering on the real numbers, or the set of sets of real numbers.
Zorn’s lemma: if you have a partially ordered set, and every subset of it on which the partial order is actually total has an upper bound, then the whole thing has a maximal element.
The best way to explain what Zorn’s lemma is saying is to give an example, so let me show that Zorn’s lemma implies the (“obviously false”) well-ordering principle. Let A be any set. We’ll try to find a well-ordering of it. Let O be the set of well-orderings of subsets of A. Given two of these—say, o1 and o2 -- say that o1 ⇐ o2 if o2 is an “extension” of o1 -- that is, o2 is a well-ordering of a superset of whatever o1 is a well-ordering of, and o1 and o2 agree where both are defined. Now, this satisfies the condition in Zorn’s lemma: if you have a subset of O on which ⇐ is a total order, this means that for any two things in the subset one is an extension of the other, and then the union of all of them is an upper bound. So if Zorn’s lemma is true then O has a maximal element, i.e. a well-ordering of some subset of A that extends every possible well-ordering of any subset of A. Call this W. Now W must actually be defined on the whole of A, because for every element a of A there’s a “trivial” well-ordering of {a}, and W must extend this, which requires a to be in W’s domain.
(A few bits of terminology that I didn’t digress to define above. A total ordering on a set is a relation < for which if a<b and b<c then a<c, and for which exactly one of a<b, b<a, a=b holds for any a,b. OR a relation ⇐ for which if a<=b and b<=c then a<=c, and for which for any a,b either a<=b or b<=a, and for which a<=b and b<=a imply a=b. A partial ordering is similar except that you’re allowed to have pairs for which a<b and b<a (OR: a<=b and b<=a) both fail. We can translate between the “<” versions and the “<=” versions: “<” means “<= but not =”, or “<=” means “< or =”. Given a partial ordering, an upper bound for a set A is an element b for which a<=b for every a in A. A maximal element in a partially ordered set is an element of the set that’s an upper bound for the whole set.)
Framing effect in math:
It might be worth saying explicitly what these three (equivalent) axioms say.
Axiom of choice: if you have a set A of nonempty sets, then there’s a function that maps each element a of A to an element of a. (I.e., a way of choosing one element f(a) from each set a in A.)
Well-ordering principle: every set can be well-ordered: that is, you can put a (total) ordering on it with the property that there are no infinite descending sequences. E.g., < is a well-ordering on the positive integers but not on all the integers, but you can replace it with an ordering where 0 < −1 < 1 < −2 < 2 < −3 < 3 < −4 < 4 < … which is a well-ordering. The well-ordering principle implies, e.g., that there’s a well-ordering on the real numbers, or the set of sets of real numbers.
Zorn’s lemma: if you have a partially ordered set, and every subset of it on which the partial order is actually total has an upper bound, then the whole thing has a maximal element.
The best way to explain what Zorn’s lemma is saying is to give an example, so let me show that Zorn’s lemma implies the (“obviously false”) well-ordering principle. Let A be any set. We’ll try to find a well-ordering of it. Let O be the set of well-orderings of subsets of A. Given two of these—say, o1 and o2 -- say that o1 ⇐ o2 if o2 is an “extension” of o1 -- that is, o2 is a well-ordering of a superset of whatever o1 is a well-ordering of, and o1 and o2 agree where both are defined. Now, this satisfies the condition in Zorn’s lemma: if you have a subset of O on which ⇐ is a total order, this means that for any two things in the subset one is an extension of the other, and then the union of all of them is an upper bound. So if Zorn’s lemma is true then O has a maximal element, i.e. a well-ordering of some subset of A that extends every possible well-ordering of any subset of A. Call this W. Now W must actually be defined on the whole of A, because for every element a of A there’s a “trivial” well-ordering of {a}, and W must extend this, which requires a to be in W’s domain.
(A few bits of terminology that I didn’t digress to define above. A total ordering on a set is a relation < for which if a<b and b<c then a<c, and for which exactly one of a<b, b<a, a=b holds for any a,b. OR a relation ⇐ for which if a<=b and b<=c then a<=c, and for which for any a,b either a<=b or b<=a, and for which a<=b and b<=a imply a=b. A partial ordering is similar except that you’re allowed to have pairs for which a<b and b<a (OR: a<=b and b<=a) both fail. We can translate between the “<” versions and the “<=” versions: “<” means “<= but not =”, or “<=” means “< or =”. Given a partial ordering, an upper bound for a set A is an element b for which a<=b for every a in A. A maximal element in a partially ordered set is an element of the set that’s an upper bound for the whole set.)