Is axiom of choice necessary for proving that every infinite set has a countably infinite subset?
Is it possible to prove the following fact without axiom of choice ?
" Every infinite set has a countably infinite subset". Can it be proved that axiom of choice is necessary here ?
Solution 1:
First let us clear up the definitions, since there may be some confusion about them.
We say that a set $A$ is finite, if there is a natural number $n$ and a bijection between $A$ and $\{0,\ldots,n-1\}$. If $A$ is not finite, we say that it is infinite.
We say that a set $A$ is Dedekind-finite, if whenever $f\colon A\to A$ is an injective function, then $f$ is a bijection. If $A$ is not Dedekind-finite, we say that it is Dedekind-infinite.
What can we say immediately?
- Every finite set is Dedekind-finite, and every Dedekind-infinite set is infinite.
- $A$ is Dedekind-infinite if and only if it has a countably infinite subset if and only if there is an injection from $\Bbb N$ into $A$.
- Equivalently, $A$ is Dedekind-finite if and only if it has no countably infinite subset if and only if there is no injection from $\Bbb N$ into $A$.
While in some low-level courses the definitions may be given as synonymous, the equivalence between finite and Dedekind-finite (or infinite and Dedekind-infinite) requires the presence of countable choice to some degree. This was shown originally by Fraenkel in the context of $\sf ZFA$ (where we allow non-set objects in our universe), and later the proof was imitated by Cohen in the context of forcing and symmetric extensions for producing a model of $\sf ZF$ without atoms where this equivalence fails.
Interestingly enough, Dedekind-finiteness can be graded into various level of finiteness, so some sets are more finite than others. For example, it is possible for a Dedekind-finite set to be mapped onto $\Bbb N$, which in some way makes it "less finite" than sets which cannot be mapped onto $\Bbb N$.
Solution 2:
This cannot be proved without the axiom of choice. A set with no countably infinite subset is called a Dedekind-finite set. An equivalent characterization is that the set is not in one-to-one correspondence with any proper subset of itself. This condition is equivalent to finiteness in ZFC but not in ZF. (See https://en.wikipedia.org/wiki/Dedekind-infinite_set and the references there for more information.)