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} $ .