6.1.2. Countably Infinite Sets

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. 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.

This introduction establishes the context of the lecture, indicating that the focus will shift from countably finite sets, which can be counted or listed, to countably infinite sets, which also can be matched with the set of natural numbers (positive integers). The lecturer will also introduce uncountable sets, demonstrating that not all infinite sets can be counted in this way.

Think of countably infinite sets like a library with an infinite number of books, where every book has a unique identification number. You can list them one by one. In contrast, uncountable sets are like an infinite ocean—there are so many waves that you can't even begin to label them all.

So we saw several such sets; it may be the set of integers, the 2 dimensional plane, integer plane, set of rational numbers, set of prime numbers, and set of all binary strings of finite length.

In this chunk, the lecturer provides concrete examples of countably infinite sets. Each of these sets can be listed in a manner similar to counting: integers can be counted as 1, 2, 3, ...; rational numbers can be represented in a systematic way, etc. This illustrates that although these sets are infinite, they can still be ‘counted’ in a certain sense.

Imagine you are invited to count the number of students in a never-ending school. Even though there are lots and lots of students, each one has a unique name and can be identified sequentially, just like we can list or count integers.

But the interesting part here is that is not the case and the focus of this lecture is to argue about the existence of infinite sets whose cardinality is different from that of set of positive integers.

This slide acknowledges a critical turning point in the understanding of infinity. While some infinite sets can be counted, there are others that are so vast that they cannot be put into a one-to-one correspondence with the positive integers. The lecturer aims to explore this distinction further, which leads to the concept of uncountable sets.

If you imagine a series of steps leading to an infinite staircase, countably infinite steps allow you to count each one. However, uncountable steps are like having an infinity of staircases running parallel without any way to match them one-to-one, making it impossible to enumerate them all.

So 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} .

Here, the lecturer introduces the specific example of binary strings of infinite length, such as '000...' or '010101...'. This set is defined using the notation {0, 1}, indicating that each binary string is composed of the digits 0 and 1 and continues infinitely without terminating.

Imagine trying to write down every possible combination of light switches that can be flipped on (1) or off (0) over an infinite time frame. Each unique configuration is a binary string. Even though you can create endless arrangements, you can't finish listing them!

Even if I consider the set {0, 1}* , the number of strings in that set is infinite. However, the length of each string in that set will be finite.

This chunk compares two types of binary sets: those with strings of finite length ({0, 1}*) and those with infinite length ({0, 1}). While both sets are infinite, the former contains strings that end after a certain number of characters, while the latter does not have an endpoint, making them fundamentally different.

Think of {0, 1}* as a stack of books, where each book contains a finite number of pages (information) and ends. In contrast, {0, 1} is like a never-ending scroll that continually reveals new pages without ever concluding.

Now what we are going to discuss is a very beautiful result...we are going to prove is that the set of all binary strings of infinite length is an uncountable set.

Cantor’s Diagonalization Argument is a proof technique used to demonstrate that the set of all binary strings of infinite length ({0, 1}) cannot be enumerated. The main idea is to assume that such an enumeration exists and then construct a new binary string by modifying the diagonal elements of the enumeration, leading to a contradiction.

Imagine a party where everyone is seated in a row, and every person has an infinite list of preferences. If you try to create a master list of everyone’s favorite color by picking one color from each preference, there will always be at least one person whose favorite we have missed because we choose based on their list. Thus, you can’t fully represent everyone’s preferences.

This shows that your set {0, 1} is an uncountable set because as per the definition countably infinite set if the set is countably infinite there must be some valid sequencing...

In conclusion, the argument proves that the size (cardinality) of the set of infinite binary strings is larger than that of the countably infinite set of integers. There is no way to list all possibilities of infinite binary strings, hence establishing that such sets are uncountable.

Returning to our library analogy, you can think of this as discovering a new collection of magical books that contain stories so vast and intricate that no librarian can ever catalog them all; thus, they’re considered uncountable.

--