Discrete Mathematical Structures, Lecture 4.5: Cardinality and infinite sets

Discrete Mathematical Structures, Lecture 4.5: Cardinality and infinite sets.

Two sets A and B have the same cardinality (size) if there is a bijection from one to the other. We begin with few thought experiments that showcase some very strange properties about infinity, including the famous "Hilbert's Hotel". Next prove that the rational numbers have the same cardinality of the integers -- these are said to be "countable", and they are strictly smaller than the set of real numbers. After that, we show that the cardinality of any set is always smaller than its power set, which means there are infinitely many infinities. We conclude with a potpourri of "fun facts", such as how to cover the rational numbers of intervals of total length 1, and a bit of history of the continuum hypothesis, which asks whether there is a set S of size larger than the integers but smaller than the reals. Georg Cantor went crazy trying to prove this in the late 1880s, and in the mid-20th century, Kurt Gödel and Paul Cohen established that it was indeed undecidable -- it lies completely outside of our standard set of axioms.