Difference between revisions of "Zorn's Lemma"
m (→Lemma 2.: the element strictly less than some c in T is x, not s, as s is an upper bound on T by assumption) |
m (→Proof (using the Axiom of Choice): corrected "union" to "intersection" in the definition of M before Lemma 1) |
||
Line 24: | Line 24: | ||
* For every totally ordered subset <math>T \subseteq B</math>, the least upper bound of <math>T</math> in <math>A'</math> is an element of <math>B</math>. | * For every totally ordered subset <math>T \subseteq B</math>, the least upper bound of <math>T</math> in <math>A'</math> is an element of <math>B</math>. | ||
− | Let <math>M</math> be the | + | Let <math>M</math> be the intersection of all admissable subsets of <math>A'</math>. We note that <math>M</math> is not empty, as <math>A'</math> is an admissable subset of itself, and all admissable sets contain <math>a</math>. Then <math>M</math> is the least admissable set, under order by inclusion. |
We say that an element <math>c \in M</math> is an ''extreme point'' if <math>x\in M</math>, <math>x < c</math> together imply <math>f(x) \le c</math>. For an extreme point <math>c</math> denote by <math>M_c</math> the set of <math>x\in M</math> such that <math>x \le c</math> or <math>f(c) \le x</math>. | We say that an element <math>c \in M</math> is an ''extreme point'' if <math>x\in M</math>, <math>x < c</math> together imply <math>f(x) \le c</math>. For an extreme point <math>c</math> denote by <math>M_c</math> the set of <math>x\in M</math> such that <math>x \le c</math> or <math>f(c) \le x</math>. |
Latest revision as of 19:02, 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 intersection 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.