# Hausdorff Maximal Principle and Axiom of Choice

I need to show that Hausdorff Maximal Principle is equivalent to the Axiom of Choice. Suggested is to use Tukeys Lemma.

So far I have that Hausdorff Maximal Principle states that whenever < is a strict partial order of a set A, there is a maximal chain C $\subseteq$ A.

and

Tukeys Lemma states that $F \subseteq P(A)$ is of finite character if and only if for all $X \subseteq A : X \in F$ iff every finite subset of X is in $F$.

This is coming from my book Kunen Foundations of Mathematics.

I also understand a chain to be a totally ordered set, if for all x,y, in X, either $x \leq y$ or $y \leq x$. A chain has at most one maximal element.

I am really stuck on how to relate these two to each other. I think I have an idea of how to show equivalence from Tukey's Lemma to Axiom of Choice. But I am stuck when it comes to showing that the Hausdorff Maximal Principle is equivalent to Tukeys Lemma. Any help or references is greatly appreciated. I have also been reading up on this website: http://web.science.mq.edu.au/~chris/sets/CHAP09%20Axiom%20of%20Choice.pdf

• Your statement of Tukey's lemma is incorrect. What you have stated is the def'n of finite character,. Tukey's lemma is that if $F\subset P(A)$ is of finite character and $B\in F$ there is a subset-maximal $C$ with $B\subset C\in F$. For example, every vector space has a Hamel basis. Tukey's lemma is equivalent to Choice. – DanielWainfleet Mar 9 '16 at 6:02
• There are so many statements that have been shown to be equivalent to Choice that different authors use different def'ns of it. Which def'n does Kunen use? – DanielWainfleet Mar 9 '16 at 6:10
• In my first comment, I should have said that $C$ is subset-maximal among members of $F$ – DanielWainfleet Mar 9 '16 at 6:12

I actually don't see how to use Tukey's lemma here.

To me, the most natural proof is along the following lines (leaving some gaps to fill in):

• AC implies HMP: Use AC in the form of Zorn. Given a partial order $P$, let $P^*$ be the partial order consisting of chains in $P$, ordered by inclusion. Then a maximal element in $P^*$ corresponds to a maximal chain in $P$.

• HMP implies AC: Fix a set $\mathcal{A}$ of nonempty disjoint sets $A_i$ ($i\in I$); using $HMP$, I'll show that $\mathcal{A}$ has a choice function. Let $P$ be the partial order whose elements are partial choice functions: maps $p$ with domain $J_p\subseteq I$ satisfying $p(j)\in A_j$ for all $j\in J_p$. We order $P$ by extension: $p\ge q$ if $J_p\supseteq J_q$ and $p\upharpoonright J_q=q$. Then given a maximal chain $C\subseteq P$, let $q=\bigcup C$ be the union of the functions in $C$. Clearly $q\in P$, and $q\ge p$ for all $p\in C$; and if $dom(q)\not=I$, then we can extend $q$ to get a strictly larger element $q'$ of $P$, which will contradict the assumption that $C$ is maximal. So $q$ is in fact a full choice function, and we're done.

• OP should probably tell us, which variant of choice he uses. Proving Zorn's Lemma from some of them isn't any easier than proving the HMP from them. – Stefan Mesken Mar 9 '16 at 2:01
• @Stefan, I am not sure how to answer your question on the variant of choice, this is the Axiom that is in my book which is what I am basing everything off of: For a family, $F$, of nonempty sets, which are pairwise disjoint \\ $\emptyset \notin F, \forall x \in F \forall y \in \F ( x \neq y \implies x \cap y = \emptyset)$ $\implies \exists x \forall x \in F ('' c \cap x \mbox{ is a singleton}'')$ – lindc Mar 9 '16 at 2:08
• @lindc That answers my question. This is one of those variants, where the proof of Zorn's Lemma isn't any easier than the proof of HMP. Unfortunately I don't have the time right now to provide it, but it can be found in Schindler's Set Theory. – Stefan Mesken Mar 9 '16 at 2:18
• I was assuming Zorn had already been covered, and that we were allowed to use it. (Also, I was assuming the part the OP was really interested in was the other direction.) Indeed, as Stefan says the proof of Zorn from AC can be pretty easily adapted to a proof of HMP from AC. – Noah Schweber Mar 9 '16 at 2:41
• Tukey is very natural in this context, once you understand that it is the "right generalization" of compactness. – Asaf Karagila Mar 9 '16 at 2:57

The key point here is that being a chain is a property of finite character. $C$ is a chain if and only if every one of its finite subsets is a chain.

So Hausdorff's Maximality Principle follows easily from Tukey's Lemma.

In the other direction, given a family of finite character, pick a maximal chain and show the union of that chain is a maximal member of your family, here the trick is that if $C$ is the chain and $X$ is its union, then a finite subset of $X$ is a subset of some element of $C$.

• In regards to the HMP implies Tukey's lemma direction, doesn't showing for $X \in \cup C$, any finite subset of $X$ is some subset of some element of $C$ merely show that $\cup C$ is contained in the family of finite character? Doesn't one still have to show that $\cup C$ is maximal in that family? – Oiler Apr 25 '16 at 2:27
• You're confusing "types" here. $C$ is a subset of the family $\cal F$, $X=\bigcup C$, so in particular $X\notin X$. What you want is to show that $X\in\cal F$ and that it is a maximal element there. – Asaf Karagila Apr 25 '16 at 8:50
• So my understanding is to let $\mathcal{F}$ be of finite character and let $W \in \mathcal{F}$. Then consider the partial order of $\{Y \in \mathcal{F} \mid W \subset Y\}$ ordered by $\subsetneqq$. By HMP, let $C$ be a maximal chain in this partial order. Finishing off the proof is just a matter of showing $X = \bigcup C \in \mathcal{F}$ is maximal and $W \subseteq X$. Why do we care that $X \notin X$? – Oiler Apr 25 '16 at 16:23
• (1) I don't follow what you wrote. Note that the statement of Tukey's lemma is missing a part "then there is a maximal element in $\cal F$". (2) You want to show that if you have a family with FC (finite character), then it has a maximal element, but it is a partial order. Then you have a maximal chain, by HMP, here called $C$. Then you just have to show that the union over this chain, here called $X$ is a member of $\cal F$ to get that it is maximal. But now you use the FC to get that $X\in\cal F$, and you're done. (3) We don't care about $X\in X$. You just wrote $X\in\bigcup C$, so I cared – Asaf Karagila Apr 25 '16 at 16:45
• Tukey's Lemma as per Kunen is whenever $\mathcal{F} \subseteq \mathcal{P}(A)$ is of finite character and $W \in \mathcal{F}$, there is a maximal $X \in \mathcal{F}$ such that $W \subseteq X$. I have included that I want to show $X = \bigcup C \in \mathcal{F}$ is maximal and $W \subseteq X$, which is exactly Tukey's lemma, right? Also what is 'FC' that you refer to? – Oiler Apr 25 '16 at 18:06