Math is beautiful and, sometimes, math becomes even more beautiful with the help of a bit of computer science. My favorite proof of all time combines the two in just such a way.
Goal: prove that the cardinality of the set of positive rational numbers is the same as that of the set of natural numbers.
This is an old problem dating back to Cantor with many proofs:
- The traditional proof uses a diagonal argument: geometric insight that lays out the numerator and the denominator of a rational number along the x and y axes of a plane. The proof is intuitive but cumbersome to formalize.
- There is a short but dense proof that uses a Cartesian product mapping and another theorem. Personally, I don’t find simplicity and beauty in referring to complex things.
- There is a generative proof using a breadth-first traversal of a Calkin-Wilf tree (a.k.a, H tree because of its shape). Now we are getting some help from computer science but not in a way that aids simplicity.
We can do much better.
Proof:
Given a rational number p/q, write it as the hexadecimal number pAq. QED
Examples:
- 0/1 → 0A1 (161 in decimal)
- ¾ → 3A4 (932 in decimal)
- 12/5 → 12A5 (4773 in decimal)
Code (because we can):
def to_natural(p, q)
"#{p}A#{q}"
end
It is trivial to extend the generation to all rationals, not just the positive ones, as long as we require p/q to be in canonical form:
def to_natural(p, q)
"#{p < 0 ? 'A' : ''}#{p.abs}A#{q}"
end
To me, this CS-y proof feels much simpler and more accessible than any of the standard math-y proofs. It is generative, reducible to a line of code and does not require knowledge of any advanced concepts beyond number systems which are not base 10, a straight, intuitive extension of base 10 positional arithmetic.
Note: we don’t need to use hexadecimal. The first time I heard this proof it was done in base 11 but I feel that using an unusual base system does not make the proof better.
Why do you need the code at all 😉
Good question. Most people don’t but, in my experience sharing this proof over the years, some people find it helpful to see the manipulation.
This doesn’t actually prove that they’re equinumerous. To do that, you need to show that there’s a bijection; you’ve only shown an injection. In fact, there’s a reason to adopt base 11: If you have any digit B to F in the hexadecimal number, there’s no obvious way to define the inverse function. Even restricting yourself to base 11, you still need to discuss how you’re dealing with numbers that end in A followed by zero or more zeroes.
Mike, thanks for being a careful reader! You are absolutely correct that I only show an injection and that’s not technically a complete proof. You are not correct that a complete proof requires a bijection. A bijection is sufficient but is not necessary.
By the injection construction, |Q| <= |N| as 1AA1 in N has no representation in Q. Also, |Q| >= |N| as any natural n is n : 1 and n : 2 has no representation in this construction. Therefore, |Q| = |N|.
The obviousness of the last step is the reason the question came up in the first place historically: the rationals “feel” more numerous than the naturals. The beauty of the base 11 injection is that it provides the simplest proof I know that the cardinality of the rationals is not greater than that of the naturals. The rest is trivial.
A bijection _is_ necessary to say that two sets are equinumerous; that how it’s defined. That’s not to say that you need to _construct_ one, just that it exists.
In your last comment, you’re implicitly invoking the Schröder-Bernstein Theorem. Which is fine, and the easiest approach. But the Schröder-Bernstein Theorem is non-trivial, which contradicts your claim of simplicity.
Pingback: My most favorite math proof ever - FrontFluence