# Infinite Set has Countably Infinite Subset/Proof 3

Jump to: navigation, search

## Theorem

Every infinite set has a countably infinite subset.

## Proof

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$

#### Axiom of Choice

This proof depends on the Axiom of Choice.

Because of some of its bewilderingly paradoxical implications, the Axiom of Choice is considered in some mathematical circles to be controversial.

Most mathematicians are convinced of its truth and insist that it should nowadays be generally accepted.

However, others consider its implications so counter-intuitive and nonsensical that they adopt the philosophical position that it cannot be true.