6.1.3. Examples of Infinite Sets

In the last lecture, we saw examples of several countably infinite sets. The nice thing about those sets is that their cardinality is the same as the set of positive integers. Examples include the set of integers, the 2-dimensional plane, integer plane, set of rational numbers, set of prime numbers, set of all binary strings of finite length, and for any finite alphabet, the set of all possible strings of finite length over the alphabet.

In this chunk, we remind ourselves of countably infinite sets from the previous lecture. Countably infinite sets are those sets that can be put into a one-to-one correspondence with the positive integers. This means that we can list their elements like 1, 2, 3, and so on. The examples given highlight how many mathematical structures can exhibit this property, essentially telling us that there's a vast yet countable variety of infinite sets. This foundation helps us transition into understanding uncountable sets, the topic at hand.

Imagine a library where every book can be assigned a unique number (like 1, 2, 3…) in an infinite sequence. This means even if the library holds infinitely many books, you could theoretically list them all by their numbers, just as with countably infinite sets.

The interesting aspect here is that not every infinite set is countable. The focus of this lecture is to discuss the existence of infinite sets whose cardinality is different from that of the set of positive integers.

This chunk introduces us to the idea that while some infinite sets can be counted, like those from the previous chunk, others cannot. The cardinality of a set refers to the size of the set in terms of the number of elements it contains. In this lecture, we shift focus to finding infinite sets, such as real numbers, which cannot be matched one-to-one with the positive integers, thus showing they possess a different kind of infinity, making them uncountable.

Think of it like trying to list every possible decimal number between 0 and 1. No matter how hard you try to list them, you will miss some numbers, emphasizing that there are infinitely more decimals than there are whole numbers.

The first example of an infinite set we discuss is the set of all binary strings of infinite length, denoted as {0, 1}^∞. Examples include sequences of all 0s, alternating 0s and 1s, or sequences where bits equal 1 at prime indices.

In this part, we focus on binary strings that do not have a finite end but continue indefinitely. Each of these strings is formed using just 0s and 1s and can grow without bound as they go on forever. This highlights the diverse ways we can construct infinite sets, especially in a binary format, setting up the groundwork to discuss their properties further.

Imagine writing code to generate a sequence of light switches that can either be on (1) or off (0) infinitely. Each combination of on and off switches represents a different binary string, representing the multitude of endless possibilities.

The primary distinction to note is that while the set of binary strings of infinite length {0, 1}^∞ is unbounded, the set of finite length strings {0, 1}* consists of strings that are finite in their extent, meaning they have an endpoint.

This chunk clarifies a crucial distinction between infinite and finite binary strings. Here, we see that while both sets contain infinitely many elements, the finite set has a defined limit to the length of strings, whereas the infinite set has no such limit. Understanding this difference sets the stage for the main argument regarding countability.

Think about a bag of marbles where you can only take a limited number out at once (finite strings), versus an infinitely long conveyor belt of marbles that never stops (infinite strings). In the first case, you can see the end, while the second goes on forever.

We will use Cantor’s diagonalization argument to prove that the set of all binary strings of infinite length is uncountable. The proof is by contradiction, assuming that the set is countable and demonstrating that we can find at least one infinite binary string not on the list.

Here, we introduce Cantor's diagonalization, a famous method used in mathematics to demonstrate the existence of uncountable sets. By assuming that we can enumerate all infinite binary strings, we construct a new string that will always differ from any string on the list at some point. This contradiction shows that our initial assumption (that we can list all such strings) is incorrect.

It's akin to a situation where you could be asked to list every person's name in a queue, only to find that there's someone in line who is not named and cannot be matched with any name in your list. Just like an infinite number of new arrivals into line that simply cannot be captured in your counting method.

Our demonstration shows that the set {0, 1}^∞ is uncountable since there's always at least one binary string that cannot be accounted for in any enumeration of infinite binary strings. Therefore, we confirm that not all infinite sets can be matched with the positive integers.

This concluding chunk reaffirms the results obtained using Cantor's diagonalization argument. It reiterates that through our construction, we proved that there are more infinite binary strings than there are integers, confirming that the set of all binary strings of infinite length is indeed uncountable.

Consider a recipe book that promises to include all possible recipes using endless ingredients. Even if you compile a massive list, the endless combinations always allow for even more recipes that haven’t been written down yet, mirroring the infinite possibilities present in uncountable sets.

--