Infinite set and countable subsets

Prove that a set $A$ is infinite if and only if $A$ contains a countable subset $C$. I know I have to build a sequence and then I'll get a countable subset, but I don't know how to build that sequence from a infinite set.

Solution 1:

This actually requires the axiom of choice. Basically, you just do it. Let $a_0$ be any element of $A$. $A\ne\{a_0\}$, since $A$ is infinite, so $A\setminus\{a_0\}\ne\varnothing$. Thus, we can pick some $a_1\in A\setminus\{a_0\}$. $A\ne\{a_0,a_1\}$, since $A$ is infinite, so $A\setminus\{a_0,a_1\}\ne\varnothing$, and we can pick some point $a_2\in A\setminus\{a_0,a_2\}$. In general, at stage $n$ we have distinct points $a_0,\dots,a_{n-1}$. $A\setminus\{a_0,\dots,a_{n-1}\}\ne\varnothing$, since $A$ is infinite, so we can pick $a_n\in A\setminus\{a_0,\dots,a_{n-1}\}$ and continue the construction. When we’re done, we just set $C=\{a_n:n\in\Bbb N\}$.

Solution 2:

You cannot define the sequence in explicit formula, but you can do that by induction.

Since $A$ is infinite it is not empty, pick some $a_0\in A$, define $A_0=A\setminus\{a_0\}$. We only removed one element from $A$ so $A_0$ is also infinite.

Suppose that $a_n$ was chosen and $A_n$ defined and infinite. Since $A_n$ is infinite it is non-empty and we can choose $a_{n+1}\in A_n$, and define $A_{n+1}=A_n\setminus\{a_n\}$.

The induction is well-defined for every natural number $n$. We only have to show now that $a_n\neq a_m$ for $n\neq m$. However it is trivial since if $n<m$ then $a_m$ was chosen from a set which does not contain $a_n$ at all, so they cannot be equal.

Solution 3:

If we want to construct an infinite sequence, we should start by picking an element $x\in A$. We want each term in the sequence to be different from the previous ones, so that we can ensure that the sequence is infinite. So we look for an element in $A-\{x\}$. Does $A-\{x\}$ have an element?

Keep repeating this procedure. After you have chosen $x_1, ... , x_n$, can we find an element in $A- \{x_1,...,x_n\}$?

Solution 4:

I assume that you define "infinite" as: There exists a map $f\colon A\to A$ that is injective but not surjective. Select $a_0\in A\setminus f(A)$ and define recursively $a_{n+1}=f(a_n)$. Then the map $\mathbb N\to A$, $n\mapsto a_n$ is injective, hence its image is a countable subset $C$ as desired. Why is this map injective? If $a_n=a_m$ with $n\ne m$, then clearly $n\ne0$ and $m\ne 0$ as $a_0\notin f(A)$, whereas $a_k\in f(A)$ for all $k\ne0$. But then we conclude from the injectivity of $f$ that $a_{n-1}=a_{m-1}$ as well and so on (you can reformukate this to a proper induction proof).

If on the other hand $C\subset A$ and $C$ is countable via $g\colon \mathbb N\to C$, you can define $$ f(x) = \begin{cases}g((g^{-1}(x)+1) & \mathrm{if\ }x\in C\\x&\mathrm{otherwise}\end{cases}$$ and thus show that $A$ is infinite.