What Can Be Represented by Bits?
Schedule Reminders: Problem Set 0 is due this Friday (4:19pm). See the schedule for updated office hours.
Update (7 Sept): There is a correction on slide 10 to the way we defined addition for the Set-based Natural Numbers (thanks to Nijat Khanbabayev for pointing out the problem).
Some of the material from today’s class (and what we will continue on Monday) is in the TCS Book, Chapter 2. Peter Kahn’s The Natural Numbers provides a more complete description of how to build the natural numbers from sets (and how this leads to the induction principle).
If you want more practice with induction proofs, or to refresh on what it means to have a surjection or bijection between two sets, see Mathematics for Computer Science by Eric Lehman, Tom Leighton, and Albert Meyer (this is what I’ve been calling the “MCS” book).
The comic book about Cantor and uncountable infinities is: Logicomix: An epic search for truth by Apostolos Doxiadis and Christos Papadimitriou. I don’t know any other comic books about the induction principle, but can (shamelessly) recommend this comic book on countable infinities.