examples of countable sets
This entry lists some common examples of countable sets.
Derived Examples

1.
any finite set^{}, including the empty set^{} $\mathrm{\varnothing}$ (proof (http://planetmath.org/AlternativeDefinitionsOfCountable)).

2.
any subset of a countable set (proof (http://planetmath.org/SubsetsOfCountableSets)).

3.
any finite product of countable sets (proof (http://planetmath.org/UnionOfCountableSets)).

4.
any countable^{} union of countable sets (proof (http://planetmath.org/ProductOfCountableSets)).

5.
the set of all finite subsets of a countable set.
Proof.
Let $A$ be a countable set, and $F(A)$ the set of all finite subsets of $A$. Let ${A}_{n}$ be the set of all subsets of $A$ of cardinality at most $n$. Then ${A}_{1}$ is countable, since $A$ is. Suppose now that ${A}_{n}$ is countable. The function $f:{A}_{n}\times {A}_{1}\to {A}_{n+1}$ where $f(X,Y)=X\cup Y$ is easily seen to be onto. Since ${A}_{n}\times {A}_{1}$ is countable, so is ${A}_{n+1}$. Now, $F(A)$ is just the union of all the countable sets ${A}_{i}$, and this union is a countable union, we see that $F(A)$ is countable too. ∎

6.
the set of all cofinite subsets of a countable set. This is true, because there is a onetoone correspondence between the set $F(A)$ of finite sets and the set $\mathrm{co}F(A)$ of cofinite sets: $X\mapsto AX$.

7.
the set of all finite sequences^{} over a countable set.
Proof.
Let $A$ be a countable set, and ${A}_{F}$ the set of all finite sequences over $A$. An element of ${A}_{F}$ can be identified with an element of ${A}^{n}$, and vice versa (the bijection is clear). Therefore, ${A}_{F}$ can be identified with the union of ${A}^{i}$, for $i=0,1,2,\mathrm{\dots}$. Since each ${A}^{i}$ is countable (because $A$ is), and we are taking a countable union, ${A}_{F}$ is countable as a result. ∎

8.
fix countable sets $A,B$. The set $X$ of all functions from finite subsets of $B$ into $A$ is countable.
Proof.
For each finite subset $C$ of $B$, the set of all functions from $C$ to $A$ is just ${A}^{C}$, which has cardinality ${A}^{C}$, and thus is countable since $A$ is. Since $X$ is just the union of all ${A}^{C}$, where $C$ ranges over the finite subsets of $B$, and there are countably many of them (as $B$ is countable), $X$ is also countable. ∎

9.
fix countable sets $A,B$ and an element^{} $a\in A$. The set $Y$ of all functions from $B$ to $A$ such that $f(b)=a$ for all but a finite number of $b\in B$ is countable.
Proof.
For any $f:B\to A$, call the support of $f$ the set $\{b\in B\mid f(b)\ne a\}$, and denote it by $\mathrm{supp}(f)$. Then every $f\in Y$ has finite support. The map $G:Y\to X$ (where $X$ is defined in the last example) given by $G(f)=f\mathrm{supp}(f)$ is an injection: if $G(f)=G(h)$, then $f(b)=h(b)$ for any $b\in \mathrm{supp}(f)=\mathrm{supp}(h)$, and $f(b)=a=h(b)$ otherwise, whence $f=g$. But since $X$ is countable, so is $Y$. ∎
Concrete Examples

1.
the sets $\mathbb{N}$ (natural numbers^{}), $\mathbb{Z}$ (integers), and $\mathbb{Q}$ (rational numbers^{})

2.
the set of all algebraic numbers^{}
Proof.
Let $\mathbb{A}$ be the set of all algebraic numbers over $\mathbb{Q}$. For each polynomial^{} $p$ (in one variable^{} $X$) over $\mathbb{Q}$, let ${R}_{p}$ be the set of roots of $p$ over $\mathbb{Q}$. By definition, $\mathbb{A}$ is the union of all ${R}_{p}$, where $p$ ranges over the set $P$ of all polynomials over $\mathbb{Q}$. For any $p\in P$ of degree $n$, we may associate a vector ${v}_{p}\in {\mathbb{Q}}^{n+1}$ :
$$p={a}_{0}+{a}_{1}X+\mathrm{\cdots}+{a}_{n}{X}^{n}\mathit{\hspace{1em}\hspace{1em}}\u27fa\mathit{\hspace{1em}\hspace{1em}}{v}_{p}=({a}_{0},{a}_{1},\mathrm{\dots},{a}_{n}).$$ The association can be reversed. So the set ${P}_{n}\subset P$ of all polynomials of degree $n$ is equinumerous to ${\mathbb{Q}}^{n+1}$, and therefore countable. As $P$ is just the countable union of all ${P}_{n}$, $P$ is countable, which means $\mathbb{A}=\bigcup \{{R}_{p}\mid p\in P\}$ is countable also. ∎

3.
the set of all algebraic integers^{}, because every algebraic integer is an algebraic number.

4.
the set of all words over an alphabet, because ever word can be thought of as a finite sequence over the alphabet, which is finite.
Title  examples of countable sets 

Canonical name  ExamplesOfCountableSets 
Date of creation  20130322 19:02:59 
Last modified on  20130322 19:02:59 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  10 
Author  CWoo (3771) 
Entry type  Example 
Classification  msc 03E10 
Related topic  AlgebraicNumbersAreCountable 