# examples of countable sets

This entry lists some common examples of countable sets.

Derived Examples

1. 1.
2. 2.

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

3. 3.

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

4. 4.
5. 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. 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 $\operatorname{co-}F(A)$ of cofinite sets: $X\mapsto A-X$.

7. 7.
###### 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,\ldots$. Since each $A^{i}$ is countable (because $A$ is), and we are taking a countable union, $A_{F}$ is countable as a result. ∎

8. 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. 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)\neq a\}$, and denote it by $\operatorname{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|\operatorname{supp}(f)$ is an injection: if $G(f)=G(h)$, then $f(b)=h(b)$ for any $b\in\operatorname{supp}(f)=\operatorname{supp}(h)$, and $f(b)=a=h(b)$ otherwise, whence $f=g$. But since $X$ is countable, so is $Y$. ∎

Concrete Examples

1. 1.
2. 2.
###### 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+\cdots+a_{n}X^{n}\qquad\Longleftrightarrow\qquad v_{p}=(a_{0},a% _{1},\ldots,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. 3.
4. 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 ExamplesOfCountableSets 2013-03-22 19:02:59 2013-03-22 19:02:59 CWoo (3771) CWoo (3771) 10 CWoo (3771) Example msc 03E10 AlgebraicNumbersAreCountable