6.1.4. Difference between Finite and Infinite Length Binary Strings

So now what we are going to discuss is a very beautiful result, very fundamental result attributed to Cantor is called a Cantor’s Diagonalization argument and using this diagonalization argument is we are going to prove is that the set of all binary strings of infinite length is an uncountable set.

This chunk introduces Cantor's Diagonalization argument, explaining that it is a key method used to show that certain sets have different sizes or cardinalities. Specifically, it will be used to demonstrate that the set of all binary strings of infinite length cannot be counted or listed, meaning it is uncountable. Cantor's argument highlights a fundamental difference in size between sets that can be put into one-to-one correspondence with natural numbers (countable) and those that cannot (uncountable).

Imagine counting the number of people in a room. If every person can be assigned a unique number, like 1, 2, 3, etc., then that group is countable. However, think about all the possible songs that could be created using an infinite number of notes played in various sequences—a whole world of potential songs that cannot be easily counted or listed like people can. This is akin to the difference between finite and infinite binary strings.

If I consider the string x equal to 0 0 0 0 and the sequence of 0’s which never ends then that is a binary string whose length is infinite.

This chunk explains what an infinite length binary string is by providing an example. A binary string is composed of zeros and ones, and when it goes on indefinitely, such as '000...' without any termination, it is categorized as having infinite length. When a string is infinite, it implies that there is no last character; the characters continue endlessly. This characteristic fundamentally differentiates it from finite strings, which have a defined length and identifiable start and end.

Think of a movie that never ends, where the scenes just keep playing on a loop. Unlike a typical movie that has a beginning and definite conclusion, an infinite binary string goes on forever just like how there are endless stories or songs waiting to be told.

However the length of each string in that set will be finite. So the difference, the primary difference between the 2 sets is the following.

In contrast to infinite binary strings, finite binary strings have a clearly defined length. This means we can determine where the string begins and ends. The discussion here emphasizes that while both finite and infinite binary strings are infinite in number, their intrinsic properties regarding length are fundamentally different. Finite strings may be very long, but they still have a limit, which infinite strings do not.

Consider a video game level that has a specific end. You can conquer that level, reach the end, and see a completion screen. This represents finite strings. In stark contrast, think of an open-world game where you can keep exploring forever without reaching a boundary. That’s more like an infinite string—there’s always a new area to explore without ever finishing.

If I consider the set {0, 1} then the property of the set is that the length of any string in this set cannot be bounded by a natural number.

This statement addresses why infinite binary strings are uncountable. Since there is no natural number that dictates the length of the strings in the infinite set, each string can effectively represent a different point in a continuum of possibilities. That means that while we may see countably infinite representations, the actual set itself is not enumerable or countable because we cannot list all possible infinite sequences in a comprehensive manner.

Imagine a library filled with every possible book—not just the ones you could physically read, but also every book that could ever be written, even if it has never been created yet. Just like that library, infinite binary strings cannot be fully documented or listed as each time you try to write one down, another unique string waits just beyond it.

That 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 besome valid sequencing some sequencing of the element of that set.

In this conclusion, the lecture wraps up the discussion on infinite versus finite length binary strings by affirming that the infinite set of binary strings {0, 1} cannot be sequenced or counted. The conclusion reiterates the principle behind Cantor's diagonalization argument, which establishes that there is at least one string in the infinite set that cannot be found in any proposed list of strings—hence the term 'uncountable.'

Picture a leaderboard that lists champions of a video game—with every player who has ever played recorded. If a new player joins, they can’t be added to a finite list unless you remove someone. In the world of infinite binary strings, there’s always a new player joining the realm of possibilities, completely changing the game of countability.

--