Problem 56 - Discrete Mathematics with Applications

Question

If \(\Sigma\) is a nonempty alphabet, then \(\Sigma^{*}\) is infinite. (Hint: Assume \(\Sigma^{*}\) is finite. since \(\Sigma \neq \emptyset,\) it contains an element \(a\) Let \(x \in \Sigma^{*}\) with largest length. Now consider \(x a .\) )

Step-by-Step Solution

Answer

Assuming \(\Sigma^{*}\) is finite and \(\Sigma\) is nonempty with an element \(a\), we let \(x\) be the element in \(\Sigma^{*}\) with the largest length. Then, by creating a new element \(xa\) from elements in \(\Sigma^{*}\), we get a contradiction since \(xa\) is longer than x. Thus, our assumption was wrong, and \(\Sigma^{*}\) must be infinite.

Step 1: Assumption

Let's assume that \(\Sigma^{*}\) is finite. Since \(\Sigma\) is nonempty, it must contain at least one element, let's call it \(a\).

Step 2: Identify the largest element in \(\Sigma^{*}\)

Let's assume that there exists an element with the largest length in \(\Sigma^{*}\). We will call this element \(x\).

Step 3: Create a new element by appending \(a\) to \(x\)

Now, we can create a new element by appending element \(a\) to the existing largest element \(x\). This new element is \(xa\).

Step 4: Contradiction

We now have a problem because \(xa \in \Sigma^{*}\) (since it is formed from \(x\) and \(a\), both of which are elements of \(\Sigma^{*}\)), and its length is greater than the length of \(x\). This contradicts our assumption that \(x\) has the largest length among elements in \(\Sigma^{*}\).

Step 5: Conclusion

The contradiction we found in Step 4 shows that our initial assumption that \(\Sigma^{*}\) is finite was wrong. Therefore, we have proven that if \(\Sigma\) is a non-empty alphabet, then \(\Sigma^{*}\) is infinite.

Key Concepts

Alphabet

In mathematics, especially in the study of formal languages and automata theory, an "alphabet" is a finite, non-empty set of symbols. These symbols can be anything: letters, numbers, or even abstract shapes. For instance, if our alphabet is \{a, b\}, we can form strings such as "ab", "ba", or "aa" from this set.

Each symbol is important because it serves as the basic building block for strings in formal language theory. A non-empty alphabet, like the example in the exercise, ensures there is at least one symbol to work with.

• This also means that we can generate an infinite number of combinations or strings from the given alphabet.
• The set of all finite-length strings that can be created using the alphabet is denoted by \(\Sigma^*\).

Understanding this is crucial in comprehending concepts like infinite sets and string length, which are derived from the idea of non-empty alphabets.

Contradiction

The method of "proof by contradiction" is a common technique used to show that a particular statement must be true. In our case, to show that \(\Sigma^*\) is infinite, we start by assuming the opposite: assume that \(\Sigma^*\) is finite. This assumption is our starting point.

By following logical steps, we aim to find a contradiction to this initial assumption. The contradiction happens because we find a scenario that cannot possibly be true if our assumption holds.

• In the exercise, this contradiction arises when we consider adding a new symbol to the maximum-length string assumed in the finite set.
• Appending this symbol creates a new string that is longer than any previously defined, thus contradicting the idea of a 'maximum-length string.'

When we uncover this contradiction, it proves that our original assumption must be false, affirming that the set is infinite.

Infinite Sets

An "infinite set" is a concept in which there is no limit to the number of elements that can be included in a set. Unlike finite sets, which have a countable number of elements, infinite sets continue endlessly. \(\Sigma^*\), the set of all possible strings over a given alphabet \(\Sigma\), is a quintessential example.

Here’s why:

• From any non-empty alphabet, you can generate an ever-increasing number of strings simply by combining symbols indefinitely.
• This means you can keep appending symbols to form longer strings without any restriction on the string length.

The notion of infinite sets is fundamental in computer science because it allows for understanding languages that can generate an unlimited number of possible outputs or strings.

String Length

In the context of formal languages, "string length" refers to the number of symbols in a string. It is calculated by counting each distinct symbol used to form the sequence. For example, in the string "abc", the length is 3 because there are three symbols.

In the exercise, the idea of string length plays a critical role in generating a contradiction. We assume there is a longest string and that assumption leads us to add a symbol, forming a new string:\(xa\) in this case:

• This new string is longer than what was assumed to be the longest, resulting in a contradiction.
• Therefore, string length is connected to the reasoning that \(\Sigma^*\) is infinite because there is no cap on how long a string can be.

Understanding string length helps in grasping how new strings are created and how they compare in terms of size within \(\Sigma^*\).