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.

2 Responses to My most favorite math proof ever

  1. Hristo says:

    Why do you need the code at all ;-)

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s