chapter  1
Cantor and Peano type functions
ByGilbert W. Bassett Jr., Roger Koenker
Pages 20

It is widely known that one of the first set-theoretical results of Cantor was his discovery of the existence of a bijection between the set R of all real numbers and the corresponding product set R 2 = R × R $\mathbf{R}^{2} = \mathbf{R} \times \mathbf{R}$ (i.e., the Euclidean plane). For a time, Cantor did not believe that such a bijection exists and even wrote to Dedekind about his doubts in this connection. Of course, Cantor already knew of the existence of a bijection between the set N of all natural numbers and the product set N 2 = N × N $\mathbf{N}^2 = \mathbf{N} \times \mathbf{N}$ . A simple way to construct such a bijection is the following. We first observe that a function f : N → N \ { 0 } $f : \mathbf{N} \rightarrow \mathbf{N} \setminus \{0\}$ , defined by the formula f ( n ) = n + 1 $f(n) = n + 1$ for all n ∈ N $n \in \mathbf{N}$ , is a bijection between N and the set of all strictly positive natural numbers. Then, for each integer n > 0 $n> 0$ , we have a unique representation of n in the form n = 2 k ( 2 l + 1 ) $n = 2^{k}(2l + 1)$ , where k and l are some natural numbers. Now, define a function g : N \ { 0 } → N × N $g : \mathbf{N} \setminus \{0\} \rightarrow \mathbf{N} \times \mathbf{N}$ by the formula g ( n ) = ( k , l ) $g(n) = (k,l)$ for all n ∈ N \ { 0 } $n \in \mathbf{N} \setminus \{0\}$ . One can immediately check that g is a bijection, which also gives the corresponding bijection between N and N × N $\mathbf{N} \times \mathbf{N}$ .