What Cannot Be Represented by Bits? (Uncountable Sets)
Schedule Reminders: Problem Set 1 is due this Friday (4:19pm). See the schedule for updated office hours.
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.
Barrow’s The Infinite Book has chapter on the sad life of Georg Cantor: The Madness of Georg Cantor.
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].