In an introductory analysis course, one learns that the natural numbers are in 1-1 correspondence with the rational numbers: \(|\mathbb{N}|=|\mathbb{Q}|\). This is usually shown via a snake argument
Here is an alternative proof, given the intuitive Schroder-Bernstein Theorem:
Theorem: Given sets \(A\) and \(B\), if there exists injections \(A \to B\) and \(B \to A\), then \(A\) and \(B\) have the same cardinality.
There is a natural injection \(\mathbb{N}\to \mathbb{Q}\), but what about the other direction? Let’s choose any two coprime numbers, say 2 and 3, then consider the map \(f: \mathbb{Q}\to \mathbb{N}\) given by
\[f\left(\frac{p}{q}\right) = 2^p3^q\]
This is an injection so long as both \(p\) and \(q\) are positive. But as stated, this is only defined on the nonnegative rationals? What about the negative rationals (ie., when \(p<0\))? We could pick two other coprime integers, like 5 and 7 and then set
\[f\left(\frac{p}{q}\right) = 5^{-p}7^q\]
This gives an honest injection from the rationals to the naturals and we conclude that \(|\mathbb{N}| = |\mathbb{Q}|\).
Leave a Reply