Section 11*: The Maximum Principle
We have already indicated that the axiom of choice leads to the deep theorem that every set can be well-ordered. The axiom of choice has other consequences that are even more important in mathematics. Collectively referred to as "maximum principles," they come in many versions. Formulated independently by a number of mathematicians, including F. Hausdorff, K. Kuratowski, S. Bochner, and M. Zorn, during the years 1914-1935, they were typically proved as consequences of the well-ordering theorem. Later, it was realized that they were in fact equivalent to the well-ordering theorem.
A strict partial order
satisfies nRT, i.e. it is an "incomplete order".
(The Maximum Principle; Hausdorff, 1914) If
is strictly partially ordered, then there exists a maximal ordered subset of
, i.e. an ordered subset such that no other ordered subset contains it.
A strictly ordered subset
of
has an upper bound
if
or
for every
.
(Zorn’s Lemma; Kuratowski, 1922; Bochner, 1922; Zorn, 1935) If
is strictly partially ordered, and every ordered subset of
has an upper bound in
, then
has a maximal element
, i.e. an element
such that for no element
does
hold.
(Kuratowski’s Lemma) If for every ordered by proper inclusion subcollection of a collection of sets its union is in the collection, then there is a set in the collection that is not a proper subset of any set in the collection.
Let
be a set and
be a collection of some of its subsets. Then
is said to be of finite type if for every
,
iff every finite subset of
is in
.
(Tukey’s Lemma; Tukey, 1940) If a collection of subsets is of finite type, then it has a set that is not a proper subset of any set in the collection.
- MP implies ZL: a maximal ordered subset has an upper bound which is a maximal element.
- ZL implies KL: the union of an ordered subcollection is an upper bound that is in the collection, so there is a maximal element in the collection.
- KL implies TL: for every finite subset of the union of an ordered subcollection, there is a single set in the subcollection containing the finite subset, therefore, every finite subset of the union is in the collection, and so is the union.
- TL implies MP: a subset of is ordered iff any its finite subset is ordered, therefore, the collection of ordered subsets is of finite type, and there is a maximal ordered subset.
- The axiom of choice is equivalent to each of the four theorems, see Supplementary Exercises.