*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].