Editing Hausdorff maximal principle

{{Short description|Mathematical result or axiom on order relations}}

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 [[partial order|partially ordered set]], every [[total order|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 [[partial order|partially ordered set]] <math>P</math>, every chain <math>C_0</math> (i.e., a [[total order|totally ordered]] [[subset]]) is contained in a maximal chain <math>C</math> (i.e., a chain that is not contained in a strictly larger chain in <math>P</math>). 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 <math>P'</math> of all chains in <math>P</math> containing a given chain <math>C_0</math> in <math>P</math>. Then <math>P'</math> is partially ordered by set inclusion. Thus, by the maximal principle in the above form, <math>P'</math> contains a maximal chain <math>C'</math>. Let <math>C</math> be the union of <math>C'</math>, which is a chain in <math>P</math> since a union of a totally ordered set of chains is a chain. Since <math>C</math> contains <math>C_0</math>, it is an element of <math>P'</math>. Also, since any chain containing <math>C</math> is contained in <math>C</math> as <math>C</math> is a union, <math>C</math> is in fact a maximal element of <math>P'</math>; i.e., a maximal chain in <math>P</math>.

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 <math>P'</math> and thus <math>P'</math> contains a maximal element or a maximal chain in <math>P</math>.

Conversely, if the maximal principle holds, then <math>P</math> contains a maximal chain <math>C</math>. By the hypothesis of Zorn's lemma, <math>C</math> has an upper bound <math>x</math> in <math>P</math>. If <math>y \ge x</math>, then <math>\widetilde{C} = C \cup \{ y \}</math> is a chain containing <math>C</math> and so by maximality, <math>\widetilde{C} = C</math>; i.e., <math>y \in C</math> and so <math>y = x</math>. <math>\square</math>

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

== Application ==
By the Hausdorff maximal principle, we can show every [[Hilbert space]] <math>H</math> contains a maximal orthonormal subset <math>A</math> as follows.<ref>{{harvnb|Rudin|1986|loc=Theorem 4.22.}}</ref> (This fact can be stated as saying that <math>H \simeq \ell^2(A)</math> as Hilbert spaces.)

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

For the purpose of comparison, here is a proof of the same fact by Zorn's lemma. As above, let <math>P</math> be the set of all orthonormal subsets of <math>H</math>. If <math>Q</math> is a chain in <math>P</math>, then the union of <math>Q</math> is also orthonormal by the same argument as above and so is an upper bound of <math>Q</math>. Thus, by Zorn's lemma, <math>P</math> contains a maximal element <math>A</math>. (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]].<ref>{{harvnb|Halmos|1960|loc=§ 16.}}</ref><ref>{{harvnb|Rudin|1986|loc=Appendix}}</ref>

:Let <math>F</math> 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 <math>F</math> is in <math>F</math> and (2) each subset of a set in <math>F</math> is in <math>F</math>. Then <math>F</math> 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 <math>P</math> satisfies the above conditions.

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

For each <math>C \in F</math>, let <math>C^*</math> be the set of all <math>x \in P - C</math> such that <math>C \cup \{ x \}</math> is in <math>F</math>. If <math>C^* = \emptyset</math>, then let <math>\widetilde{C} = C</math>. Otherwise, let
:<math>\widetilde{C} = C \cup \{ f(C^*) \}.</math>
Note <math>C</math> is a maximal element if and only if <math>\widetilde{C} = C</math>. Thus, we are done if we can find a <math>C</math> such that <math>\widetilde{C} = C</math>.

Fix a <math>C_0</math> in <math>F</math>. We call a subset <math>T \subset F</math> a ''tower (over <math>C_0</math>)'' if

# <math>C_0</math> is in <math>T</math>.
# The union of each totally ordered subset <math>T' \subset T</math> is in <math>T</math>, where "totally ordered" is with respect to set inclusion.
# For each <math>C</math> in <math>T</math>, <math>\widetilde{C}</math> is in <math>T</math>.

There exists at least one tower; indeed, the set of all sets in <math>F</math> containing <math>C_0</math> is a tower. Let <math>T_0</math> be the intersection of all towers, which is again a tower.

Now, we shall show <math>T_0</math> is totally ordered. We say a set <math>C</math> is ''comparable in <math>T_0</math>'' if for each <math>A</math> in <math>T_0</math>, either <math>A \subset C</math> or <math>C \subset A</math>. Let <math>\Gamma</math> be the set of all sets in <math>T_0</math> that are comparable in <math>T_0</math>. We claim <math>\Gamma</math> is a tower. The conditions 1. and 2. are straightforward to check. For 3., let <math>C</math> in <math>\Gamma</math> be given and then let <math>U</math> be the set of all <math>A</math> in <math>T_0</math> such that either <math>A \subset C</math> or <math>\widetilde{C} \subset A</math>.

We claim <math>U</math> is a tower. The conditions 1. and 2. are again straightforward to check. For 3., let <math>A</math> be in <math>U</math>. If <math>A \subset C</math>, then since <math>C</math> is comparable in <math>T_0</math>, either <math>\widetilde{A} \subset C</math> or <math>C \subset \widetilde{A} </math>. In the first case, <math>\widetilde{A}</math> is in <math>U</math>. In the second case, we have <math>A \subset C \subset \widetilde{A}</math>, which implies either <math>A = C</math> or <math>C = \widetilde{A}</math>. (This is the moment we needed to collapse a set to an element by the axiom of choice to define <math>\widetilde{A}</math>.) Either way, we have <math>\widetilde{A}</math> is in <math>U</math>. Similarly, if <math>C \subset A</math>, we see <math>\widetilde{A}</math> is in <math>U</math>. Hence, <math>U</math> is a tower. Now, since <math>U \subset T_0</math> and <math>T_0</math> is the intersection of all towers, <math>U = T_0</math>, which implies <math>\widetilde{C}</math> is comparable in <math>T_0</math>; i.e., is in <math>\Gamma</math>. This completes the proof of the claim that <math>\Gamma</math> is a tower.

Finally, since <math>\Gamma</math> is a tower contained in <math>T_0</math>, we have <math>T_0 = \Gamma</math>, which means <math>T_0</math> is totally ordered.

Let <math>C</math> be the union of <math>T_0</math>. By 2., <math>C</math> is in <math>T_0</math> and then by 3., <math>\widetilde C</math> is in <math>T_0</math>. Since <math>C</math> is the union of <math>T_0</math>, <math>\widetilde C \subset C</math> and thus <math>\widetilde C = C</math>. <math>\square</math>

== Proof 2==


The [[Bourbaki–Witt theorem]], together with the [[Axiom of choice]], can be used to prove the Hausdorff maximal principle. Indeed, let <math>P</math> be a nonempty poset and <math>X\mathrel{\mathop:}=\{C\subseteq P\,:\, C\ \text{is a chain}\}</math> be the set of all totally ordered subsets of <math>P</math>. Notice that <math>X\neq \emptyset</math>, since <math>P\neq \emptyset</math> and <math>\{x\}\in X</math>, for any <math>x\in P</math>. Also, equipped with the inclusion <math>\subseteq</math>, <math>X</math> is a poset. We claim that every chain <math>\mathcal{C}\subseteq X</math> has a [[supremum]]. In order to check this out, let <math>S</math> be the union <math>\bigcup_{C\in \mathcal{C}}C</math>. Clearly, <math>C\subseteq S</math>, for all <math>C\in \mathcal{C}</math>. Also, if <math>U</math> is any upper bound  of <math>\mathcal{C}</math>, then <math>S\subseteq U</math>, since by definition <math>C\subseteq U</math> for all <math>C\in \mathcal{C}</math>. 

Now, consider the map <math>f\colon X\to X</math> given by

<math>f(C)\mathrel{\mathop:}=\begin{cases}C, &\text{if}\ C\ \text{is maximal}\\ C\cup \{g(P\setminus C)\}, &\text{if}\ C\ \text{is not maximal}\end{cases}</math>

where <math>g</math> is a [[choice function]] on <math>\{P\setminus C\}</math> whose existence is ensured by the Axiom of choice, and the fact that <math>P\setminus C\neq \emptyset</math> is an immediate consequence of the non-maximality of <math>C</math>. Thus, <math>C\subseteq f(C)</math>, for each <math>C\in X</math>. In view of the Bourbaki-Witt theorem, there exists an element <math>C_0\in \mathcal{C}</math> such that <math>f(C_0)=C_0</math>, and therefore <math>C_0</math> is a maximal chain of <math>P</math>.

In the case <math>P=\emptyset</math>, the empty set is trivially a maximal chain of <math>P</math>, as already mentioned above. <math>\square</math>

==Notes==
{{reflist}}

==References==
* {{cite book|first=Paul|last=Halmos|author-link=Paul Halmos|title=Naive set theory|location=Princeton, NJ|publisher=D. Van Nostrand Company|year=1960}}. Reprinted by Springer-Verlag, New York, 1974. {{ISBN|0-387-90092-6}} (Springer-Verlag edition).
* [[John L. Kelley|John Kelley]] (1955), ''General topology'', Von Nostrand. 
* Gregory Moore (1982), ''Zermelo's axiom of choice'', Springer.
* [[James Munkres]] (2000), ''Topology'', Pearson.
* Appendix of {{cite book | last=Rudin | first=Walter | authorlink = Walter Rudin | title = Real and Complex Analysis (International Series in Pure and Applied Mathematics) | publisher=McGraw-Hill | year=1986 |isbn=978-0-07-054234-1}}
{{Order theory}}

[[Category:Axiom of choice]]
[[Category:Mathematical principles]]
[[Category:Order theory]]