# 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 ?

• – Chris Culter Aug 14 '15 at 5:04
• Do you posses the technical knowledge to understand such an answer, or are you looking for a "yes" or "no" situation? – Asaf Karagila Aug 14 '15 at 5:35
• @AsafKaragila: Actually, I was reading some corollary of Bessel's inequality in functional analysis. Found that need to use that. – Sosha Aug 14 '15 at 6:42
• Haha, you really had a hard time deciding whose answer to accept! :-D – Asaf Karagila Aug 14 '15 at 10:50

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.)

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?

1. Every finite set is Dedekind-finite, and every Dedekind-infinite set is infinite.
2. $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$.
3. 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$.

Yes, some part of the axiom of choice is needed. In the absence of the axiom of choice it's consistent that there be an infinite, Dedekind finite set, and such a set admits no injection from $\Bbb N$.

If the definition for a set $A$ being infinite is $\exists f: \omega \to A$ injective, then in any model of ZF you can find a countably infinite subset of $A$ by taking the range of $f$ whose existence follows from replacement.

However, if the definition is $A$ is not finite, namely, there exists no bijection from $A$ to any $n\in \omega$, then the statement does not follow from ZF. In fact, in the model obtained by adjoining $\omega$ many Cohen reals (the forcing poset is $Fn(\omega\times\omega, 2)$ finite functions ordered by inclusion) then in its symmetric submodel $(HOD[G\cup \{G\}])^{M[G]}$, i.e. the class of hereditarily ordinal definable elements from $G\cup \{G\}$ in M[G] (which is a model of ZF), there exists a set that does not have countably infinite subset in the model $(HOD[G\cup \{G\}])^{M[G]}$, i.e. the set of Cohen reals $\{C_i: i\in \omega\}$ where $C_i(j)=G(i,j) \forall i,j\in\omega$. The reason is really that these Cohen reals can easily be permuted given finite information (aka the forcing is weakly homogeneous). You can refer to Jech's book on set theory for more details (there should be a chapter about symmetric submodes).

• This is not the standard definition of "infinite". – Eric Wofsey Aug 14 '15 at 5:10
• I just couldn't resist cheating sometimes :-(. – Jing Zhang Aug 14 '15 at 5:16

In very short terms (you are allready overwhelmed by good answers of experts):

$$\omega\leq_{1}A\implies\neg A<_{1}\omega$$ Or in words:$$A\text{ is Dedekind-infinite}\implies A\text{ is infinite}$$

But for the converse you need a weakened form of AC.

The axiom that every countable set has a choice-function (denoted as CC) will do.

This axiom implies that: $$A\leq_{1}\omega\vee\omega\leq_{1}A$$

• Just a minor remark, countable choice is in fact stronger than what needed; but one can show that if every Dedekind-finite set is finite, then we at least have countable choice from families of finite sets. So while there is no "accurate strength" in terms of "axiom of choice for such and such", we can place this assertion somewhere around countable choice. Surprisingly enough, the naive proof (by induction), requires more than countable choice to go through. – Asaf Karagila Aug 14 '15 at 10:49
• @AsafKaragila Interesting! At the moment I am reading a book about sets (to get wiser). I did not encounter yet what you mentioned. So equivalence of Dedekind-infinite and infinite does not imply CC? – drhab Aug 14 '15 at 10:51
• No, it does not. You can find a construction in Gordon Monro's paper "Independence results concerning Dedekind-finite sets" (last section). I think you might be able to find a similar construction in Jech "The Axiom of Choice" in Chapter 8 which deals with the various relations between comparability, partial choice and dependent choice principles. But the book is on the top shelf, and it's too hot to stand up and reach for it right now... :P – Asaf Karagila Aug 14 '15 at 10:58
• Thank you for this information. I have found the paper and will take a look there. – drhab Aug 14 '15 at 11:02
• I think there is something that Monro was unaware of, is that "partial countable choice" (that countable family has a countable subfamily which admits a choice function) is in fact equivalent to countable choice. So he did some extra work there. – Asaf Karagila Aug 14 '15 at 11:04