## You are here

Homeproduct of countable sets

## Primary tabs

# product of countable sets

###### Proposition 1.

$\mathbb{N}^{2}$ is countable.

This is actually proved in this entry, by finding either a surjection $\mathbb{N}\to\mathbb{N}^{2}$, or an injection $\mathbb{N}^{2}\to\mathbb{N}$. In the following proof, we are going to get a bijection.

###### Proof.

There are many ways to prove this. One way is to place the integer pairs in a two-dimensional array indicated by the table on the left below:

$i\backslash j$ | $1$ | $2$ | $3$ | $\cdots$ |
---|---|---|---|---|

$1$ | $(0,0)$ | $(0,1)$ | $(0,2)$ | $\cdots$ |

$2$ | $(1,0)$ | $(1,1)$ | $(1,2)$ | $\cdots$ |

$3$ | $(2,0)$ | $(2,1)$ | $(2,2)$ | $\cdots$ |

$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\ddots$ |

$i\backslash j$ | $1$ | $2$ | $3$ | $\cdots$ |
---|---|---|---|---|

$1$ | $1$ | $2$ | $4$ | $\cdots$ |

$2$ | $3$ | $5$ | $8$ | $\cdots$ |

$3$ | $6$ | $9$ | $13$ | $\cdots$ |

$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\ddots$ |

Let $C(i,j)$ be the content of cell $(i,j)$, located in the $i$-th row and $j$-th column. For example, $C(1,1)=(0,0)$, and $C(3,2)=(2,1)$.

Now, let us construct a list of the pairs, which essentially amounts to constructing a bijection $h:\mathbb{N}^{2}\to\mathbb{N}$ (the table on the right above). We start at cell $(1,1)$. If cell $(i,j)$ has been counted, the next cell to be counted is $(i+1,j-1)$ if $j>1$, or $(1,i+1)$ if $j=1$. Thus, the first several pairs on the list are

$(0,0),\;(0,1),\;(1,0),\;(0,2),\;(1,1),\;(2,0),\;(0,3),\;\ldots$ |

We leave it to the reader to find the bijection $h$ (hint: see the entry on pairing function). Therefore, $\mathbb{N}^{2}$ is countable. ∎

###### Proposition 2.

If $A$ and $B$ are countable, so is $A\times B$.

###### Proof.

Suppose $f:A\to\mathbb{N}$ and $g:B\to\mathbb{N}$ are injections. Then $h:=(f,g):A\times B\to\mathbb{N}^{2}$ is an injection. Since $\mathbb{N}^{2}$ is countable, so is $A\times B$. ∎

###### Proposition 3.

Let $n$ be a positive integer, and $A_{1},\ldots,A_{n}$ sets. Then $A_{1}\times\cdots\times A_{n}$ is countable iff each $A_{i}$ is.

###### Proof.

Again, if one of $A_{i}$ is empty, so is the product, and vice versa. The countability follows immediately. So we assume that none of $A_{i}$ is empty. Set $A:=A_{1}\times\cdots A_{n}$.

Suppose first that $A_{1},\ldots,A_{n}$ are countable. We do induction on $n$. The case where $n=1$ is clear. Suppose now that $n=k$ is true. Then $A_{1}\times\cdots\times A_{k}\times A_{{k+1}}$ is just the product of two countable sets $A_{1}\times\cdots\times A_{k}$ and $A_{{k+1}}$, which we know is countable by the proposition above.

Conversely, suppose $A$ is countable. Let $g:A\to\mathbb{N}$ be an injection. Since $A_{i}\neq\varnothing$, fix $a_{i}\in A_{i}$ for each $i=1,\ldots,n$. Now, for any $A_{i}$, define a map $e_{i}:A_{i}\to A$ so that the $i$-th component of $e_{i}(a)$ is $a$, and the $j$-th component is the fixed element $a_{j}\in A_{j}$, if $j\neq i$. Clearly, $e_{i}:A_{i}\to A$ is an injection, so its composition with $g$ is also an injection from $A$ to $\mathbb{N}$, showing that $A_{i}$ is countable. ∎

###### Corollary 1.

For any positive integer $n$, $A$ is countable iff $A^{n}$ is.

Remark. However, infinite products of sets are in general uncountable, even if each of the sets is finite. In particular, $\{0,1\}^{{\mathbb{N}}}$ is uncountable. The proof uses Cantor’s diagonalization argument.

## 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