My most favorite math proof ever

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.

About Simeon Simeonov

I'm an entrepreneur, hacker, angel investor and reformed VC. I am currently Founder & CTO of Swoop, a search advertising platform. Through FastIgnite I invest in and work with a few great startups to get more done with less. Learn more, follow @simeons on Twitter and connect with me on LinkedIn.
This entry was posted in Uncategorized. Bookmark the permalink.

5 Responses to My most favorite math proof ever

  1. Hristo says:

    Why do you need the code at all 😉

  2. Mike says:

    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.

      • Mike says:

        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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s