6.1.6. Proof by Contradiction

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} . So; some examples of binary strings of infinite length 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.

We start by defining what we mean by binary strings of infinite length. This means that there can be strings composed of the digits 0 and 1 that never end. An example of such a binary string is a sequence of 0's that goes on forever. We denote the set of all these infinite binary strings as {0, 1}∞. Understanding this concept is crucial for the next steps.

Imagine writing a never-ending story where you could only use two words: 'yes' and 'no'. If you keep adding to this story without ever stopping, you create an infinite binary string. Just like in our analogy, the story can never truly be finished; there are always more words (0's or 1's) to add.

So we are supposed to prove that this set is an uncountable set. But we believe the contrary, we assume the contrary and we assume that the set is countable and if it is countable then it must be having a sequencing of elements of the set.

Here, we assume for the sake of argument that the set of all infinite binary strings can be arranged into a sequence. If this set were countable, we would be able to list all elements like r1, r2, r3, etc. This assumption sets the stage to reach a contradiction.

Think of a library where you suppose every book in the library can be arranged neatly on shelves. You are convinced all books can fit in, but then you discover a new valuable book that hasn't been placed on any shelf, creating a contradiction to your initial claim.

I will show that there exist at least 1 string which is of infinite length and which is binary and which is not in the sequence of binary strings that we are assuming exists. So what, exactly that string? So you consider the binary string r which is obtained by focusing on the bits along the diagonal here.

Using Cantor's diagonal argument, we identify a new binary string by examining the diagonal bits from the assumed sequence. For instance, if the first string starts with a 0, we can take another digit that is the opposite (1), and we repeat this for each subsequent string, creating a new binary string that is guaranteed to differ from each string in the original list in at least one position.

Imagine a class of students where you write down each student's name and their favorite number from 1 to 10. If a student named Alex says their favorite number is the second student's favorite plus one, this ensures Alex's favorite differs from one listed before, just like our diagonal construction ensures our new string isn't found in the earlier sequence.

Now my claim is that the string r which I have constructed here which I am considering here will be different from all the string r , r , r , r and so on in the sequencing which I am assuming to exist.

Now, we show that the constructed string r, which we derived from the diagonal method, is not in the original sequence of binary strings. This implies that there is at least one infinite binary string that is missing from our sequenced list. Since we found a string that cannot belong to the assumed list, this contradicts our original assumption that the set is countable.

Imagine concluding a race where you have declared all runners' positions, but then a new runner arrives who matches none. The appearance of this new runner breaks your initial declaration of being able to list all participants, illustrating how our initial assumption about countability fails.

--