# equivalence between axiom of choice and Zorn's lemma in a particular case.

Define $A(x)$ and $Z(x)$ as follows.

$A(x)\Leftrightarrow$for every indexed family $(S_i)_{i\in I}$ of nonempty sets s.t. $\# I =x$, there exists an indexed family $(s_i)_{i\in I}$ s.t. $s_i \in S_i$ for every $i\in I$.

$Z(x)\Leftrightarrow$for every inductive ordered set $X$ s.t. $\# X =x$ and for every $a\in X$, there exists $b\in X$ s.t. $a\leq b$ and for every $c\in X$ $b\leq c$ implies b=c.

Does $A(x) \Leftrightarrow Z(x)$ holds?

I edited.

• Your formulation for $Z(x)$ is probably not what you meant. – Hagen von Eitzen Jul 12 '13 at 12:39
• Yes, $Z(x)$ should be "There exists $b\in X$ such that for every $a\in X$, $a\geq b$ implies $a=b$." – Thomas Andrews Jul 12 '13 at 12:50
• The usual restriction of Zorn's lemma is not by limiting the size of the poset, but rather limiting the length of the well-ordered chains. – Asaf Karagila Jul 12 '13 at 13:10

Let me assume that you want the proof to be in $\sf ZF$ and not in $\sf ZFC$, where both the statements are provable and therefore provably equivalent. The answer is negative. Let me explain why using a very violent image, and then give the reason as to why we can't prove this.

Suppose that you are set to kill someone. It doesn't matter if you have killed them with a spoon, or with a chainsaw, or a gun, or a nuclear bomb. True, it's much easier to kill someone with a gun than it is with a spoon; and death by a spoon is likely to cause vastly less collateral damage than death by a low yield nuclear device. But if you have managed to kill that someone, then you mission is done. All the methods are equivalent for that matter. They are dead.

If, on the other hand, you failed in your mission, for one reason or another, then the methods are no longer equivalent. Failing to kill someone with a spoon is likely to leave them with a few black and blue marks that will pass after a few days. Failing to kill someone with a gun may leave them paralyzed. Failing to kill someone with a nuclear bomb is likely to leave them with a good radiation dose that (if comic books and '50s horror B-movies are of any indication) will turn them into an angry fifty feet green zombie-monster that is likely to destroy Tokyo and other major cities.

So if you managed to kill your victim, it's fine and every method of execution was equally satisfactory. But if you failed to kill your victim, then a lot of different methods are no longer equivalent.

Similarly, the axiom of choice have many many many equivalents. Because when the axiom of choice holds in its full power it kills a lot of the pathologies, and we are left with a bunch of well-behaved sets. But when the axiom of choice fails, and we want to know whether or not certain restrictions of the axiom of choice are equivalent then the answers are usually negative. Let me give you an example:

The axiom of choice is equivalent to the trichotomy. That is to say, the axiom of choice holds if and only if every two cardinals are comparable. So we can ask whether or not the statement "Every cardinal is comparable with $\aleph_1$" is equivalent to the statement "Every family of $\aleph_1$ non-empty sets admits a choice function". The answer is no. In fact the answer is so negative that even assuming "Every well-ordered family of non-empty sets admits a choice function" is not sufficient to imply that every cardinal is comparable with $\aleph_1$. Similarly even if every set is comparable with $\aleph_1$ it does not imply the axiom of countable choice.

The reason that nonequivalence happens when we make these restrictions is that we use a varying degree of choice when we prove the full axiom of choice from Zorn's lemma, or from the well-ordering theorem. We use choice functions on very large sets, or partial orders whose cardinality is very large to end up with a choice function of a relatively small family of sets.

For example, being able to choose from a countable family of countable sets is not enough in order to prove that the countable union of countable sets is countable. The reason is that we need to choose a well-order for each of our sets, but there are $2^{\aleph_0}$ possible well-orderings to choose from, so we can't assure a choice function from this countable family of uncountable sets.

So finally, we reach to the problem at hand. Limiting Zorn's lemma to sets of a certain cardinality and limiting the axiom of choice to families of certain sizes.

Consider the case where $x=\omega$, a countably infinite set. One can trace the proof of Zorn's lemma and see that in $\sf ZF$ it holds that if $(X,\leq)$ is a set satisfying Zorn's lemma's hypothesis, and $X$ can be well-ordered, then there is a maximal element in $X$.

On the other hand, one cannot prove $\sf AC_\omega$, or as you denote it $A(\omega)$, from $\sf ZF$ itself.

Let me finish this already long answer by pointing out that the common restriction of Zorn's lemma is not to the size of the partial order, but rather to the length of its well-ordered chains. In that case $\sf ZL_\kappa$ is equivalent to $\sf DC_\kappa$, where $\sf DC_\kappa$ is the principle of dependent choice for $\kappa$. In that case $\sf DC_\kappa$ is strictly stronger than $\sf AC_\kappa$ for every $\aleph$ number $\kappa$.

I suppose that one can talk about $\sf DC_X$ for non-well orderable $X$, but no one has done that to my knowledge. Mostly because the whole motivation of $\sf DC$ is to define things by recursion, and we generally do recursion over ordinals.

• Asaf, it seems to me that your answer suggests an interesting "left-over" question. You've shown that $Z(x)$ comes nowhere near implying $A(x)$, since the former always holds (in ZF) for well-orfdered $x$ while the latter might not. What about the converse? I expect that it fails, i.e., that it's consistent (with ZF) for a poset $P$ to be a counterexample to Zorn's Lemma while $P$-indexed choice holds. But no example of this occurs to me immediately – Andreas Blass Jul 12 '13 at 15:00
• Andreas, I had the same hunch exactly but nothing immediate came to mind. I'll have some more free time later this evening, so I'll try to come up with an example. – Asaf Karagila Jul 12 '13 at 15:03
• A tangential comment: There is a version of Zorn's Lemma that assumes that every chain has not merely an upper bound but a least upper bound. That version for a poset $P$ is deducible, by the usual proof, from $P$-indexed choice. The point is that $P$-indexed choice suffices if there is a function assigning, to each chain, one of its upper bounds. Least upper bounds provide such a function. – Andreas Blass Jul 12 '13 at 16:43
• @Andreas: Ah yes, the chain-complete variant with Bourbaki-Witt theorem. I think I know why it is so difficult to come up with a counterexample to the other implication (although I am certain one exists). We hardly work in contexts of $\sf AC_\frak m$, where $\frak m$ is a general cardinal. – Asaf Karagila Jul 12 '13 at 21:28