5.1.3. Enumeration of subsets Π(i)

Now what we now going to prove is that the set of all strings over a finite alphabet is also countable. So what do I mean by that is just few slides back I took a binary alphabet which has only 2 symbols 0 and 1. And I proved that the set Π* which is the set of all possible strings of finite length which are binary is countable. Now I am generalizing this result to a bigger alphabet which may have more than 2 symbols or 2 characters.

The objective is to prove that any set of strings formed from a finite alphabet is countable. In previous sections, we established this for a binary alphabet (two symbols: 0 and 1). The author is now expanding this concept to an alphabet that could consist of more than two symbols. Thus, we can apply countability to larger alphabets as well.

Think of a vending machine with buttons representing different snacks. If it has two buttons, it's simple to count the combinations of snacks you can get. Now, imagine it has more buttons. While it becomes more complex, you can still count how many different snack combinations you can select.

So I am assuming that I have an alphabet Π consisting of m number of characters s to s or m 1 m number of symbols. And Π* denote the set of all possible strings finite length strings over this alphabet. So my claim is that is that Π* is countable.

Here, the author defines its alphabet (Π) as containing 'm' characters. The set Π* is then introduced as comprising all possible strings of finite lengths that can be composed from this alphabet. The claim emphasizes that, similar to the binary case, this larger set of strings can still be counted.

Imagine you have a collection of colored beads (the characters in the alphabet). Even if you have many colors, you can combine them to make necklaces of various lengths. Even with endless combinations, you can list them systematically.

So again what is Π*, the way we have defined Π* for the case of the binary alphabet we are going to follow the definition: Π* will be the union of the various subsets Π(i). Where Π(i) denote the subset of all strings of length exactly i over the alphabet Π.

The author clarifies the composition of the set Π* as the union of subsets denoted by Π(i). Each subset Π(i) includes strings that have a fixed length 'i'. For example, if the alphabet contains three letters (a, b, c), then Π(0) represents the empty string, Π(1) includes strings of length 1 (a, b, c), and so forth.

Consider typing on a keyboard—even though every key allows for infinite letters, you can categorize your typing based on character count. For instance, a list of all potential one-letter words, then two-letter combinations, etc.

So it is easy to see that each subset Π(i) is finite because each subset will have mi number strings. And the set Π* is the union of all such subsets. So it will have infinite number of elements.

Each subset Π(i) contains a specific number of strings, calculated as m raised to the power of i (mi). Since each of these subsets is finite, but there are infinite subsets (as 'i' can increase indefinitely), the overall set Π* contains an infinite number of strings.

Think of building blocks. Each level of blocks (representing subset Π(i)) has a finite number of arrangements or structures based on the number of blocks you can use. However, you can keep building higher levels indefinitely, leading to an infinite tower of structures.

But now we want to show a valid sequencing of the elements in the set Π*. So here is how we can list down all the elements of the set Π* without missing any of them.

The crux of the proof lies in arranging all unique strings in Π* systematically. The author suggests focusing on organizing the strings by the sum of their indices from subsets Π(i), which allows us to construct a sequence that includes every string without omission.

This is like organizing a concert program by the duration of each song. You start with the shortest songs, gradually progressing to longer compositions, thereby ensuring no song is left out and maintaining an orderly show.

The idea is that you first list down all strings of the form str where the sum of the indices i and j is 2. Why we are starting with the summation of indices being 2, because you can see that my first string here the least indexing I can have here is str.

By beginning with the sum of indices equal to 2 (i.e., strings from subsets where i + j = 2), the arrangement guarantees that no strings are overlooked. The author explains listing them in a specific increment where all strings corresponding to the same sum appear together and systematically add more strings as the indices increase.

Think of stacking books by height. You first put all the small books together, then you move on to the medium-sized books, followed by the larger ones, ensuring that all books are represented without mixing sizes.

Why it is well defined ordering? Because you take any string x belonging to Π* it will belong to some Π(i). That means it will be appearing somewhere in the listing of the elements of Π(i) and it will have a form str.

The author argues the sequencing is valid because any arbitrary string from Π* must be part of some subset Π(i). This ensures that during the enumeration process, every single possible string will be listed without skipping any, validating the countability of Π*.

Imagine a school having multiple grades. Each student belongs to a certain grade, and during a school assembly, every student is called by their grade. Because every student fits into a grade, no one gets overlooked, and everyone is accounted for in the correct order.

--