What Cannot Be Represented by Bits? (Uncountable Sets)
Here is Cantor’s original proof (in German, but the math is universal, so somewhat understandable even without knowing German):
Georg Cantor, Ueber eine elementare Frage der Mannigfaltigkeitslehre. Published in Jahresbericht der Deutschen Mathematiker-Vereinigung, Volume 1, 1891. (About this Scan)
Its only a bit over 2 pages long, and its easy to see Cantor’s answer to the ``Is 0 a Natural Number?” question without understanding any German. Google translates the title as On an elementary question of the theory of manifolds.
We went through the proof that the binary strings are uncountable pretty quickly, and this is definitely a mind-blowing result. If you are not bothered by this result, its probably because you aren’t thinking about things deeply enough. Some other recommended presentations of these topics include:
Vi Hart video’s on Proof some infinities are bigger than other infinities and How many kinds of infinity are there? (sample youtube comment: watching this makes me feel like i’ve just taken the red pill and the blue pill, crushed them into a single, purple powder and snorted it).
Numberphile’s, Infinity is bigger than you think.
You can also see how Prof. Mahmoody and I covered this in cs2102 over these three classes (which overlaps a fair bit with what we’ve done in cs3102, but with more detail and examples): Class 17: Infinite Sets [Video], Class 18: Spooky Infinities [Video], Class 19: Reviewing Infinities [Video].