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.


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

  • $\begingroup$ 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. $\endgroup$ – DanielWainfleet Mar 9 '16 at 6:02
  • $\begingroup$ 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? $\endgroup$ – DanielWainfleet Mar 9 '16 at 6:10
  • $\begingroup$ In my first comment, I should have said that $C$ is subset-maximal among members of $F$ $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Stefan Mesken Mar 9 '16 at 2:01
  • $\begingroup$ @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}'')$ $\endgroup$ – lindc Mar 9 '16 at 2:08
  • $\begingroup$ @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. $\endgroup$ – Stefan Mesken Mar 9 '16 at 2:18
  • $\begingroup$ 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. $\endgroup$ – Noah Schweber Mar 9 '16 at 2:41
  • $\begingroup$ Tukey is very natural in this context, once you understand that it is the "right generalization" of compactness. $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – Oiler Apr 25 '16 at 2:27
  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila Apr 25 '16 at 8:50
  • $\begingroup$ 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$? $\endgroup$ – Oiler Apr 25 '16 at 16:23
  • $\begingroup$ (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 $\endgroup$ – Asaf Karagila Apr 25 '16 at 16:45
  • $\begingroup$ 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? $\endgroup$ – Oiler Apr 25 '16 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.