Class 4: Uncountability

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.

Slides (PDF)
Video

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: