How does one prove $ZF\vDash MC\Rightarrow AC$?

Question

This is somewhat adressed to Andreas Blass, whose papers I have read, in particular I make reference to an old paper of his »Existence of Basis implies the Axiom of Choice« (84). Anyone who happens to be informed may nevertheless feel free to enlighten me.

---

One works within $ZF$. Assume $MC$, that is, for all $X$ there exists $f:\mathcal{P}(X)\to\mathcal{P}(X)$, so that for all $A\in\mathcal{P}(X)\setminus\{\emptyset\}$ it holds $\emptyset\neq f(A)\subseteq A$ and $f(A)$ finite. To show is $AC$.

Due to $MC$ it holds

Proposition 0. Let $X$ be a set. There is a choice function $\mathcal{P}(X)\to X$ $\Longleftarrow$ $X$ is linear-orderable.

Proof. Consider a l.o. $\preceq$ on $X$. Set $m:\mathcal{P}(X)\to\mathcal{P}(X)$ a multi-choice function. Then $c:\mathcal{P}(X)\setminus\{\emptyset\}\to X$ defined by $c(A)=\min_{\preceq}m(A)$ is well-defined and a choice function. $\blacksquare$

Since one is working within $ZF$ it also holds:

Proposition 1. Let $X$ be a set. There is a choice function $\mathcal{P}(X)\to X$ $\Longleftrightarrow$ $X$ is well-orderable. $\dashv$

Corollary. $X$ has choice $\Longrightarrow$ $X$ has a w.o. $\Longrightarrow$ $X$ has a l.o. $\Longrightarrow$ $X$ has choice. $\dashv$

It is thus necessary and sufficient to show, every set is linear-orderable. Again, since one is working within $ZF$, it is necessary and sufficient to just consider the sets $V_{\alpha}$ for $\alpha\in NO$ (the ordinal numbers).

An argument per induction seems to suggest itself. For the successor stages, one simply builds out of a well-order $\preceq$ on $V_{\alpha-1}$ a linear order (the lexical order, $\preceq_{lex}$) on $V_{\alpha}=\mathcal{P}(V_{\alpha-1})\equiv_{SET}{}^{V_{\alpha-1}}2$.

The argument encounters difficulty for limit-ordinals, since one cannot „choose“ a well-order for all the stages below it (except when the ordinal satisfies $cf(\alpha)<\alpha$). Consider simply $\alpha=\omega_{1}$, how would one construct a linear-order on $V_{\omega_{1}}$?

---

I should note: all authors I have read up until now each hold that $ZF\vDash MC\Rightarrow AC$.

---

Final Remark. I see now how to handle with successor stages in Frunobulax’ argument.

Thm. Assuming $ZF+MC$ every $V_{\alpha}$ is well-orderable.

Proof. Consider $\alpha\in NO$ any ordinal. Thanks to $MC$ there exists $m:\mathcal{P}(V_{\alpha})\to\mathcal{P}(V_{\alpha})$ a multi-choice function. This shall henceforth remain fixed.

As already mention it holds

Claim. for $X\subseteq V_{\alpha}$ and an LO $\preceq$ on $X$, using just $m$ and $\preceq$ one can canonically construct a choice function $\mathcal{P}(X)\to X$ (via. $c:A\mapsto \min_{\preceq}(m(A))$ for $A\neq\emptyset$) and out of this in turn canonically construct a WO of $X$ (utilising the recursion $x_{\gamma}:=c(X\setminus\{x_{\xi}:\xi<\gamma\})$ for $\gamma\in NO$ for as long as $X\supsetneq\{x_{\xi}:\xi<\gamma\}$). This canonically-definable well-order shall be denoted $\preceq^{m}$. $\dashv$

Construction of a WO of $V_{\alpha}$. One constructs recursively an increasing chain $(\preceq_{\beta})_{\beta\leq\alpha}$ of WO-s of the $V_{\beta}$:

• $\preceq_{0}:=\emptyset$.
• Limit stages: $\preceq_{\beta}:=\bigcup_{\xi<\beta}\preceq_{\xi}$.
• Successor stages: one linearly orders $R_{\beta}:=V_{\beta}\setminus V_{\beta-1}\subseteq \mathcal{P}(V_{\beta-1})\equiv{}^{V_{\beta-1}}2$ via the lexical-ordering $(\preceq_{beta-1})_{lex}$. Note that $R_{\beta}\subseteq V_{\alpha}$. Set $\preceq^{\ast}:=(\preceq_{beta-1})_{lex}^{m}$ a well-order. The well-orders are then patched together by placing everything in $R_{\beta}$ after $V_{\beta-1}$, to obtain a well-order of $V_{\beta-1}\sqcup R_{\beta}=V_{\beta}$.

This recursion is well-define and in particular $\preceq_{\alpha}$ witnesses the well-orderability of $V_{\alpha}$. $\blacksquare$

Answer 1

If that's OK with you, it's easy to show that $\textbf{MC}$ implies the antichain principle which is known to be equivalent to the axiom of choice:

Let $X$ be a set partially ordered by $R$, i.e. $R$ is reflexive, antisymmetric and transitive. Let $f$ be a function which assigns to each non-empty subset $A$ of $X$ a finite non-empty subset $f(A)$ of $A$. For each such $A$ the set of $R$-minimal elements of $f(A)$ is finite, non-empty and an $R$-antichain. We'll call it $A'$.

Now, inductively, define $C_\alpha$ to be the set of all elements of $X$ which are $R$-incomparable with all elements of $B_\beta$ for all $\beta<\alpha$ and let $B_\alpha$ be $C_\alpha'$ (or $\emptyset$ if $C_\alpha$ is empty).

The union of all $B_\alpha$ is a maximal $R$-antichain.

Answer 2

Here's a modified version of a proof by Rubin which builds on what you already have above:

We claim that $\textbf{MC}$ implies that all $\mathbf{V}_\alpha$ can be well-ordered.

So, let $\alpha$ be some fixed arbitrary ordinal. Let $\lambda$ be the smallest ordinal which can't be mapped one-to-one into $\mathbf{V}_\alpha$ (i.e. the Hartogs number of $\mathbf{V}_\alpha$). $\lambda$ is well-ordered by $\in$, so we can define a linear order $\preccurlyeq$ on ${\cal P}(\lambda)$ by $x \preccurlyeq y$ iff $x=y$ or $x\neq y$ and $\min(x\bigtriangleup y)\in x$ (where $\bigtriangleup$ is the symmetric difference).

As you've shown above, due to $\textbf{MC}$ we'll find a choice function for ${\cal P}(\lambda)$ which in turn implies that this set can be well-ordered. We fix one well-ordering of ${\cal P}(\lambda)$ for the rest of the proof.

Now let $R_\beta$ be the set of all $x\in{\mathbf V}_\alpha$ with rank $\beta$. If we can show, that all $R_\beta$ for $\beta<\alpha$ can be well-ordered, then it is obvious how we can combine these well-orderings to get one for ${\mathbf V}_\alpha$. So, we'll inductively define well-orderings $\preccurlyeq_\beta$ of $R_\beta$:

Pick $\beta<\alpha$ and assume that for $\gamma<\beta$ a well-ordering $\preccurlyeq_\gamma$ of $R_\gamma$ has already been defined. Using these, we can define an "obvious" well-ordering $<_\beta$ of ${\mathbf V}_\beta$ (being the disjoint union of the $R_\gamma$ for $\gamma<\beta$).

There's a unique ordinal $\delta_\beta$ such that $(\mathbf{V}_\beta,<_\beta)$ is isomorphic to $(\delta_\beta,\in)$ and correspondingly there's a unique isomorphism $g_\beta$ from $(\delta_\beta,\in)$ onto $(\mathbf{V}_\beta,<_\beta)$. As $g_\beta$ is also an injection from $\delta_\beta$ into $\mathbf{V}_\alpha$, we must have $\delta_\beta<\lambda$.

Now, for an element $x$ of $R_\beta$ we have $x\subseteq{\mathbf V}_\beta$ and thus $g_\beta^{-1}[x] \subseteq \delta_\beta \subseteq \lambda$. Thus, $g_\beta$ (or rather its inverse) gives us a natural way of "projecting" a part of the above-mentioned well-ordering of ${\cal P}(\lambda)$ to $R_\beta$ which finishes our proof.

The important thing to note here is that we didn't make a choice at each $\beta<\alpha$ stage. The only choice made was right at the beginning when we fixed a well-ordering of ${\cal P}(\lambda)$.