6.1. Lecture No # 29: Cantor’s Diagonalization Argument

In the last lecture, we saw various examples of countably finite sets. So we will continue the discussion on countably infinite sets and the plan for this lecture is as follows. We will see several other examples of uncountable sets and we will discuss Cantor’s diagonalization argument and Cantor’s theorem.

In this introduction, the lecturer explains that the previous lecture covered countably finite sets, which are sets whose elements can be matched one-to-one with the positive integers. The current lecture will extend the discussion to countably infinite sets, and it will introduce the concept of uncountable sets, primarily focusing on Cantor's diagonalization argument.

Think of countably infinite sets like guests at a hotel where every room is numbered. If each guest can be assigned a room number, they represent a countable set. However, Cantor's diagonalization will introduce a scenario where certain guests cannot fit into any room, illustrating the concept of uncountability.

We begin with our first set, namely the set of all binary strings but of infinite length, denoted by {0, 1}∞. Examples include the infinite string of 0's or a sequence with alternating 0's and 1's, demonstrating various patterns.

Here, the lecturer introduces infinite binary strings, which are sequences that do not end. Examples such as a string composed solely of 0's or alternating 0's and 1's illustrate how these strings can take various forms. The key is that their lengths are infinite, meaning they cannot be numbered or counted in the traditional finite sense.

Visualize writing a story but never finishing it. You keep adding more sentences, creating endless possibilities. In this analogy, each sentence represents a binary digit, with infinite stories forming an infinite binary string.

The difference between the set of finite length binary strings {0, 1}* and the infinite length binary strings {0, 1}∞ becomes clear. The first has strings of finite length, while the latter cannot be bounded by any natural number.

This chunk highlights the critical distinction between binary strings of finite length and those of infinite length. While a finite string has a definite end, an infinite string continues indefinitely with no endpoint. This distinction sets the stage for understanding Cantor's argument regarding countability.

Imagine a finished book versus an endless story. The finished book has a clear last page (finite string), while the endless story continues on forever (infinite string), reflecting the concept of uncountability.

Cantor’s diagonalization argument aims to prove that the set of all binary strings of infinite length is uncountable. We will use a proof by contradiction to reveal that there's always a new binary string excluded from any supposed list.

In this segment, Cantor's diagonalization argument is introduced as a method for demonstrating that infinite binary strings constitute an uncountable set. By assuming we can list all binary strings, Cantor shows how we can create a new string that differs from every listed string, proving that our original assumption of a complete list was incorrect.

Consider someone claiming to have collected every song ever composed. Cantor's argument is like playing a new song that no one has heard before, proving that there are always more songs to discover than in the claimed complete collection.

Assume a sequence of all infinite binary strings: r1, r2, r3, ... . By focusing on the diagonal bits, we can construct a new binary string r' that is different from each string in the list.

The lecturer explains how to construct a new binary string by taking the diagonal elements of the assumed list of infinite binary strings. By flipping each bit along the diagonal, a new string is created that cannot be found in the original list, since it differs from every string at least in one position.

Imagine you're playing a game where you try to predict someone else's choices. No matter how many choices they make, you can always choose something different by altering your answer slightly, just like Cantor alters the diagonal bits to create a new string.

Since the newly created string r' is not in the original list, this shows that the set of infinite binary strings cannot be counted, proving it is uncountable.

This final part of Cantor's argument wraps up the proof by emphasizing that the existence of the new binary string r' demonstrates the incompleteness of the assumed list. This logically concludes that the set of all infinite binary strings must be uncountable, as no complete enumeration can exist.

Think of this situation as having a potluck dinner where every dish is listed, but someone brings a surprise dish that wasn't accounted for. The irrefutable presence of this unexpected dish represents the uncountable nature of the infinite binary strings, proving that some things just cannot be fully enumerated.

--