Yellow Pig Day
Happy Yellow Pig Day. (It's Tuesday.)
In honor of Yellow Pig Day, here is a proof Nathaniel Smith sent me yesterday:
The proof that c (the cardinality of the reals) is equal to the cardinality of the power set of the naturals (or integers, or whatever) is actually pretty fun. Knowing you, I'd have guessed you'd heard it already, but your diary leaves some doubt, so I feel compelled to describe it. Also, it's so pretty that I can never resist telling people about it at the slightest excuse. Of course, being a cardinality argument, it's mind-bendingly simple and hence takes less space than this whole disclaimer...The basic idea is to use the binary representation of reals (say between 0 and 1), padding finite expansions with an infinite number of zeros, and take these as bit-strings. (So 0.4 decimal is "010000...".) These, then have a simple bijection to subsets of the natural numbers -- if the nth digit is a 1, put n in the corresponding subset. (So 0.4 decimal maps to {2}). These is obviously bijective, so, there you go.
Of course, I cheated -- the mapping to bitstrings isn't quite bijective. It's ye olde 9's problem -- just like 1 = 0.9999..., the binary representation of a real number is not necessarily unique. This is possible to get around (there are only countable numbers with this problem (those with terminating binary representations), so it's easy but irritating to fiddle room for them), but boring -- the fun part is the bitstring to subset trick.
The continuum hypothesis tattoo that I saw at DEF CON did contain an error. Alas!
