Great Ideas in Theoretical Computer Science: Countability and Diagonalization

This lecture introduces cardinality, bijections, surjections, countably infinite sets, and diagonalization. It concludes by showing that computable real numbers are countable while the real numbers are uncountable, so uncomputable reals exist.

Syllabus

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