[go: up one dir, main page]
Scribd
Upload
30 views2 pages

Zorn

Zorn's lemma is a fundamental result in set theory that states that a partially ordered set in which every chain (totally ordered subset) has an upper bound contains at least one maximal element. The document provides a proof of Zorn's lemma using the concept of a "g-set", which is a well-ordered subset of a partially ordered set where each element is defined in terms of the elements below it. The proof shows that any two g-sets must be comparable, and then constructs a g-set containing all other g-sets to obtain a contradiction.

Uploaded by

Ali Arshad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
30 views2 pages

Zorn

Zorn's lemma is a fundamental result in set theory that states that a partially ordered set in which every chain (totally ordered subset) has an upper bound contains at least one maximal element. The document provides a proof of Zorn's lemma using the concept of a "g-set", which is a well-ordered subset of a partially ordered set where each element is defined in terms of the elements below it. The proof shows that any two g-sets must be comparable, and then constructs a g-set containing all other g-sets to obtain a contradiction.

Uploaded by

Ali Arshad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

ZORN’S LEMMA

DANIEL R. GRAYSON

1. Introduction
Zermelo gave a beautiful proof in [6] that every set can be well ordered, and
Kneser adapted it to give a direct proof of Zorn’s lemma in [3]. Sources such as [4],
[5], [2, p. 63], and most recently, [1], describe this proof, but it still doesn’t seem to
be generally known by mathematicians.

2. The proof
A partially ordered set is a set X equipped with a relation x ≤ y satisfying x ≤ x
and x ≤ y ≤ z ⇒ x ≤ z and x ≤ y ≤ x ⇔ x = y. (The last property is easily
obtained by considering the quotient set for the equivalence relation x ∼ y ⇔ x ≤
y ≤ x.) A totally ordered set is a partially ordered set where x ≤ y ∨ y ≤ x. A well
ordered set is a totally ordered set where every nonempty subset has a minimal
element. A closed subset Y of a partially ordered set X is a subset satisfying
x ≤ y ∈ Y ⇒ x ∈ Y ; we write Y ≤ X, and if Y 6= X, too, then we write Y < X. If
X is well ordered and Y < X, and we take x to be the smallest element of X − Y ,
then Y = {y ∈ X | y < x}.
Lemma 2.1. Suppose X is a partially ordered set, and F is a collection of subsets
S of X. Suppose also that for any C, D ∈ F ,
which are well ordered by the ordering
either C ≤ D or D ≤ C. Let E = C∈F C. Then E is well ordered, and for each
C ∈ F we have C ≤ E.
Theorem 2.2 (Zorn’s lemma). A partially ordered set X with upper bounds for its
well ordered subsets has a maximal element.
Proof. Suppose not. For each well ordered subset C ⊆ X pick an upper bound
g(C) ∈ / C. A well ordered subset C ⊆ X such that c = g({c0 ∈ C | c0 < c}) for
every c ∈ C will be called a g-set.
Intuitively, a g-set C, as far as it goes, is determined by g. For example, if C
starts out with {c0 < c1 < c2 < . . . }, then necessarily c0 = g({}), c1 = g({c0 }),
c2 = g({c0 , c1 }), and so on. A pseudoproof of the theorem might go like this. We
start with an empty collection of g-sets and add larger and larger g-sets to it. At
each stage let W be the union of the g-sets encountered previously. We see that
W 0 = W ∪ {g(W )} is a larger g-set, and we add it to our collection. Continue this
procedure forever and let W be the union of the g-sets encountered along the way;
it’s again a g-set, and we can enlarge it once again, thereby encountering a g-set
that isn’t in our final collection and providing a contradiction. The problem with
this pseudoproof is in interpreting the meaning of “forever”, so now we turn to the
real proof.
Date: January 22, 2007.
1
2 GRAYSON

We claim that if C and D are g-sets, then either C ≤ D or D ≤ C. To see


this, let W be the union of the subsets B ⊆ X satisfying B ≤ C and B ≤ D.
Since a union of closed subsets is closed, we see that W ≤ C and W ≤ D, and
W is the largest subset of X with this property. If W = C or W = D we are
done, so assume W < C and W < D, and pick elements c ∈ C and d ∈ D so that
W = {c0 ∈ C | c0 < c} = {d0 ∈ D | d0 < d}. Since C and D are g-sets, we see that
c = g(W ) = d. Let W 0 = W ∪ {g(W )}; it’s a g-set larger than W with W 0 ≤ C
and W 0 ≤ D, contradicting the maximality of W .
Now let W be the union of all the g-sets. It’s a g-set, too, and it’s the largest
g-set, but W 0 = W ∪ {g(W )} is a larger g-set, yielding a contradiction. 

References
[1] Akihiro Kanamori. The mathematical import of Zermelo’s well-ordering theorem. Bull. Sym-
bolic Logic, 3(3):281–311, 1997.
[2] Irving Kaplansky. Set theory and metric spaces. Chelsea Publishing Co., New York, second
edition, 1977.
[3] Hellmuth Kneser. Eine direkte Ableitung des Zornschen Lemmas aus dem Auswahlaxiom.
Math. Z., 53:110–113, 1950.
[4] T. Szele. On Zorn’s lemma. Publ. Math. Debrecen, 1:254–256, erratum 257, 1950.
[5] J. D. Weston. A short proof of Zorn’s lemma. Arch. Math., 8:279, 1957.
[6] Ernst Zermelo. Beweis, daß jede Menge wohlgeordnet werden kann. Math. Ann., 59:514–516,
1904.

University of Illinois at Urbana-Champaign


E-mail address: dan@math.uiuc.edu
URL: http://www.math.uiuc.edu/~dan

You might also like