Hausdorff maximal principle

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.

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

The Hausdorff maximal principle states that, in any partially ordered set, every totally ordered subset is contained in a maximal totally ordered subset (a totally ordered subset that, if enlarged in any way, does not remain totally ordered). In general, there may be many maximal totally ordered subsets containing a given totally ordered subset.

An equivalent form of the Hausdorff maximal principle is that in every partially ordered set there exists a maximal totally ordered subset. To prove that this statement follows from the original form, let A be a partially ordered set. Then $\varnothing$ is a totally ordered subset of A, hence there exists a maximal totally ordered subset containing $\varnothing$ , hence in particular A contains a maximal totally ordered subset. For the converse direction, let A be a partially ordered set and T a totally ordered subset of A. Then

\{S\mid T\subseteq S\subseteq A{\mbox{ and S totally ordered}}\}

is partially ordered by set inclusion $\subseteq$ , therefore it contains a maximal totally ordered subset P. Then the set $P$ satisfies the desired properties.

The proof that the Hausdorff maximal principle is equivalent to Zorn's lemma is very similar to this proof.^{[clarification needed]}

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 $\mathbb {R} ^{2}$ , define (x₀, y₀) < (x₁, y₁) if y₀ = y₁ and x₀ < x₁. This is a partial ordering of $\mathbb {R} ^{2}$ under which two points are comparable only if they lie on the same horizontal line. The maximal totally ordered sets are horizontal lines in $\mathbb {R} ^{2}$ .

Application

By the Hausdorff maximal principle, we can show every Hilbert space $H$ contains a maximal orthonormal subset $A$ as follows.^[1] (This fact can be stated as saying that $H\simeq \ell ^{2}(A)$ as Hilbert spaces.)

Let $P$ be the set of all orthonormal subsets of the given Hilbert space $H$ , 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 $Q$ . Let $A$ be the union of $Q$ . We shall show it is a maximal orthonormal subset. First, if $S,T$ are in $Q$ , then either $S\subset T$ or $T\subset S$ . That is, any given two distinct elements in $A$ are contained in some $S$ in $Q$ and so they are orthogonal to each other (and of course, $A$ is a subset of the unit sphere in $H$ ). Second, if $B\supsetneq A$ for some $B$ in $P$ , then $B$ cannot be in $Q$ and so $Q\cup \{B\}$ is a chain strictly larger than $Q$ , a contradiction. $\square$

For the purpose of comparison, here is a proof of the same fact by Zorn's lemma. As above, let $P$ be the set of all orthonormal subsets of $H$ . If $Q$ is a chain in $P$ , then the union of $Q$ is also orthonormal by the same argument as above and so is an upper bound of $Q$ . Thus, by Zorn's lemma, $P$ contains a maximal element $A$ . (So, the difference is that the maximal principle gives a maximal chain while Zorn's lemma gives a maximal element directly.)

Proof sketch

The idea of the following proof is essentially due to Zermelo.^[2]^[3] The same idea of the proof (namely, a tower) can also be used to show Zorn's lemma.

By the axiom of choice, we have a function $f:{\mathfrak {P}}(P)-\{\emptyset \}\to P$ such that $f(S)\in S$ for the power set ${\mathfrak {P}}(P)$ of $P$ .

Let $F$ be the set of all chains (totally ordered subsets) in $P$ . For each $C\in F$ , let $C^{*}$ be the set of all $x\in P-C$ such that $C\cup \{x\}$ is a chain; i.e., is in $F$ . If $C^{*}=\emptyset$ , then let ${\widetilde {C}}=C$ . Otherwise, let

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

Note $C$ is a maximal chain if and only if ${\widetilde {C}}=C$ . Thus, we are done if we can find a chain $C$ such that ${\widetilde {C}}=C$ .

Fix a chain $C_{0}$ in $F$ (for example, the empty set). We call a subset $T\subset F$ a tower over $C_{0}$ if

$C_{0}$ is in $T$ .
The union of each totally ordered subset $T'\subset T$ is in $T$ , where "totally ordered" is with respect to set inclusion.
For each $C$ in $T$ , ${\widetilde {C}}$ is in $T$ .

There exists at least one tower over $C_{0}$ ; indeed, the set of all chains in $F$ containing $C_{0}$ is such a tower. Let $T_{0}$ be the intersection of all towers over $C_{0}$ , which is again a tower over $C_{0}$ . Then, with some work,^[4] one sees $T_{0}$ is totally ordered with respect to set inclusion. Let $C$ be the union of $T_{0}$ . By 2., $C$ is in $T_{0}$ and then by 3., ${\widetilde {C}}$ is in $T_{0}$ . Since $C$ is the union of $T_{0}$ , ${\widetilde {C}}\subset C$ and thus ${\widetilde {C}}=C$ ; i.e., a maximal chain exists. Also, if we take $C_{0}$ to be a given chain, then we get a maximal chain containing it. $\square$

References

^ Rudin 1986, Theorem 4.22.
^ Halmos 1960, § 16.
^ Rudin 1986, Appendix
^ Editorial note: we should give a detail of this step.

Paul Halmos, Naive set theory. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted by Springer-Verlag, New York, 1974. ISBN 0-387-90092-6 (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 Rudin, Walter (1986). Real and Complex Analysis (International Series in Pure and Applied Mathematics). McGraw-Hill. ISBN 978-0-07-054234-1.

[1] Rudin 1986, Theorem 4.22.

[2] Halmos 1960, § 16.

[3] Rudin 1986, Appendix

[4] Editorial note: we should give a detail of this step.

[1]

[2]

[3]

[4]

v t e Order theory
Topics Glossary Category
Key concepts	Binary relation Boolean algebra Cyclic order Lattice Partial order Preorder Total order Weak ordering
Results	Boolean prime ideal theorem Cantor–Bernstein theorem Cantor's isomorphism theorem Dilworth's theorem Dushnik–Miller theorem Hausdorff maximal principle Knaster–Tarski theorem Kruskal's tree theorem Laver's theorem Mirsky's theorem Szpilrajn extension theorem Zorn's lemma
Properties & Types (list)	Antisymmetric Asymmetric Boolean algebra topics Completeness Connected Covering Dense Directed (Partial) Equivalence Foundational Heyting algebra Homogeneous Idempotent Lattice Bounded Complemented Complete Distributive Join and meet Reflexive Partial order Chain-complete Graded Eulerian Strict Prefix order Preorder Total Semilattice Semiorder Symmetric Total Tolerance Transitive Well-founded Well-quasi-ordering (Better) (Pre) Well-order
Constructions	Composition Converse/Transpose Lexicographic order Linear extension Product order Reflexive closure Series-parallel partial order Star product Symmetric closure Transitive closure
Topology & Orders	Alexandrov topology & Specialization preorder Ordered topological vector space Normal cone Order topology Order topology Topological vector lattice Banach Fréchet Locally convex Normed
Related	Antichain Cofinal Cofinality Comparability Graph Duality Filter Hasse diagram Ideal Net Subnet Order morphism Embedding Isomorphism Order type Ordered field Positive cone of an ordered field Ordered vector space Partially ordered Positive cone of an ordered vector space Riesz space Partially ordered group Positive cone of a partially ordered group Upper set Young's lattice