---
tag: 08G4XH86JC
kind: statement
role: proposition
name: Product of countable sets is countable
msc: ["03E10"]
uses: [0ZG61TFBES, 0C81YBVTWH, 0NP5N5PYW5]
sources:
  - url: https://en.wikipedia.org/wiki/Countable_set
    locator: Formal overview
---

## Statement

Let $A$ and $B$ be [[countable sets|0ZG61TFBES]].
Then the [[Cartesian product|0C81YBVTWH]] $A \times B$ is countable.

## Remarks

Proof: take injections $f \colon A \to \mathbb{N}$ and $g \colon B \to \mathbb{N}$. Then $(a, b) \mapsto \pi(f(a), g(b))$ is an injection to $\mathbb{N}$, where $\pi$ is the [[Cantor pairing function|0NP5N5PYW5]].
By induction, a finite product $A_1 \times \dots \times A_n$ of countable sets is countable.
An infinite product need not be countable: the set of sequences of $0$ and $1$ is [[uncountable|0X55M9XET4]].

## Explanations

### L1 human

The pairs of natural numbers fill an infinite grid, and the grid can be listed diagonal by diagonal.
So a product of two lists is again a list.