3
$\begingroup$

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$

$\endgroup$
3
  • 2
    $\begingroup$ For the result that $\mathcal P(\alpha)$ being well-orderable for all ordinals $\alpha$ gives choice, this has been asked here a few times. Or see here. You may want to remark explicitly that your proposition 0 is not being proved in $\mathsf{ZF}$ alone, where it is false. $\endgroup$ Sep 9, 2014 at 14:39
  • $\begingroup$ There are copious amounts of models of $\sf ZF$ with linearly ordered sets which are not well-orderable. For example the Dedekind-finite set of reals in Cohen's first model; $\Bbb R$ in Solovay's model and in models of $\sf AD$; and so on and so forth. $\endgroup$
    – Asaf Karagila
    Sep 9, 2014 at 14:44
  • $\begingroup$ »You may want to remark explicitly that your proposition 0 is not being proved in 𝖹𝖥 alone, where it is false.« I know, that is why it is written directly above Proposition 0 »Due to MC it holds«. The Corollary below Proposition 1 is within the assumptions of the Argument (i.~e. inclusive MC). $\endgroup$
    – Thomas
    Sep 10, 2014 at 7:50

2 Answers 2

1
$\begingroup$

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)$.

$\endgroup$
9
  • $\begingroup$ Hmmm, this is really sketchy at a critical step. »[$\forall{x\in R_\beta:~}x\subseteq{\mathbf V}_\beta$, thus $g_\beta^{-1}[x] \subseteq \delta_\beta \subseteq \lambda$. Thus, $g_\beta$ ... 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.]« Problem: $g_{\beta}$ ist not necessarily uniquely/naturally choosable. There are more than one Bijektions from $R_{\beta}\to\delta_{\beta}$, since one may simply permute the elements of $R_{\beta}$. $\endgroup$
    – Thomas
    Sep 13, 2014 at 16:37
  • $\begingroup$ Also it is not due to $MC$, that »$X$ has a WO $\Leftrightarrow$ $\mathcal{P}(X)$ has choice«, but rather due to $ZF$ (or other suitable basic axioms). It is due to $MC$ that »$X$ has a WO $\Leftrightarrow$ $X$ has a LO«. $\endgroup$
    – Thomas
    Sep 13, 2014 at 16:42
  • $\begingroup$ No, that's wrong. At that point of the construction $<_\beta$ is well-defined and, as I wrote, there's a unique ordinal and a unique isomorphism. That's a standard theorem of set theory. The mapping is between $\mathbf{V}_\beta$ and $\delta_\beta$, not between $R_\beta$ and $\delta_\beta$, and it is uniquely determined by the well-ordering. $\endgroup$
    – Frunobulax
    Sep 13, 2014 at 16:44
  • $\begingroup$ For your second comment, see what @AndresCaicedo wrote above. This can not be proved in ZF alone. I'll repeat that step of the proof in detail: $\lambda$ is well-ordered because it's an ordinal. Using this well-ordering I construct a linear ordering on ${\cal P}(\lambda)$. You've shown above that with MC we now have that ${\cal P}(\lambda)$ has a choice function (the choice function being a function from ${\cal P}({\cal P}(\lambda))$ to ${\cal P}(\lambda)$). This is equivalent to ${\cal P}(\lambda)$ being well-orderable. $\endgroup$
    – Frunobulax
    Sep 13, 2014 at 16:49
  • 1
    $\begingroup$ Well, I've wasted enough time on this already and I certainly don't feel the desire to be insulted. I maintain that both my answers are correct. I suggest you go to a library and read for example Rubin's second book about AC. $\endgroup$
    – Frunobulax
    Sep 16, 2014 at 14:49
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thanks for the contribution. The idea is good, but contains a technical failure: $A’$ may be empty! Consider an Equivalence relation, and suppose $f(A)$ consists of more than one element out of the same equivalence class, then $A’$ is empty. $\endgroup$
    – Thomas
    Sep 10, 2014 at 7:45
  • $\begingroup$ A partial order which at the same time is an equivalence relation? That leaves only one choice and its equivalence classes only have one element each... $\endgroup$
    – Frunobulax
    Sep 10, 2014 at 11:32
  • $\begingroup$ The partial orders to be considered are simply: transitive+reflexive (do not necc. satisfy $x\leq y\leq x\Rightarrow y=x$). Here the proof that max-antichain-principle $\Longrightarrow$ AC: Let $X$ be a set. Let $P:=\{(a,A):a\in A\subseteq X\}$ and define $(a,A)\leq(a',A')$ iff $A'=A$. Then a maximal antichain corresponds to a choice function. (Notice, that this is an equivalence relation.) $\endgroup$
    – Thomas
    Sep 10, 2014 at 12:25
  • $\begingroup$ I stand corrected! I see now, how your Version of max-Antichain-Principle also allows for a proof of $AC$: Let $X$ be a set of non-empty pairwise disjoint sets. Consider $\mathbb{P}:=\{(x,A)|\exists{B\in X:~}x\in A\subseteq B\}$ p.o. by $(x,A)<(x',A')$ iff $A\subset A'$ strict. Thus $<$ is transitive and non-refl. Observation: $(x,A)\perp (x',A')$ iff $A\cap A'=\emptyset$. Now let $\mathcal{C}$ be a maximal antichain for $\mathbb{P}$. Observation: $\forall{B\in X:~}\exists{!(x_{B},A_{B})\in\mathcal{C}:~}A_{B}\subseteq B$, which gives rise to a choice function $B\in X\mapsto x_{B}$. $\endgroup$
    – Thomas
    Sep 10, 2014 at 16:47
  • $\begingroup$ Ach! Nee, the above does not work. I think the proof $Antichain-Principle\Longrightarrow AC$ really works with $(\mathbb{P},\leq)$ satisfying simply transitive+reflexive. In which case the problem remains, that $A’$ is not necessarily an antichain. $\endgroup$
    – Thomas
    Sep 11, 2014 at 8:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .