alt Hacker NewsIndeed, it's always presented that way.¹ It's very unsatisfying because it doesn't establish a 1:1 correspondence; it depends on the idea that if set A has the same cardinality as a superset of set B, then set B's cardinality cannot exceed set A's. Add the assumption that the natural numbers have the lowest possible infinite cardinality and the proof is technically complete.
I've read about an actual bijection between naturals and rationals, but I don't remember how it was done.
¹ Possibly in the more general form of showing the bijection between ℕ and ℤ².
Replies
For bijection, the path through the rationals can just jump over and skip any numbers that have already been visited by the path.
For the construction of a bijection between natural numbers and another set, when you already know that the sets have the same number of elements, it is enough to define an order relation on the other set.
There are many ways to define an order on the rational numbers, which would establish a bijection to 0, 1, 2 ...
For instance, after reducing the numerator and denominator, so that you have unique rational numbers, you could define that they are ordered based on the sum of the number of digits of the numerator and of the denominator. This ensures that for each N that is the sum of digits, there are only a finite number of rational numbers. Inside this finite set, you can choose various rules, e.g. that positive numbers precede negative numbers, that a number with fewer digits in the denominator precedes another, etc. Then among the numbers with e.g. K digits in the numerator and L digits in the denominator, you could choose a lexicographic ordering, when the numerator is written before the denominator.
It does not matter which ordering rules you choose, the point is that you can always find such an order, which will arrange all rational numbers in a sequence, which describes thus a bijection with the natural numbers.
For algebraic numbers, you can establish such an order for the polynomials whose solutions they are, again finding a bijection. The easy solution is the same, to first establish an order between subsets of numbers that contain only a finite number of elements, and then define an order inside the subsets (e.g. with unique polynomials, where the coefficients do not have common factors, you can order them based on the sum of the number of digits of all coefficients).
The same technique works with any power of the set of rational numbers, or of the set of algebraic numbers.
For computable numbers, which are determined by programs written with an alphabet having a finite number of characters, you can define an order for the programs, e.g. first based on the length of the program, and then, among the finite number of programs having the same length, with lexicographic order.
With real numbers such methods do not work, because any attempt to arrange the real numbers into a sequence of subsets results in subsets that do not have a finite number of elements, like above, but which have an infinite number of elements.
The cantor pairing function is a bijection though between (N, N) -> N so it does establish a bijection in cardinality between positive rationals and N.
The approach you mentioned would be if you used a non-bijective function to map from (N, N) to N like 2^a 3^b which can show that the cardinality of positive rationals is a subset of the cardinality of the naturals, and then you get your version of the proof.
Edit: Wait unless the objection was that actually the bijection from (N, N) -> N is not sufficient since e.g. (1,1) and (2,2) all map to the same rational. You could probably skip duplicates when enumerating, but if you insist on a explicit constructive version I have no idea how you'd find the inversion formula for that.