6.1.5. Cantor’s Diagonalization Argument

In this lecture we will see several other examples of uncountable sets and we will discuss about Cantor’s diagonalization argument and Cantor’s theorem.

In this lecture, the focus is on introducing the concept of uncountable sets, which are sets that are larger than countably infinite sets. It begins by acknowledging previous discussions on countably infinite sets like integers and rational numbers, which share the same cardinality as the set of positive integers. The lecturer states the goal of exploring examples of uncountable sets, starting with Cantor's diagonalization argument that shows such sets cannot be enumerated like countable sets.

Think of countably infinite sets like a line of people queuing up, where you can assign each person a number. In contrast, uncountable sets are like a vast ocean where you can never list all the individual waves or drops; no number of labels can cover every single one.

We begin with our first set namely set of all binary strings but of infinite length. And this set is denoted by this notation {0, 1}∞.

This chunk introduces infinite binary strings as the first set to consider regarding uncountability. The set consists of strings made up of 0s and 1s that continue indefinitely without a terminus. Examples of such strings can include sequences of alternating 0s and 1s or strings defined by specific mathematical properties (like containing 1s at prime-numbered positions). The focus here is to highlight that while there are infinitely many binary strings, their lengths are infinite, which differentiates them from other finite sets.

Imagine a machine that produces digital signals for as long as it's powered on. Each signal is like an infinitely long binary string, where you can have endless variations (like 0000... forever, 010101... forever), much like how songs can have endless variations, but each is played eternally.

It turns out that indeed these two sets are completely different. The difference is in the terms of the length of the strings in the individual sets.

This segment explains the crucial distinction between two types of sets: the set of all binary strings of finite length ({0, 1}*) and the set of all binary strings of infinite length ({0, 1}∞). The key difference lies in the length: while both sets have an infinite number of strings, every string in the finite set has a determined end, allowing for enumeration, while strings in the infinite set do not, making enumeration impossible.

Think of collecting books. If you have a library with an infinite number of finite books, you can catalogue them all. But if you have a single infinite book that goes on forever, you cannot catalogue it because there is no endpoint to stop at!

We are supposed to prove that this set is an uncountable set. But we believe the contrary, we assume the contrary... shown is one string which will be missed in the sequencing which will show that the sequencing which we are assuming to exist does not exist actually.

Cantor's diagonalization argument begins with the assumption that we can list all infinite binary strings. Each string is indexed, and a new string is constructed by selecting bits from the diagonal of this list and flipping them (0s become 1s, and 1s become 0s). This newly created string cannot be found in the original list—hence, we reach a contradiction of the initial assumption that we listed all strings, demonstrating that the set of infinite binary strings is uncountable.

Imagine a row of lockers, each containing a different infinite string of numbers. Cantor's technique is like creating a new locker string that is guaranteed to differ from every existing locker due to its unique combination—therefore proving you can't list all possible locker numbers!

That shows that the sequencing that we are assuming is not the complete sequencing of the set {0, 1} or the complete sequencing of the elements of the set, {0, 1} is an uncountable set.

The conclusion reinforces that since any assumed enumeration of infinite binary strings will always miss at least one string (the one obtained via the diagonalization argument), we cannot enumerate all elements of {0, 1}∞. Thus, it confirms that this set is indeed uncountable, highlighting the limitations of our assumptions about cardinality in mathematics.

It's like trying to count all the stars in the sky using the best telescope you have; no matter how much you observe, you'll always find new stars that you missed—symbolizing the uncountable nature of certain sets!

There are few subtleties involved here when running the Cantor’s diagonalization argument. It might look to you that why I cannot...which is not countable.

This section addresses the limitations of Cantor's diagonalization argument by discussing why it fails for finite binary strings ({0, 1}*) and other constructs like the set of integers and rationals. The primary reason is that these constructions entail finite representations that can ultimately be completely enumerated and accounted for, preventing the argument from holding true.

Imagine trying to draw a circle with a compass. You can always draw a larger circle, but you can't keep adding more points forever without running into the boundary defined by the original. This illustrates how finite structures can always be completely defined and enumerated, unlike the 'infinite' circles where there are always more points to discover.

--