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.
 A: 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\}$.
A: 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.
A: 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\}$?
A: 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.
