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 one-to-one correspondence between the set $F(A)$ of finite sets and the set $\mathrm{co}-F(A)$ of cofinite sets: $X\mapsto A-X$.

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 $𝔸$ 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, $𝔸$ 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}}⟺\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 $𝔸=\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.