Hausdorff maximal principle explained

In mathematics, the Hausdorff maximal principle is an alternate and earlier formulation of Zorn's lemma proved by Felix Hausdorff in 1914 (Moore 1982:168). It states that in any partially ordered set, every totally ordered subset is contained in a maximal totally ordered subset, where "maximal" is with respect to set inclusion.

In a partially ordered set, a totally ordered subset is also called a chain. Thus, the maximal principle says every chain in the set extends to a maximal chain.

The Hausdorff maximal principle is one of many statements equivalent to the axiom of choice over ZF (Zermelo–Fraenkel set theory without the axiom of choice). The principle is also called the Hausdorff maximality theorem or the Kuratowski lemma (Kelley 1955:33).

Statement

, every chain

C₀

(i.e., a totally ordered subset) is contained in a maximal chain

(i.e., a chain that is not contained in a strictly larger chain in

). In general, there may be several maximal chains containing a given chain.

An equivalent form of the Hausdorff maximal principle is that in every partially ordered set, there exists a maximal chain. (Note if the set is empty, the empty subset is a maximal chain.)

This form follows from the original form since the empty set is a chain. Conversely, to deduce the original form from this form, consider the set

of all chains in

containing a given chain

C₀

. Then

is partially ordered by set inclusion. Thus, by the maximal principle in the above form,

contains a maximal chain

. Let

be the union of

, which is a chain in

since a union of a totally ordered set of chains is a chain. Since

contains

C₀

, it is an element of

. Also, since any chain containing

is contained in

is a union,

is in fact a maximal element of

; i.e., a maximal chain in

The proof that the Hausdorff maximal principle is equivalent to Zorn's lemma is somehow similar to this proof. Indeed, first assume Zorn's lemma. Since a union of a totally ordered set of chains is a chain, the hypothesis of Zorn's lemma (every chain has an upper bound) is satisfied for

and thus

contains a maximal element or a maximal chain in

Conversely, if the maximal principle holds, then

contains a maximal chain

. By the hypothesis of Zorn's lemma,

has an upper bound

. If

y\gex

, then

\widetilde{C}=C\cup\{y\}

is a chain containing

and so by maximality,

\widetilde{C}=C

; i.e.,

y\inC

and so

y=x

\square

Examples

If A is any collection of sets, the relation "is a proper subset of" is a strict partial order on A. Suppose that A is the collection of all circular regions (interiors of circles) in the plane. One maximal totally ordered sub-collection of A consists of all circular regions with centers at the origin. Another maximal totally ordered sub-collection consists of all circular regions bounded by circles tangent from the right to the y-axis at the origin.

If (x₀, y₀) and (x₁, y₁) are two points of the plane

R²

, define (x₀, y₀) < (x₁, y₁) if y₀ = y₁ and x₀ < x₁. This is a partial ordering of

R²

under which two points are comparable only if they lie on the same horizontal line. The maximal totally ordered sets are horizontal lines in

R²

Application

contains a maximal orthonormal subset

as follows. (This fact can be stated as saying that

H\simeq\ell^2(A)

as Hilbert spaces.)

Let

be the set of all orthonormal subsets of the given Hilbert space

, which is partially ordered by set inclusion. It is nonempty as it contains the empty set and thus by the maximal principle, it contains a maximal chain

. Let

be the union of

. We shall show it is a maximal orthonormal subset. First, if

S,T

are in

, then either

S\subsetT

T\subsetS

. That is, any given two distinct elements in

are contained in some

and so they are orthogonal to each other (and of course,

is a subset of the unit sphere in

). Second, if

B\supsetneqA

for some

, then

cannot be in

and so

Q\cup\{B\}

is a chain strictly larger than

, a contradiction.

\square

For the purpose of comparison, here is a proof of the same fact by Zorn's lemma. As above, let

be the set of all orthonormal subsets of

. If

is a chain in

, then the union of

is also orthonormal by the same argument as above and so is an upper bound of

. Thus, by Zorn's lemma,

contains a maximal element

. (So, the difference is that the maximal principle gives a maximal chain while Zorn's lemma gives a maximal element directly.)

Proof 1

The idea of the proof is essentially due to Zermelo and is to prove the following weak form of Zorn's lemma, from the axiom of choice.

Let

be a nonempty set of subsets of some fixed set, ordered by set inclusion, such that (1) the union of each totally ordered subset of

is in

and (2) each subset of a set in

is in

. Then

has a maximal element.

(Zorn's lemma itself also follows from this weak form.) The maximal principle follows from the above since the set of all chains in

satisfies the above conditions.

By the axiom of choice, we have a function

f:ak{P}(P)-\{\emptyset\}\toP

such that

f(S)\inS

for the power set

ak{P}(P)

For each

C\inF

, let

C^*

be the set of all

x\inP-C

such that

C\cup\{x\}

is in

. If

C^*=\emptyset

, then let

\widetilde{C}=C

. Otherwise, let

\widetilde{C}=C\cup\{f(C^*)\}.

Note

is a maximal element if and only if

\widetilde{C}=C

. Thus, we are done if we can find a

such that

\widetilde{C}=C

Fix a

C₀

. We call a subset

T\subsetF

a tower (over
C₀

) if

C₀

is in

The union of each totally ordered subset

T'\subsetT

is in

, where "totally ordered" is with respect to set inclusion.

For each

\widetilde{C}

is in

There exists at least one tower; indeed, the set of all sets in

containing

C₀

is a tower. Let

T₀

be the intersection of all towers, which is again a tower.

Now, we shall show

T₀

is totally ordered. We say a set

is comparable in
T₀

if for each

T₀

, either

A\subsetC

C\subsetA

. Let

\Gamma

be the set of all sets in

T₀

that are comparable in

T₀

. We claim

\Gamma

is a tower. The conditions 1. and 2. are straightforward to check. For 3., let

\Gamma

be given and then let

be the set of all

T₀

such that either

A\subsetC

\widetilde{C}\subsetA

We claim

is a tower. The conditions 1. and 2. are again straightforward to check. For 3., let

be in

. If

A\subsetC

, then since

is comparable in

T₀

, either

\widetilde{A}\subsetC

C\subset\widetilde{A}

. In the first case,

\widetilde{A}

is in

. In the second case, we have

A\subsetC\subset\widetilde{A}

, which implies either

A=C

C=\widetilde{A}

. (This is the moment we needed to collapse a set to an element by the axiom of choice to define

\widetilde{A}

.) Either way, we have

\widetilde{A}

is in

. Similarly, if

C\subsetA

, we see

\widetilde{A}

is in

. Hence,

is a tower. Now, since

U\subsetT₀

and

T₀

is the intersection of all towers,

U=T₀

, which implies

\widetilde{C}

is comparable in

T₀

; i.e., is in

\Gamma

. This completes the proof of the claim that

\Gamma

is a tower.

Finally, since

\Gamma

is a tower contained in

T₀

, we have

T₀=\Gamma

, which means

T₀

is totally ordered.

Let

be the union of

T₀

. By 2.,

is in

T₀

and then by 3.,

\widetildeC

is in

T₀

. Since

is the union of

T₀

\widetildeC\subsetC

and thus

\widetildeC=C

\square

Proof 2

The Bourbaki–Witt theorem can also be used to prove the Hausdorff maximal principle:

References

Book: Halmos, Paul. Paul Halmos. Naive set theory. Princeton, NJ. D. Van Nostrand Company. 1960. . Reprinted by Springer-Verlag, New York, 1974. (Springer-Verlag edition).
John Kelley (1955), General topology, Von Nostrand.
Gregory Moore (1982), Zermelo's axiom of choice, Springer.
James Munkres (2000), Topology, Pearson.
Appendix of Book: Rudin, Walter . Walter Rudin

. Walter Rudin . Real and Complex Analysis (International Series in Pure and Applied Mathematics) . McGraw-Hill . 1986 . 978-0-07-054234-1.