The set of counting numbers, or of positive integers, is the set $~$\mathbb{Z}^+ = \{1, 2, 3, 4, \ldots\}$~$.
A set $~$S$~$ is called countable or enumerable if there exists a surjection from the counting numbers onto $~$S$~$.
Example: The rational numbers
The set of rational numbers, $~$\mathbb Q$~$, is the set of integer fractions $~$\frac{p}{q}$~$ in reduced form; the greatest common divisor of $~$p$~$ and $~$q$~$ is one, with $~$q > 0$~$.
Theorem The rational numbers are countable.
The proof is, essentially, that $~$\mathbb Z^+ \times \mathbb Z^+$~$ is isomorphic to $~$\mathbb Z$~$; we count in a roughly spiral pattern centered at zero.
Proof Define the height of $~$\frac{a}{b}$~$ to be $~$|a| + |b|$~$. We may count the rational numbers in order of height, and ordering by $~$a$~$, and then $~$b$~$, when the heights are the same. The beginning of this counting is $~$0 / 1$~$, $~$-1 / 1$~$, $~$1 / 1$~$, $~$-2 / 1$~$, $~$-1 / 2$~$, $~$1 / 2$~$, $~$2 / 1$~$, $~$\ldots$~$ Since there are at most $~$(2d+1)^2$~$ rational numbers of height less than or equal to $~$d$~$, a rational number with height $~$d$~$ is mapped on to by one of the counting numbers up to $~$(2d+1)^2$~$; every rational number is mapped onto by this counting. Thus, the rational numbers are countable. $~$\square$~$
Note: It is not hard to extend this proof to show that $~$(\mathbb Z^+)^n$~$ is countable for any finite $~$n$~$.
Theorem If there exists a surjection $~$f$~$ from a countable set $~$A$~$ to a set $~$B$~$, then $~$B$~$ is countable. Proof By definition of countable, there exists an enumeration $~$E$~$ of $~$A$~$. Now, $~$E\circ f$~$ is an enumeration of $~$B$~$, so $~$B$~$ is countable.
Exercises
Show that the set $~$\Sigma^*$~$ of [ finite words] of an enumerable [ alphabet] is countable.
%%hidden(Show solution): First, we note that since $~$\mathbb N^n$~$ is countable, the set of words of length $~$n$~$ for each $~$n\in \mathbb N$~$ is countable.
Let $~$E_n: \mathbb N \to \mathbb N^n$~$ stand for an enumeration of $~$\mathbb N ^n$~$, and $~$(J_1,J_2)(n)$~$ for an enumeration of $~$\mathbb N^2$~$.
Consider the function $~$E: \mathbb N \to \Sigma^* , n\hookrightarrow E_{J_1(n)}(J_2(n))$~$ which maps every number to a word in $~$\Sigma^*$~$. Then a little thought shows that $~$E$~$ is an enumeration of $~$\Sigma^*$~$.
$~$\square$~$ %%
Show that the set $~$P_\omega(A)$~$ of finite subsets of an enumerable set $~$A$~$ is countable.
%%hidden(Show solution): Let $~$E$~$ be an enumeration of $~$A$~$.
Consider the function $~$E': \mathbb N^* \to P_\omega(A)$~$ which relates a word $~$n_0 n_1 n_2 … n_r$~$ made from natural numbers to the set $~$\{a\in A:\exists m\le k E(n_m)=a\}\subseteq A$~$. Clearly $~$E'$~$ is an enumeration of $~$P_\omega(A)$~$. %%
Show that the set of [ cofinite subsets] of an enumerable set is countable.
%%hidden(Show solution): Simply consider the function which relates each cofinite set with its complementary. %%