# Countable infinity and the axiom of choice

Many of the states of affairs about infinite cardinalities and their size, depend on the axiom of choice. What would a comprehensive list be of the properties of the cardinality of the natural numbers N, be if we do not allow anything beyond ZF set theory? Surprise me.

Another question would be about the axiom of countable choice? Why do people accept this but not the axiom of choice proper? It is not intuitive (only less counterintuitive). Yes you can choose an element one by one, but this "intuition" leads to an inductive proof of finite choice for arbitrarily large finite n, not countable choice...

Is it accepted more sheerly on a practical basis? Because a theoretical one seems nonexistent to me.

Edit: I realised this is two questions, but perhaps countable choice is at least a connection between the two.

• I'm not sure if my answer was what you were looking for. But there is really not much difference between ZF and ZFC when it comes to the natural numbers. – Asaf Karagila Nov 21 '12 at 14:39
• It is easy to be confused by some literature about the status of the axiom of choice. Almost all mathematicians "accept" the full axiom of choice. Of the small minority of those who do not, only a smaller minority nevertheless "accept" the axiom of countable choice. The main interest in the countable axiom of choice in set theory is that there are come models of ZF where the full axiom of choice cannot hold (because the models satisfy other things that contradict AC); some of those models do satisfy the countable axiom of choice, which makes useful to know what can be proved with it. – Carl Mummert Nov 21 '12 at 14:40
• I never know when to give writing advice, but the first question can be asked in one quick sentence: "What is a comprehensive list of facts about the countable cardinal that depend on the axiom of choice?" Lots of verbiage (and misplaced commas) in there to ask that question. You get more answers to questions if people can quickly figure out the question. – Thomas Andrews Nov 21 '12 at 14:58
• @CarlMummert There is a distinction between "accepting" something as an axiom and "accepting" that it is true. The latter is really not a mathematical statement but a belief system. – Thomas Andrews Nov 21 '12 at 20:45
• @Thomas: Who is we? I spoke to several prominent set theorists which expressed some questions about the usage of inaccessible cardinals in Wiles' proof of FLT. No number theorists they spoke with (and all of them asked prominent number theorists) cared about this fact. I always found large cardinals to be much more worrisome (in terms of consistency) than the axiom of choice. Why do people care about choice, but they don't care about large cardinals, then? – Asaf Karagila Nov 22 '12 at 0:10

The natural numbers are well-ordered without the axiom of choice. In fact they still serve as the definition for countability without the axiom of choice assumed. Therefore the basic things we know about the natural numbers hold regardless to the axiom of choice. In particular $\mathbb{N\times N}$ is still countable, and $\{A\subseteq\mathbb N\mid A\text{ is finite}\}$ is also countable.

However when the axiom of choice is negated some other weird things could happen in the power set of the natural numbers, and in other infinite sets:

1. There could be a set which is infinite, but has no countably infinite subset.
2. It could be that there are no free ultrafilters on the natural numbers.
3. It could be that the power set of the natural numbers cannot be well-ordered (it can still be linearly ordered, though).
4. Countable unions of general countable sets need not be countable.
5. It is possible that there is no linear basis for $\mathbb R$ over $\mathbb Q$.

Let us focus on the first one for a moment, such sets are known as infinite Dedekind-finite sets. Their existence contradicts the axiom of countable choice, so if we assume that we can prove that every infinite set has a countably infinite subset. The fourth one has the same properties, it negates the axiom of countable choice.

Both the second, third and fifth points, however, are compatible with countable choice.

As for why we accept the axiom of choice, historically we did not accept it. People found its consequence strange (regardless to the fact they have used it intuitively). After it was proved that assuming the axiom of choice does not add inconsistencies to ZF, people began using the axiom of choice more and see its wonderful applications. It simply made things easier.

• @JohnSmith: Of course. Those infinite sets which do not have a countably infinite subset are exactly those which are incomparable with $\aleph_0$. – Asaf Karagila Nov 21 '12 at 17:37