Sketch of The Proof of Zorn's Lemma (from The Axiom of Choice)
A sketch of the proof of Zorn's lemma follows. Suppose the lemma is false. Then there exists a partially ordered set, or poset, P such that every totally ordered subset has an upper bound, and every element has a bigger one. For every totally ordered subset T we may then define a bigger element b(T), because T has an upper bound, and that upper bound has a bigger element. To actually define the function b, we need to employ the axiom of choice.
Using the function b, we are going to define elements a0 < a1 < a2 < a3 < ... in P. This sequence is really long: the indices are not just the natural numbers, but all ordinals. In fact, the sequence is too long for the set P; there are too many ordinals (a proper class), more than there are elements in any set, and the set P will be exhausted before long and then we will run into the desired contradiction.
The ai are defined by transfinite recursion: we pick a0 in P arbitrary (this is possible, since P contains an upper bound for the empty set and is thus not empty) and for any other ordinal w we set aw = b({av: v < w}). Because the av are totally ordered, this is a well-founded definition.
This proof shows that actually a slightly stronger version of Zorn's lemma is true:
If P is a poset in which every well-ordered subset has an upper bound, and if x is any element of P, then P has a maximal element that is greater than or equal to x. That is, there is a maximal element which is comparable to x.Read more about this topic: Zorn's Lemma
Famous quotes containing the words sketch, proof and/or axiom:
“We criticize a man or a book most sharply when we sketch out their ideal.”
—Friedrich Nietzsche (18441900)
“There is no better proof of a mans being truly good than his desiring to be constantly under the observation of good men.”
—François, Duc De La Rochefoucauld (16131680)
“Its an old axiom of mine: marry your enemies and behead your friends.”
—Robert N. Lee. Rowland V. Lee. King Edward IV (Ian Hunter)