Indeed, 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 ℤ².
alt Hacker News
Indeed, 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 ℤ².