Great Ideas in Theoretical Computer Science: Countability and Diagonalization

Explore fundamental concepts in theoretical computer science through this lecture on countability and diagonalization from CMU's 15-251 course. Delve into topics such as cardinality, bijections, countable infinity, and the diagonal argument. Learn about set size taxonomy and infinite sets as Professor Ryan O'Donnell guides you through key ideas in this field. Gain insights into the work of mathematicians like Galileo and Dedekind while tackling challenging concepts like surjections and the order of complex numbers. Enhance your understanding of theoretical computer science principles through this comprehensive 74-minute lecture, complete with quizzes and in-depth explanations.