Mapping between infinite sets
Task number: 3377
Find a mapping with the following properties.
Variant
A bijection between \(\mathbb N\) and \(\mathbb Z\).
Hint
Try to map the elements of \(\mathbb N\) in an alternating way.
Solution
One possible solution is the mapping given by \(f(2k+1)=k\) for \(k\in\{0{,}1, \dots \}\) and \(f(2k)=-k\) for \(k\in\{1{,}2, \dots \}\).
The mapping \(f\) is injective (the first part yields non-negative values and the second negative), and each part is an injective linear function.
The mapping is surjective because a non-negative \(k\) is the pre-image of \(2k+1\), while a negative \(k\) is the pre-image of \(-2k\).Variant
A bijection between \(\mathbb N\) and \(\mathbb N^2\).
Hint
In other words, your task is to traverse all elements of \(\mathbb N^2\) (omitting none, visiting each element exactly once).
Solution
One possibility is to arrange the points of an infinite grid \(\mathbb N^2\) into a sequence, and the bijection is determined by the order of the element in this sequence. One possible sequence is shown in the figure.
This arrangement can be described by the mapping \(f:\mathbb N^2 \to \mathbb N\) given by \(f((u,v))=v+\sum\limits_{i=1}^{u+v-1} i\). The mapping \(f\) is injective and surjective, and is therefore a bijection. Its inverse \(f^{-1}\) is a bijection from \(\mathbb N\) to \(\mathbb N^2\).
Solution
Another approach is based on the observation that any positive integer \(n\) can be written uniquely as the product of an odd number and a power of two (including the case of \(2^0\)), or \(n=2^{u-1}(2v-1)\), where \(u\) and \(v\) are positve integers. Then the mapping given by \(g(n)=(u,v)\) is a bijection between \(\mathbb N\) and \(\mathbb N^2\).
Variant
An injection from \(\mathbb Q^+\) to \(\mathbb N\). (Or even construct a bijection.)
Hint
Try to use the preceding variant somehow.
Solution
Each positive rational number is represented by a fraction \(\frac{p}q\), where \(p\) and \(q\) are coprime integers. This fraction corresponds to the pair \((p,q)\).
Let us denote by \(h\) the mapping that assigns to the positive rational number \(\frac{p}q\) the pair \((p,q)\). This is an injective mapping from \(\mathbb Q^+\) to \(\mathbb N^2\), since different rational numbers correspond to different fractions. The mapping \(h\) is not surjective, because the non-coprime pairs are not in the range of \(h\).
If we compose the mapping \(h\) with the mapping \(f\) from the previous variant, then we get an injective mapping \(\mathbb Q^+ \to \mathbb N\).
A bijection can be obtained by omitting all pairs with a common divisor when constructing the ordering as shown in the figure above (the line of such a point to the origin contains another lattice point). This representation, however, has no simple description. Another method is to use chain fractions or a non-constructive proof using the Cantor-Bernstein theorem.
