How can choice fail in ZF?

Question

I don't see how the Axiom of Choice can fail in ZF. By transfinite induction you can demonstrate larger and larger ordinals, using union and pairing to show the successor and limit steps, so that for any set there exists a one to one correspondence with at least one of these ordinals. "Following the arrow" of this one to one correspondence assigns ordinals (elements of the ordinal) to the elements of the set, which produces a well ordering of the set. For a set to exist with no well ordering, there has to be a cardinality (that of the set) that is bigger than any ordinal. The transfinite induction mentioned above has to fail before reaching that cardinality. How does that happen? I'm no mathematician so appreciate a correction in simple terms if possible.

Answer 1

I suppose that you mean the proof of the well-ordering theorem.

You construct an injective function from a set $X$ into an ordinal. At each step you choose an arbitrary element. And at limit steps you want to be sure that all your previous steps are coherent.

And these two things you can't really pull transfinitely without the axiom of choice. The proof, without choice, really just give you two things:

1. If you could construct a partial injection into $\alpha$, and the domain of the partial injection is not the entire set, then you can extend it by one step.

2. If you could construct a sequence of partial injections into an increasing sequence of ordinals, and the partial injections are compatible, then the union is a partial injection from the union of the domains into the limit of the sequence.

But in order to ensure that you actually have this sequence at limit steps, you needed the axiom of choice.

This is a detail often forgotten, but what you really do when you begin this proof is fix a choice function on non-empty subset of $X$, and at each step you use the choice function to "guess" the next element to be chosen; and this also ensures that at a limit step the injections are compatible, since you never mapped two elements to the same ordinal or tried to give one element two values.

And just let me finish by remarking that for a set to be non well-orderable, you don't have it with cardinality "bigger than all the ordinals", rather you have it with cardinality incomparable with most of the ordinals.

Answer 2

You are correct that you can construct the ordinals and prove they can have unboundedly large cardinality without Choice. However, the problem with your argument is that you can't explicitly write down a correspondence between elements of your set and ordinals without a choice function on subsets of your set.

To see this more clearly, let's make your argument more precise. Fix a set $S$. You are trying to well-order $S$ by defining a function $F:Ord\to S$ by induction as follows. Having defined $F(\beta)$ for all $\beta<\alpha$, you defined $F(\alpha)$ to be some element of $S$ which is not equal to $F(\beta)$ for any $\beta<\alpha$, if such an element exists. If not, you stop the induction.

If this induction stops, great: if you stop at $\alpha$, that means that $F$ is a bijection between the ordinals less than $\alpha$ and $S$, which you can use to well-order $S$. If this induction never stops, it defines an injection $F:Ord\to S$ ($S$ has "cardinality that is bigger than any ordinal", in your words). Since the ordinals form a proper class, this contradicts the Axiom of Replacement.

However, there is a problem with the above argument: the function $F$ is not precisely defined! To define $F(\alpha)$, you have to specify how you are choosing an element of $S$ which is not equal to $F(\beta)$ for any $\beta<\alpha$. If you have a choice function $c$ on the nonempty subsets of $S$, this is easy: just define $F(\alpha)=c(S\setminus\{F(\beta)\}_{\beta<\alpha})$. But without such a choice function, there is no way to define $F(\alpha)$ in general.

As a final note, in the absence of Choice, it is not true that cardinalites are totally ordered. So just because the cardinalities of ordinals are unbounded, that doesn't mean you can't have another cardinality which is not smaller than that of any ordinal: such a cardinality must simply be incomparable with (neither less than nor greater than) the cardinalities of most ordinals.