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, 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
The Hausdorff maximal principle states that, in any partially ordered set , every chain (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 in . 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 , it is an element of . Also, since any chain containing is contained in as 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 in . If , then is a chain containing and so by maximality, ; i.e., and so .
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 (x0, y0) and (x1, y1) are two points of the plane , define (x0, y0) < (x1, y1) if y0 = y1 and x0 < x1. This is a partial ordering of under which two points are comparable only if they lie on the same horizontal line. The maximal totally ordered sets are horizontal lines in .
Application
By the Hausdorff maximal principle, we can show every Hilbert space contains a maximal orthonormal subset as follows.[1] (This fact can be stated as saying that 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 are in , then either or . That is, any given two distinct elements in are contained in some in and so they are orthogonal to each other (and of course, is a subset of the unit sphere in ). Second, if for some in , then cannot be in and so is a chain strictly larger than , a contradiction.
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 sketch
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.[2][3]
- 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 such that for the power set of .
For each , let be the set of all such that is in . If , then let . Otherwise, let
Note is a maximal element if and only if . Thus, we are done if we can find a such that .
Fix a in . We call a subset a tower over if
- is in .
- The union of each totally ordered subset is in , where "totally ordered" is with respect to set inclusion.
- For each in , is in .
There exists at least one tower over ; indeed, the set of all sets in containing is such a tower. Let be the intersection of all towers over , which is again a tower over . Then, with some work,[4] one sees is totally ordered with respect to set inclusion. Let be the union of . By 2., is in and then by 3., is in . Since is the union of , and thus .
References
- ^ Rudin 1986, Theorem 4.22.
- ^ Halmos 1960, § 16. harvnb error: no target: CITEREFHalmos1960 (help)
- ^ 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.
- v
- t
- e
- Binary relation
- Boolean algebra
- Cyclic order
- Lattice
- Partial order
- Preorder
- Total order
- Weak ordering
- Antisymmetric
- Asymmetric
- Boolean algebra
- Completeness
- Connected
- Covering
- Dense
- Directed
- (Partial) Equivalence
- Foundational
- Heyting algebra
- Homogeneous
- Idempotent
- Lattice
- Reflexive
- Partial order
- Prefix order
- Preorder
- Semilattice
- Semiorder
- Symmetric
- Total
- Tolerance
- Transitive
- Well-founded
- Well-quasi-ordering (Better)
- (Pre) Well-order
- Alexandrov topology & Specialization preorder
- Ordered topological vector space
- Normal cone
- Order topology
- Order topology
- Topological vector lattice
- Antichain
- Cofinal
- Cofinality
- Comparability
- Duality
- Filter
- Hasse diagram
- Ideal
- Net
- Subnet
- Order morphism
- Order type
- Ordered field
- Ordered vector space
- Partially ordered group
- Upper set
- Young's lattice