# "Proving" the axiom of choice in ZF.

I was trying to explain the difference between formal and informal proofs - and why informal proofs are not always "good enough" - to my brother when I came up with an example of an informal proof (in ZF) which, on the surface, appears to be a proof of the axiom of choice.

The argument goes like this:

By definition, every infinite cardinal is an initial ordinal and every ordinal corresponds to the order-type of a well ordered set (namely the ordinal itself, ordered by set membership).

A set $$X$$ has cardinality $$\kappa$$ iff - provided some ordering relation on $$X$$ - $$X$$ is order-isomorphic to $$\kappa$$.*

Because $$\kappa$$ is an initial ordinal, the order on $$\kappa$$ is a well-order. In order for $$X$$ to be order-isomorphic to $$\kappa$$, $$X$$ must be well-orderable.

Because every set has a cardinality, it follows that every set is well-orderable - thus proving the well-ordering principle. It is well-known that the well-ordering principle is equivalent to the axiom of choice. Thus, we have proven the axiom of choice.

I suspect that the critical error is in assuming that the existence of a cardinal $$\kappa$$ such that $$|X|=\kappa$$ is the same as "ZF proves $$|X|=\kappa$$". Certainly, ZF is sufficient to prove or disprove that the cardinality of a finite set is equal to a given cardinal; for infinite sets I'm not sure that this is the case.

This raises the question: can ZF, plus some independent means of cardinal assignment, be used to prove AC? Alternatively, is there an extension of ZF in which the cardinality of every set can be proven without AC?**

*It is not strictly necessary that $$X$$ (under a given order) be order-isomorphic to $$\kappa$$ for $$|X|=\kappa$$. However, the nonexistence of an ordering relation such that $$X$$ is order-isomorphic to $$\kappa$$ strictly requires that $$|X|\ne\kappa$$. Most proofs that a set has a given cardinality make implicit use of this fact. For example, Cantor's proof of the countability of the rationals makes use of a well-order on $$\Bbb{N}^2$$ to show that $$\Bbb{N}^2\cong\omega=\aleph_0$$.

**While it may not be necessary that every set have a cardinality in order to prove AC, a theory capable of proving the cardinality of every set would be able to prove AC. This is more-or-less the missing piece of my original argument.

• The problem is not with decidability, in general ZF models there are sets that are (provably) not well-orderable. "Some independent means of cardinal assignment" produce messy structures with mostly incomparable elements, well-ordering or AC are not coming out of that. And if "proving the cardinality of every set" means "proving that every set is well-orderable" that obviously implies AC. Jan 3, 2020 at 22:53
• Thank you. 1) Do you have any examples of "independent means of cardinal assignment"? 2) My understanding was that if you can prove that a given set has a particular cardinality, then you can prove that it is well-orderable - so any extension of ZF capable of proving the cardinality of any set is capable of proving the well-ordering principle and thus AC. Jan 3, 2020 at 23:20
• Just take every class of equipotent sets as a "cardinal", as Cantor originally suggested. Then every set trivially has a particular "cardinality", but it implies nothing about well-ordering. On the other hand, if by "cardinality" you mean the class of a well-ordered set, and any given set "has it", then there is nothing left to prove. Jan 3, 2020 at 23:56
• "Because every set has a cardinality..." What is a cardinality?..... & Assuming that every set is bijective to some cardinal ordinal is assuming AC. Jan 4, 2020 at 2:12
• This has nothing to do with formal or informal proofs. You used the wrong definition. There are deeper problems, but they only appear when you try to find the mistake. Those problems are more serious, by the way. Jan 4, 2020 at 19:12

• Though I appreciate the point you make, I was more asking about an extension of ZF in which the cardinality of every set can be proven - i.e. $\vdash |X|=\kappa$ or $\vdash |X|\ne\kappa$ for any set $X$ and cardinal $\kappa$. This is subtly different from the provability of the fact that every set has a cardinality. I will try to be more clear on this. Jan 3, 2020 at 22:57
• Given an arbirtary set $X$ and cardinal $\kappa$ prove that $|X|=\kappa$ or prove that $|X|\ne\kappa$. In this case, I am assuming that every cardinal is an initial ordinal (or an equivalence class of ordinals). Jan 3, 2020 at 23:11
• Not even ZFC can do that, not even for $X=\Bbb R$ and $\kappa=\aleph_1$. So... what do you mean, again? And without choice, why would $\Bbb R$ even be provably well-orderable? Jan 3, 2020 at 23:12
• @R.Burton: ZF cannot even decide whether $\{x\in\{0\}\mid\operatorname{Con}({\sf ZF})\}$ is empty. Where does choice enter the equation? Nowhere, that's where. Jan 3, 2020 at 23:24