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

269 Views Asked by At

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?

Thanks in advance!

I edited.

1

There are 1 best solutions below

4
On BEST ANSWER

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.