Products of countable sets
is countable: pairs listed along diagonals give a surjection , and gives an injection. Hence and are countable.
Theorem 6.6
is countable.
Diagonal listing
List the pairs along the diagonals of the grid:
Formally, let and, writing ,
which produces a well-defined sequence listing every pair. Then is a surjection .
Prime factorisation injection
By the characterisations of countability it suffices to construct an injection . Set
If , the fundamental theorem of arithmetic forces and . Thus is an injection.
Integer lattices
Since is countable there is an injection , and then
is an injection , where is as above. Hence is countable. By induction, is countable for every .
Related
Stated in
- Theorem 6.6§6 Countability