Prove the antichain principle is equivalent to choice.

Question

Wikipedia lists the maximal antichain principle (every partially ordered set has a maximal antichain) as equivalent to the axiom of choice:
https://en.wikipedia.org/wiki/Axiom_of_choice

I can show quite easily show the maximal chain principle (every poset has a maximal chain) implies the maximal antichain principle:
Take a maximal chain $C$ in the set of antichains, ordered by inclusion. The antichain $\bigcup C$ is then maximal.

My question then is how to prove the axiom of choice from the maximal antichain principle (and indeed which incarnation of choice is the easiest to prove from the maximal antichain principle; I imagine either the maximal chain principle or Zorn's lemma?)

Thanks in advance!

Answer 1

The approach that I’ve seen starts by showing that the antichain principle implies that every linearly ordered set can be well-ordered.

Let $\langle X,\le\rangle$ be a linear order. Let $\mathscr{P}=\{\langle A,x\rangle\in\wp(X)\times X:x\in A\}$, and define a strict partial order $\prec$ on $\mathscr{P}$ by setting $\langle A,x\rangle\prec\langle B,y\rangle$ iff $A=B$ and $x<y$. Let $\mathscr{A}$ be a maximal antichain in $\mathscr{P}$, and suppose that $\langle A,x\rangle,\langle B,y\rangle\in\mathscr{A}$. If $A=B$, then $x\not<y\not<x$, so $x=y$, and $\langle A,x\rangle=\langle B,y\rangle$. Thus, $\mathscr{A}$ is actually a choice function on $X$.

Now recursively define a sequence $\langle x_\xi:\xi<\alpha\rangle$ in $X$ as follows. If $\beta$ is an ordinal, and $\{x_\xi:\xi<\beta\}\subseteq X$ has been defined and is not equal to $X$, let $x_\beta=\mathscr{A}(X\setminus\{x_\xi:\xi<\beta\})$. Since $X$ is a set, there must be a least ordinal $\alpha$ for which $x_\alpha$ is undefined, and clearly $X=\{x_\xi:\xi<\alpha\}$ is an enumeration of $X$ in type $\alpha$ that induces an obvious well-ordering of $X$.

Then one shows that the power set of every ordinal is linearly orderable.

Let $\alpha$ be an ordinal, and for $A,B\subseteq\alpha$ let $\delta(A,B)=\min(A\mathop{\triangle}B)$. Define a relation $\prec$ on $\wp(\alpha)$ by setting $A\prec B$ iff $\delta(A,B)\in B$. Then $A\prec B$ iff $\chi_A$ precedes $\chi_B$ in the lexicographic order on ${^\alpha2}$, so $\prec$ is a strict linear order on $\wp(\alpha)$.

The final step is to apply the theorem that $\mathsf{AC}$ holds if $\wp(\alpha)$ is well-orderable for every ordinal $\alpha$. This is an older result by Herman Rubin whose proof is significantly harder and involves showing by induction that the hypothesis implies that each $V_\alpha$ in the von Neumann hierarchy can be well-ordered; let me see if I can find it online. Ah, here we go: it’s the last theorem on this page of Andrés Caicedo’s Teaching blog, along with the rest of this proof; this may well be where I first saw the result, in fact.