Counterexample to the Hausdorff Maximal Principle

Question

The Hausdorff Maximal Principle states:

Every partially ordered set $\left(X,\leqslant\right)$ has a linearly ordered subset $\left(E,\leqslant\right)$ such that no subset of $X$ that properly includes $E$ is linearly ordered by $\leqslant$.     [Folland]

I know that this principle is equivalent to the axiom of choice, which means that it is undecidable. If we assume its negation (or the negation of axiom of choice, or of the well ordering principle, or anything equivalent), can we actually construct a counterexample?

My question is: is it possible [or even easy? :)] to write down an example of a partially ordered set such that no linearly ordered subset is maximal?

I know that to construct such an example, we need to use the negation of the axiom of choice.

Answer 1

Take the negation of Zorn's Lemma (which is equivalent to the negation of the axiom of choice). So we have a partially ordered set $X$ with no maximal element but each linearly ordered subset has an upper bound. Take an arbitrary subset $Y\subseteq X$ which is linearly ordered. Then $Y$ can't be maximal. This is because $Y$ has an upper bound but there are even bigger elements than this bound since otherwise the bound would be maximal element of $X$.

Answer 2

You can't quite get a specific example. If you could, then it would suffice to show that this example has a maximal chain in order to prove the axiom of choice, or the Hausdorff maximality principle, and we know that there isn't one particular example.

Why do we know that? We know that because given a model of $\sf ZF$, and a counterexample to the axiom of choice (or whatever equivalent of it you prefer to think of), we can always use set theoretic techniques to extend that model of $\sf ZF$ and ensure that the given set is no longer a counterexample; but the axiom of choice will remain false (either because fixing that particular counterexample wasn't enough to restore the axiom of choice, or because we added new counterexamples instead).

So the negation of the axiom of choice only gives us a vague family of sets which does not admit a choice function. It is consistent, for example, that the axiom of choice fails but every family of finite sets still admits a choice function; or maybe every countable family of sets each of size $\leq|\Bbb R|$ still admits a choice function; or maybe every family of sets where the family can be well-ordered admits a choice function...

The options are endless. All we can say, when we just assume the negation of the axiom of choice, is that the axiom of choice fails somehow.

But sure enough, if something is equivalent to the axiom of choice then from the proof of equivalence we can usually generate some algorithm, that given a family of sets which does not admit a choice function, we can generate a counterexample to the equivalent principle.

In this case, a partial order without maximal chains. The proof of the axiom of choice from the Hausdorff maximality principle goes a bit like this:

1. Let $\{A_i\mid i\in I\}$ be a family of non-empty sets. Define $(P,\leq)$ to be all the functions which choose from $\{A_j\mid j\in J\}$, where $J\subseteq I$. Formally, $P=\bigcup_{J\subseteq I}\prod_{j\in J}A_j$, and $f\leq g$ if $f\subseteq g$.

2. Assuming the maximality principle, we have a maximal chain, then this is a chain of functions, therefore its union is also a function, and it is not a difficult task to verify that this function is in fact a choice function from $\{A_i\mid i\in I\}$ (it is certainly a choice function; and if its domain is a proper subset of $I$ then we can extend the chain, contradiction its maximality).

Therefore, if we assume that the axiom of choice fails, given a family of sets $\{A_i\mid i\in I\}$ which does not admit a choice function, we can simply consider $P$ as above, and it will necessarily be a partial order without maximal chains.

This is not quite as explicit counterexample as we might like it to be, but it is slightly more instructive for understanding how the axiom of choice and the Hausdorff maximality principle are related. And it also tells us that if we know about a concrete family of sets without a choice function, then we can manufacture this example as well (and note that $P$ above is also a counterexample to Zorn's lemma).