Exercise 823Logic, sets and proofs › Countability and cardinalityL1Added 3 Nov 2026

Countable product

#product#countable#product rule

Statement

Show that if $A$ and $B$ are countable, then $A\times B$ is countable.

Hint

If $f:A\to\mathbb{N}$ and $g:B\to\mathbb{N}$ are injections, then $(a,b)\mapsto\pi(f(a),g(b))$ is injective.

Show solutionHide solution

Injection. Using the pairing function $\pi:\mathbb{N}^2\to\mathbb{N}$ , $(a,b)\mapsto\pi(f(a),g(b))$ is injective.

Conclusion. $A\times B$ is countable.

Remark. Finite products of countable sets are countable; infinite countable products need not be.