Hausdorff maximal principle

The Hausdorff maximal principle states that, in any partially ordered set P, every chain C_0 (i.e., a totally ordered subset) is contained in a maximal chain C (i.e., a chain that is not contained in a strictly larger chain in P). 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 P' of all chains in P containing a given chain C_0 in P. Then P' is partially ordered by set inclusion. Thus, by the maximal principle in the above form, P' contains a maximal chain C'. Let C be the union of C', which is a chain in P since a union of a totally ordered set of chains is a chain. Since C contains C_0, it is an element of P'. Also, since any chain containing C is contained in C as C is a union, C is in fact a maximal element of P'; i.e., a maximal chain in P. 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 P' and thus P' contains a maximal element or a maximal chain in P. Conversely, if the maximal principle holds, then P contains a maximal chain C. By the hypothesis of Zorn's lemma, C has an upper bound x in P. If y \ge x, then \widetilde{C} = C \cup \{ y \} is a chain containing C and so by maximality, \widetilde{C} = C; i.e., y \in C 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 (x0, y0) and (x1, y1) are two points of the plane \mathbb{R}^{2}, define (x0, y0) 1, y1) if y0 = y1 and x0 1. 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. (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.) == Proofs ==

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. (Zorn's lemma itself also follows from this weak form.) The maximal principle follows from the above since the set of all chains in P satisfies the above conditions. 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. For each C \in F, let C^* be the set of all x \in P - C such that C \cup \{ x \} is in F. If C^* = \emptyset, then let \widetilde{C} = C. Otherwise, let :\widetilde{C} = C \cup \{ f(C^*) \}. Note C is a maximal element if and only if \widetilde{C} = C. Thus, we are done if we can find a C such that \widetilde{C} = C. Fix a C_0 in F. 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; indeed, F itself is a tower. Let T_0 be the intersection of all towers, which is again a tower. Now, we shall show T_0 is totally ordered. We say a set C is comparable in T_0 if for each A in T_0, either A \subset C or C \subset A. Let \Gamma be the set of all sets in T_0 that are comparable in T_0. We claim \Gamma is a tower. The conditions 1. and 2. are straightforward to check. For 3., let C in \Gamma be given and then let U be the set of all A in T_0 such that either A \subset C or \widetilde{C} \subset A. We claim U is a tower. The conditions 1. and 2. are again straightforward to check. For 3., let A be in U. If A \subset C, then since C is comparable in T_0, either \widetilde{A} \subset C or C \subset \widetilde{A} . In the first case, \widetilde{A} is in U. In the second case, we have A \subset C \subset \widetilde{A}, which implies either A = C or 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 U. Similarly, if C \subset A, we see \widetilde{A} is in U. Hence, U is a tower. Now, since U \subset T_0 and T_0 is the intersection of all towers, U = T_0, which implies \widetilde{C} is comparable in T_0; 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_0, we have T_0 = \Gamma, which means T_0 is totally ordered. 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. \square The existence of a C in F such that \widetilde{C} = C is also immediately given by the Bourbaki–Witt theorem (cf. ), which says that F \to F, \, C \mapsto \widetilde{C} has a fixed point. On the other hand, the above proof actually establishes the following as a special case, which is somewhat of independent interest. Indeed, if such g exists, we define \widetilde{C} = C \cup \{ g(C) \} and the above C gives a contradiction as C = \widetilde{C}. This lemma in turns immediately implies the Bourbaki–Witt theorem; see Bourbaki–Witt theorem#Proof 3. For an alternative proof (of Bourbaki–Witt), see also the proof of Theorem 3.1. (Bourbaki-Witt) at https://ncatlab.org/nlab/show/Zorn's+lemma What we call a tower here is the same as an s-inductive set there. That proof is exactly the same as the proof of Zorn's lemma in Lang's Algebra. Proof 2 The Bourbaki–Witt theorem states :Let X be a nonempty poset in which each chain has a least upper bound (i,e., supremum). Then each function f : X \to X such that f(x) \ge x for every x in X has a fixed point. The above theorem itself does not rely on the axiom of choice. However, together with the axiom of choice, it can be used to prove the Hausdorff maximal principle as follows. Take X to be the set of all chains in a poset P, which itself is a poset with respect to set inclusion. It is nonempty since it includes the empty set. Also, the union of a chain \mathcal{C} \subset X is a least upper bound: it is clearly an upper bound and if U is an upper bound of \mathcal{C}, then \cup \mathcal{C} \subset U. Now, for each chain C in P, let C^* be the set of all strict upper bounds of C. Let :g : \mathfrak{P}(P) - \{ \emptyset \} \to P be a choice function whose existence is ensured by the axiom of choice and then define f : X \to X by :f(C)\mathrel{\mathop:}=\begin{cases}C, &\text{if}\ C\ \text{is maximal}\\ C\cup \{g(C^*)\}, &\text{if}\ C\ \text{is not maximal}\end{cases} By the Bourbaki-Witt theorem, there exists an element C in X such that f(C) = C and this C is a maximal chain in P. \square Proof from the well-ordering theorem Let P' be the set of all chains in P. By the well-ordering theorem, we find a well-ordering \preceq on P. We shall construct the function :f : P \to P' recursively with respect to \preceq as follows. For an element x in P, suppose we are given an arbitrary function :g : \{ y \in P \mid y \prec x \} \to P'. Then let :f(x) = (\cup \operatorname{im}(g)) \cup \{ x \} if the set on the right is totally ordered; i.e., an element of P' and f(x) = \emptyset otherwise. If g itself is also required to satisfy the above recursive condition, then the transfinite recursion theorem ensures this defines the function f uniquely (in a nutshell, if x is a \preceq-least element, the domain of g above is the empty set and thus f(x) is uniquely determined and in general, the recursion condition ensures the unique g is used to define f(x).) We note • The image of f is totally ordered, with respect to set inclusion. • If D is a chain containing \cup \{ f(y) \mid y \prec x, \, x \in D \}, then x \in f(x) for each x \in D. Indeed, (1) holds since if y \prec x, then :f(x) = (\cup \{ f(y) \mid y \prec x \}) \cup \{ x \} which contains f(y) as a subset. (2) holds since :f(\{ y \mid y \prec x \}) \cup \{ x \} \subset D is a chain as it is a subset of a chain. Finally, by (1), the union C of the image of f is a chain and it is maximal by (2), since if D \supset C is another chain, then x \in f(x)\subset C for each x \in D. \square ==Notes==