## You are here

Homeexamples of countable sets

## Primary tabs

# examples of countable sets

This entry lists some common examples of countable sets.

Derived Examples

1. any finite set, including the empty set $\varnothing$ (proof).

2. 3. any finite product of countable sets (proof).

4. any countable union of countable sets (proof).

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 $\operatorname{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,\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. 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)\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. 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+\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. the set of all algebraic integers, because every algebraic integer is an algebraic number.

4.

## Mathematics Subject Classification

03E10*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections