I'm looking at the following in Jech's The Axiom of Choice on page 20:

2.4.1. Example: The Countable Axiom of Choice implies that every infinite set has a countable subset.

Proof. Let $S$ be an infinite set. Consider all finite one-to-one finite sequences $$\langle a_0 , a_1 , \ldots , a_k \rangle$$ of elements of $S$. The Countable Axiom of Choice picks out one $k$-sequence for each natural number; more exactly: $$\mathscr{F} = \{ A_k : k \in \omega \},$$ where $$A_k = \{ \langle a_0 , \ldots , a_k \rangle : a_0 , \ldots , a_k\text{ distinct elements of }S \},$$ and $\mathscr{F}$ has a choice function: $f ( A_k ) \in A_k$ for all $k$. The union of all the chosen finite sequences is obviously countable.

And I'm wondering if I can instead prove it as follows:

Let $S$ be an infinite set, that is, $|S| \ge |\omega|$. By the definition of $|S| \ge |\omega|$ there is an injection $f: \omega \hookrightarrow S$. Then $f(\omega) \subseteq S$ yields the desired result.

I think yes but I might be missing something. Thanks for your help.


It is likely that Jech is using the following definition: A set $X$ is infinite set iff it is not finite (i.e., there is no natural number $n$ such that $X$ is in one-to-one correspondence with $\{ 0 , \ldots , n-1 \}$). (I cannot find a statement of this definition in The Axiom of Choice, but Jech does use it in his Set Theory tome.) In the presence of some amount of Choice, being infinite is equivalent to $\aleph_0 \leq | X |$, but this is not a definition.

A set $X$ such that there is no injection $\mathbb{N} \to X$ is called a Dedekind finite set. It is consistent with ZF+$\neg$AC that there are infinite Dedekind finite sets. What this Example shows (once Dedekind finiteness is defined on p.25) is that under the assumption of Countable Choice all Dedekind finite sets are finite.

  • $\begingroup$ I'm sorry for asking a follow up question: I'm trying to show the "union of all the chosen finite sequences is obviously countable". Assume $f_n$ is the injection we chose for $n \hookrightarrow S$. Can I then argue as follows? Since $|\mathrm{im} f_n| = n$, and since $\bigcup_{n \in \omega} n = \omega$, it follows that $\bigcup_{n \in \omega} \mathrm{im} f_n = \omega$? $\endgroup$ – Rudy the Reindeer Apr 4 '13 at 11:54
  • 2
    $\begingroup$ @MattN. I think your argument only gives that $A = \bigcup_n \mathrm{im} f_n$ is infinite (after interpreting "$\bigcup_{n \in \omega} \mathrm{im} f_n = \omega$" in some reasonable manner). To establish countability you can define a bijection between $A$ and a subset of $\omega \times \omega$ ($h(a)$ is the lexicographically first $\langle i , j \rangle$ such that $f_i (j) = a$), and note that infinite subsets of $\omega \times \omega$ are countably infinite. $\endgroup$ – user642796 Apr 4 '13 at 12:17
  • 1
    $\begingroup$ @Matt: One can do that, but one has to establish first that the countable union of finite sets is countable. It's not difficult, and might be useful on its own. $\endgroup$ – Asaf Karagila Apr 4 '13 at 12:51
  • 1
    $\begingroup$ @Matt: Close enough. You need the $A_k$'s to be pairwise disjoint first. Or simply map $a\in\bigcup A_k$ to $(i,j)$ where $i$ is the least index such that $a\in A_i$ and $j$ is the index of $a$ in the selected enumeration of $A_i$. $\endgroup$ – Asaf Karagila Apr 4 '13 at 13:11
  • 1
    $\begingroup$ @MattN.: Your idea was clearly correct, just the details needed to be filled in -- and working without Choice sort of gnaws at you after a while as many of the usual intuitions are all of the sudden just plain wrong. $\endgroup$ – user642796 Apr 4 '13 at 13:12

We say that $S$ is infinite iff $|S|\not<|\omega|.$ Without some choice principle, we can't conclude that all infinite sets admit a countably infinite subset, as it's entirely possible that $S$ and $\omega$ are of incomparable cardinality.

The least choice principle sufficient to the task is: "$\omega$ is of comparable cardinality with all sets," a strictly weaker principle than $\text{AC}_\omega$. That is, any stronger principle will do the job, but weaker principles will fail to be able to prove that infinite sets have countably infinite subsets. On the other hand, if every infinite set has a countably infinite subset, then $\omega$ is of comparable cardinality with all sets. Thus, the aforementioned choice principle is actually logically equivalent to the result that Jech proves with $\text{AC}_\omega$.

We say that sets with a countably infinite subset are "Dedekind-infinite" or just "D-infinite." D-infinite sets are always infinite, but without a choice principle at least as strong as the one mentioned above, there may be infinite, D-finite sets.

For some equivalent statements to the choice principle I mentioned above, see here.

  • 1
    $\begingroup$ It's not just least, it's the "accurate bound". If it fails then there is an infinite set which is incomparable with $\aleph_0$, i.e. an infinite Dedekind-finite set. $\endgroup$ – Asaf Karagila Apr 3 '13 at 16:28
  • $\begingroup$ @Asaf: True. I will rephrase for precision. $\endgroup$ – Cameron Buie Apr 3 '13 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.