Difference between revisions of "Zorn's Lemma"
m (Inserted a missing subscript 'i' in 'X_i'.) |
(→Corollary 5 (Zorn's Lemma).: the first maximal element in the final para should be from T, not Z) |
||
Line 68: | Line 68: | ||
is evidently the least upper bound of the <math>X_i</math>, and if <math>a,b \in Z</math>, then for some <math>i,j \in I</math>, <math>a \in X_i</math> and <math>b \in X_j</math>; one of <math>X_i</math> and <math>X_j</math> is a subset of the other, by assumption, so <math>a</math> and <math>b</math> are comparable. It follows that <math>Z</math> is totally ordered, i.e., <math>Z \in T</math>. | is evidently the least upper bound of the <math>X_i</math>, and if <math>a,b \in Z</math>, then for some <math>i,j \in I</math>, <math>a \in X_i</math> and <math>b \in X_j</math>; one of <math>X_i</math> and <math>X_j</math> is a subset of the other, by assumption, so <math>a</math> and <math>b</math> are comparable. It follows that <math>Z</math> is totally ordered, i.e., <math>Z \in T</math>. | ||
− | Now, by Corollary 4, there exists a maximal element <math>P</math> of <math> | + | Now, by Corollary 4, there exists a maximal element <math>P</math> of <math>T</math>. This set <math>P</math> is totally ordered, so it has an upper bound <math>x_0</math> in <math>A</math>. Then <math>P \cup \{x_0\}</math> is a totally ordered set, so by the maximality of <math>P</math>, <math>x_0 \in P</math>. Now, if <math>y\ge x_0</math>, then <math>P \cup \{y\}</math> is a totally ordered set, so <math>y \in P</math> and <math>y\le x_0</math>, so <math>y=x_0</math>. Therefore <math>x_0</math> is a maximal element, as desired. {{halmos}} |
== References == | == References == |
Revision as of 18:58, 1 August 2018
Zorn's Lemma is a set theoretic result which is equivalent to the Axiom of Choice.
Contents
Background
Let be a partially ordered set.
We say that is inductively ordered if every totally ordered subset
of
has an upper bound, i.e., an element
such that for all
,
. We say that
is strictly inductively ordered if every totally ordered subset
of
has a least upper bound, i.e., an upper bound
so that if
is an upper bound of
, then
.
An element is maximal if the relation
implies
. (Note that a set may have several maximal elements.)
We say a function is increasing if
for all
.
Statement
Every inductively ordered set has a maximal element.
Proof (using the Axiom of Choice)
We first prove some intermediate results, viz., Bourbaki's Theorem (also known as the Bourbaki-Witt theorem).
Let be a strictly inductively ordered set, and let
be an increasing function. Pick some
. Let
be the set of elements
such that
. Evidently,
is stricty inductively ordered, for if
is a totally ordered subset of
, then it has a least upper bound in
, which is evidently greater than
, so this least upper bound is an element of
. We say that a subset
is admissable if it satisfies these conditions:
- For every totally ordered subset
, the least upper bound of
in
is an element of
.
Let be the union of all admissable subsets of
. We note that
is not empty, as
is an admissable subset of itself, and all admissable sets contain
. Then
is the least admissable set, under order by inclusion.
We say that an element is an extreme point if
,
together imply
. For an extreme point
denote by
the set of
such that
or
.
Lemma 1.
For each extreme point ,
.
Proof. It suffices to show that is an admissable set. Evidently,
, so
. Now, let
be an element of
. If
, then evidently,
, so
. If
, then since
is an extreme point,
, so
. On the other hand, if
, then
, so
. Therefore
.
Let be a totally ordered subset of
. Then
has a least upper bound
. Since
is admissable,
. Now, if
, then evidently
. On the other hand, if
, then either
, or every element of
is less than or equal to
, so
. Hence the least upper bound of every totally ordered subset
of
is an element of
, so
is admissable. Therefore
; since we know
, it follows that
. ∎
Lemma 2.
Every element of is an extreme point.
Proof. Let be the set of extreme points of
. As before, it suffices to show that
is an admissable set. Evidently,
is an extreme point of
, as no element of
is less than
, so every element less than
is also less than or equal to
. Now, suppose
is an extreme point of
. Then for any
, if
, then by Lemma 1,
. If
, then
, so
; if
, then since
is an extreme point,
. Therefore
is an extreme point, so
.
Now, let be a totally ordered set of extreme points. Consider the least upper bound
of
in
. If
is an element of
strictly less than
, then
must be strictly less than some element
. But
is an extreme point, so
. Therefore
is an extreme point, i.e., an element of
. It follows that
is an admissable set, so as before,
. ∎
Theorem 3 (Bourbaki).
For any strictly inductively ordered set and any increasing function
, there exists an element
of
such that
.
Proof. Choose an arbitrary , and define
as before. Let
be the least admissable subset of
, as before. By Lemmata 2 and 1, for all elements
, either
, or
. Therefore
is totally ordered under the ordering induced by
. Then
has a least upper bound
which is an element of
. We note that
, so
, and since
is increasing,
. Hence
, as desired. ∎
Note that thus far, we have not used the Axiom of Choice. In the next corollary, however, we will use the Axiom of Choice.
Corollary 4.
Let be a strictly inductively ordered set. Then
has a maximal element.
Proof. Suppose the contrary. Then by the Axiom of Choice, for each , we may define
to be an element strictly greater than
. Then
is an increasing function, but for no
does
, which contradicts the Bourbaki-Witt Theorem. ∎
Corollary 5 (Zorn's Lemma).
Let be an inductively ordered set. Then
has a maximal element.
Proof. Let be the family of totally ordered subsets of
.
We claim that under the order relation ,
is a strictly inductively ordered set. Indeed, if
is a totally ordered subset of
, then
is evidently the least upper bound of the
, and if
, then for some
,
and
; one of
and
is a subset of the other, by assumption, so
and
are comparable. It follows that
is totally ordered, i.e.,
.
Now, by Corollary 4, there exists a maximal element of
. This set
is totally ordered, so it has an upper bound
in
. Then
is a totally ordered set, so by the maximality of
,
. Now, if
, then
is a totally ordered set, so
and
, so
. Therefore
is a maximal element, as desired. ∎
References
- Lang, S. Algebra, Revised Third Edition. Springer (2002), ISBN 0-387-95385-X.