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.

Introduction
Quiz
Galileo
Characters
The Last Word
The Great Other Neutral Guy
Definition of Cardinality
Definition of bijection
Objection
Transitivity
Order of Complex Numbers
Countably Infinite
Countable
Notation
Surjections
Countability
Infinite Sets
Dedekind
Infinite Binary Strings
Diagonal Argument
Set Size Taxonomy