Infinite Set has Countably Infinite Subset

Theorem

Every infinite set has a countably infinite subset.

Proof

Intuitive Proof

Let $S$ be an infinite set, and let $a_0 \in S$.

$S$ is infinite, so $\exists a_1 \in S, a_1 \ne a_0$, and $\exists a_2 \in S, a_2 \ne a_0, a_2 \ne a_1$, and so on.

That is, we can continue to pick elements out of $S$, and assign them the labels $a_0, a_1, a_2, \ldots$ and this procedure will never terminate as $S$ is infinite.

Each one of the elements is in one-to-one correspondence with the elements of $\N$, and therefore the set $\left\{{a_0, a_1, a_2, \ldots}\right\} \subseteq S$ is countably infinite.

$\blacksquare$

Warning

The intuitive nature of this proof obscures the fact that it is not a trivial truth that one may choose elements of $S$ in this manner when $S$ is infinite.

A rigorous application of the principle of induction would show that while one may choose any finite value of $a_n$ in a step-by-step in ZF, but the Axiom of Countable Choice is required to choose a countably infinite number all at once.

Proof 1

Assume that $S$ is an infinite set which has no countably infinite subset.

Suppose there were an injection $\psi: \N \hookrightarrow S$.

Let $\operatorname{Im} \left({\psi}\right) = T$ be the image of $\psi$.

From Injection to Image is Bijection it follows that $\psi^{-1}: T \to \N$ is a bijection.

Thus by definition, $T$ is countably infinite subset of $S$, contrary to hypothesis.

So there could be no such injection.

From Between Two Sets Exists Injection or Surjection, it follows that there is function $\phi: \N \to S$ which is surjective but not injective.

Thus from Surjection iff Right Inverse, $\phi$ has a right inverse $\phi^{-1}: S \to \N$ such that $\phi \circ \phi^{-1} = I_S$.

From Right Inverse Mapping is Injection, it follows that $\phi^{-1}$ is injective.

But from Injection from Infinite to Countably Infinite Set it follows that $S$ is countably infinite.

So from Subset of Itself $S$ has a subset $S$ which is countably infinite.

Hence the result from proof by contradiction.

$\blacksquare$

Proof 2

This proof follows the same steps as the intuitive one, but with more formality.

Let $S$ be an infinite set.

First an injection $f: \N \to S$ is constructed.

Let $g$ be a choice function on $\mathcal P \left({S}\right) \setminus \left\{{\varnothing}\right\}$.

Then define $f: \N \to S$ as follows:

$\forall n \in \N: f \left({n}\right) = \begin{cases} g \left({S}\right) & : n = 0 \\ g \left({S \setminus \left\{{f \left({0}\right), \ldots, f \left({n - 1} \right)}\right\} }\right) & : n > 0 \end{cases}$

Since $S$ is infinite, $S \setminus \left\{{f \left({0}\right), \ldots, f \left({n - 1} \right)}\right\}$ is non-empty for each $n \in \N$, so $f \left({\N}\right)$ is infinite.

To show that $f$ is injective, let $m, n \in \N$, say $m < n$.

Then:

$f \left({m}\right) \in \left\{{f \left({0}\right), \ldots, f\left({n-1}\right)}\right\}$

but:

$f \left({n}\right) \in S \setminus \left\{{f \left({0}\right), \ldots, f \left({n-1}\right)}\right\}$

Hence $f \left({m}\right) \ne f \left({n}\right)$.

Since $f$ is injective, it follows from Injection to Image is Bijection that $f$ is a bijection from $\N$ to $f \left({\N}\right)$.

Thus $f \left({\N}\right)$ is a countable subset of $S$.

$\blacksquare$

Proof 3

Let $S$ be an infinite set.

First an injection $f: \N \to S$ is constructed.

Let $f$ be a choice function on $\mathcal P \left({S}\right) \setminus \left\{{\varnothing}\right\}$.

That is:

$\forall A \in \mathcal P \left({S}\right) \setminus \left\{{\varnothing}\right\}: f \left({A}\right) \in A$

This is justified only if the Axiom of Choice is accepted.

Let $\mathcal C$ be the set of all finite subsets of $S$.

Let $A \in \mathcal C$.

Since $S$ is infinite it follows that $S \setminus A \ne \varnothing$.

So $S \setminus A \in \operatorname{Dom} \left({f}\right)$.

Let $g: \mathcal C \to \mathcal C$ be the mapping defined as:

$g \left({A}\right) = A \cup \left\{{f \left({S \setminus A}\right)}\right\}$

That is, $g \left({A}\right)$ is constructed by joining $A$ with the element that $f$ chooses from $S \setminus A$.

Consider the Recursion Theorem applied to $g$, starting with the set $\varnothing$.

We obtain a mapping $U: \N \to \mathcal C$ such that:

$U \left({x}\right) = \begin{cases} \varnothing & : x = 0 \\ U \left({n}\right) \cup \left\{{f \left({S \setminus U \left({n}\right)}\right)}\right\} & : x = n^+ \end{cases}$

where here $\N$ is considered as elements of the minimal infinite successor set $\omega$.

Consider the mapping $v: \N \to S$, defined as:

$\forall n \in \N: v \left({n}\right) = f \left({S \setminus U \left({n}\right)}\right)$

We have that, by definition of $v$:

$(1): \quad \forall n \in \N: v \left({n}\right) \notin U \left({n}\right)$

$(2): \quad \forall n \in \N: v \left({n}\right) \in U \left({n^+}\right)$

$(3): \quad \forall m, n \in \N: n \le m \implies U \left({n}\right) \subseteq U \left({m}\right)$

Then because $v \left({n}\right) \in U \left({m}\right)$ but $v \left({m}\right) \notin U \left({m}\right)$:

$(4): \quad \forall m, n \in \N: n < m \implies v \left({n}\right) \ne v \left({m}\right)$

So $(4)$ implies that $v$ maps distinct elements of $\N$ onto distinct elements of $S$.

Thus $v: \N \to S$ is an injection.

It follows from Injection to Image is Bijection that $v$ is a bijection from $\N$ to $v \left({\N}\right)$.

Thus $v \left({\N}\right)$ is the countable subset of $S$ that was required.

$\blacksquare$

Proof 4

Let $S$ be an infinite set.

For all $n \in \N$, let $\mathcal F_n = \left\{{T \subseteq S : \left\vert{T}\right\vert = n}\right\}$ where $\left\vert{T}\right\vert$ denotes the cardinality of $T$.

Then $\mathcal F_n$ is non-empty because an infinite set has subsets of any finite cardinality.

Using the axiom of countable choice, there exists a sequence $\left\langle{S_n}\right\rangle_{n \in \N}$ such that $S_n \in \mathcal F_n$ for all $n \in \N$.

Let $\displaystyle T = \bigcup_{n \in \N} S_n$. Then $T \subseteq S$.

For all $n \in \N$, $S_n$ is a subset of $T$ whose cardinality is $n$.

Hence $T$ is infinite.

Because the countable union of finite sets is countable, $T$ is countable.

$\blacksquare$

Note

Although this is intuitively an "obvious" theorem, it is a theorem about cardinalities. The theory of cardinal numbers depends strongly on the axiom of choice. Without AoC one cannot guarantee "elementary" and "intuitive" results, like Surjection iff Right Inverse: if $f: X \to Y$ is surjective, then $\exists g: Y \to X$ injective. It is not true that only "complex" or "strange" results (like the Banach-Tarski Paradox, or the existence of a basis for $\R$ as a vector space over $\Q$) depend on the AoC.

Comment

What this in effect shows is that countably infinite sets are the smallest possible infinite sets.

Axiom of Countable Choice

This theorem depends on the Axiom of Countable Choice.

Although not as strong as the Axiom of Choice, the Axiom of Countable Choice is similarly independent of the Zermelo-Fraenkel axioms.

As such, mathematicians are generally convinced of its truth and believe that it should be generally accepted.

Sources

• Paul R. Halmos: Naive Set Theory (1960): $\S 15$: Axiom of Choice
• A.N. Kolmogorov and S.V. Fomin‎: Introductory Real Analysis (1968): $\S 2.2$: Theorem $3$
• Elon Lages Lima: Análise Real 1 (1989): $\S 1.3$
• Keith Devlin: The Joy of Sets: Fundamentals of Contemporary Set Theory (1993)