Every Infinite Subset of N is Countably Infinite

# Every Infinite Subset of N is Countably Infinite

We will now look at some theorems regarding countable and uncountable sets.

 Theorem 1: Every infinite subset of $\mathbb{N}$ is countably infinite.
• Proof: Let $A \subseteq \mathbb{N}$ be an infinite set. Since $A$ is an infinite set, $A$ is nonempty. Furthermore, we are given that $A$ is a subset of $\mathbb{N}$. By the well-ordering principle the set $A$ contains a least element, call it $f(1)$.
• Now consider the set $A \setminus \{ f(1) \}$, which is also a nonempty infinite subset of the natural numbers. Again by the well-ordering principle the set $A \setminus \{ f(1) \}$ contains a least element, call it $f(2)$.
• We continue indefinitely and define $f : \mathbb{N} \to A$ by this rule. We claim that $f$ is a bijection.
• First let $m, n \in \mathbb{N}$ and suppose that $f(m) = f(n)$. Then $f(m)$ is the least element of the set $A \setminus \{ f(1), f(2), ..., f(m-1) \}$ and $f(n)$ is the least element of $A \setminus \{ f(1), f(2), ..., f(n-1) \}$. If $m \neq n$ then either $m < n$ or $m > n$. Without loss of generality, suppose that $m < n$. Then:
(1)
\begin{align} \quad A \setminus \{ f(1), f(2), ..., f(m-1) \} \supseteq A \setminus \{ f(1), f(2), ..., f(m-1), f(m), ..., f(n-1) \} \end{align}
• But the two sets above have the same least element which is a contradiction by the definition of $f$. So we must indeed have that $m = n$. So $f$ is injective.
• Now let $a \in A$. Then $a$ is some finite number, and one of $f(1), f(2), ..., f(a)$ must equal $a$. In other words, for some $n \in \{ 1, 2, ..., a \}$ we have that $f(n) = a$. So $f$ is surjective.
• Therefore $f : \mathbb{N} \to A$ is a bijection, so $A$ is countably infinite. $\blacksquare$
 Theorem 2: Let $A$ and $B$ be sets and suppose that $A \subseteq B$. If $B$ is countable then $A$ is countable.
• Proof: First suppose that $B$ is finite. Then clearly any subset $A$ of $B$ is also finite and hence countable.
• So suppose that $B$ is countably infinite. If $A$ is finite we are done so we can assume that $A$ is an infinite set. Then there exists a bijection $f : B \to \mathbb{N}$. Observe that $f_A : A \to f(A)$ defined for all $a \in A$ by $f_A(a) = f(a)$ is a bijection.
• Now since $f$ is bijection we have that $f(B) = \mathbb{N}$. Note that:
(2)
\begin{align} \quad f_A(A) = f(A) \subseteq f(B) = \mathbb{N} \end{align}
• So $f_A(A)$ is an infinite subset of the natural numbers. By Theorem 1 this implies that $f_A(A)$ is countably infinite. So there exists a bijection $g : f_A(A) \to \mathbb{N}$. Consider the composition $g \circ f_A : A \to \mathbb{N}$. Since $g$ and $f_A$ are both bijections, their composition is also a bijection, and so $A$ is countably infinite. $\blacksquare$
 Corollary 3: Let $A$ and $B$ be sets and suppose that $A \subseteq B$. If $A$ is uncountable then $B$ is uncountable.
• Proof: The statement in corollary 3 is logically equivalent to theorem 2, that is, corollary 3 is simply the contrapositive of theorem 2. $\blacksquare$
 Corollary 4: Let $A$ be a set. If $f : A \to \mathbb{N}$ is injective then $A$ is countable.
• Proof: Suppose that $f : A \to \mathbb{N}$ is injective. If $A$ is finite then we are done. So assume that $A$ is infinite Observe that $f(A) \subseteq \mathbb{N}$. So $f(A)$ is an infinite subset (since $f$ is injective) of $\mathbb{N}$. By Theorem 1 this implies that $f(A)$ is countably infinite. Hence $A$ is countably infinite and so it is countable. $\blacksquare$