Theorem·T54
The product of two countable sets is countable
Pair up witnessing injections into the naturals with the pairing function itself.
For countable sets
and
:
In words
For a countable set X and a countable set Y: their cartesian product is countable.
Never needed: F05 · F10 · F13 · A03 · A04 · A05 · A07 · A09 (computed from the citation graph, not asserted).
Proof
- 1Since and are countable, there are injections and .
- 2Define by , where is the pairing function. Suppose : then , so by injectivity of pi, and ; since are injective, and , so (L01).
- 3is an injection, so , i.e. is countable.
∎
Remarks
The same combining trick as T53, one level simpler (no need to choose among several witnessing injections, since there are only the two,
and
, both already in hand). Feeds into countability of n-tuples.