# Proof that if the alphabet set is at most countable, then strings cnt

• Matrim
In summary, the lemma states that if the alphabet A is at most countable, then the set A^* of strings over A is also countable. The proof provided uses the concept of prime numbers to define a function \beta that maps strings of symbols from the alphabet A to natural numbers. This function is injective, meaning that different strings will be mapped to different numbers. However, the function does not account for order, so a modified version is proposed to account for repetition and order. The function \beta is sufficiently defined to prove that the set of finite strings is countable, but not the set of infinite strings. The authors may have assumed some understanding from the reader, but the concept can be difficult to grasp without further explanation
Matrim
Lemma: If $A$ is an at most countable alphabet, then the set $A^*$ of strings over $A$ is countable.

Proof begin:
Let $p_n$ be the $n^{th}$ prime number: $p_0 = 2$, $p_1=3$, $p_2=5$, and so on. If $A$ is finite, say $A = {a_0, a_1, ... , a_n}$, where $a_0, a_1, ... , a_n$ are pairwise distinct, or if $A$ is countable, say $A = {a_0, a_1, ... }$, where $a_i$ are pairwise distinct, we can define the map $\beta :A^{*}\rightarrow N$ by

$$\beta(emptyString) := 1$$
$$\beta(a_{i_{0}}, ..., a_{i_{r}}) := {p_{0}}^{i_0 + 1} * ... * {p_{r}}^{i_r + 1}$$

Clearly $\beta$ is injective and thus $A^*$ is at most countable. Also it cannot be finite...thus countable.

end proofOk...my problem with this proof (taken from Mathematical Logic 2nd ed by Ebbinghaus et. al.) is the enumeration of the primes in the function $\beta$. The string of symbols from the alphabet $A$ can have repetition so I would think that we need more subscripts to denote this. For example if the alphabet is the English alphabet then alphabet might map to, the primes from 2 to the 26th prime. then a string like qqwertyyyy would be:

$$\beta(qqwertyyyy) = 59^2 * 83^1 * 11^1 * 61^1*71^1*97^4$$

If my interpretation is right, then we really need something more like,

$$\beta(emptyString) := 1$$

$$\beta( a_{i_{0}}, ..., a_{i_{r}},a_{j_{0}}, ..., a_{j_{k}},a_{m_{0}}, ..., a_{m_{x}},...) := {p_{i}}^{r} * {p_{j}}^{k} * {p_{m}}^{x} *...$$

Which, based on the unique factorization theorem, we can conclude that $\beta$ is injective? And thus (from a previous lemma) we can conclude countable...almost. There is the question of order...which my function does not account for...(which means it is not well defined)

abcd and adbc would map to the same number and there would no way to discern the two strings. So I would really need something that would keep order as well...this could be done by taking the 27th prime for the first position, and then raise it to the power of the prime for the letter for that position raised to the power of the number of repetitions of that letter. Then finding the letter for the first position requires seeing how many factors of 27 there are then this is some prime from the first to the 26th prime...to get repetitions just see which prime it is and how many factors it has. Thus we get we defined function that is injective (which is easy since it is clearly a strictly increasing monotonic function)

In other words, I believe it can be done (and I think I have done it) and I am not hung on this proof in terms of agreement, but in following the logic of the authors...

What I would like is to understand what the author(s) proof is supposed to mean and how it accounts for all possible strings in an alphabet. It might do what it is supposed to do and there may just be a lot more understanding expected from the reader...

Matrim said:
For example if the alphabet is the English alphabet then alphabet might map to, the primes from 2 to the 26th prime. then a string like qqwertyyyy would be:

$$\beta(qqwertyyyy) = 59^2 * 83^1 * 11^1 * 61^1*71^1*97^4$$

I stopped reading here because this indicates you have misunderstood how β is defined. For the string in question we should have something like β(qqwertyyyy) = 21731752375111813201725192523252925.

Ah...well that is much nicer. And it cleanly accounts for position. However, I don't see how what the author(s) wrote and what you are wrote are the same...there is the same subscript, i, for all the alphabet items in the definition of β Then these are iterated over...which means (to my eyes) that we have a single term from the alphabet repeated r times.

Would you please explain what the subscripts i and r mean? It is not clear to me...

edit: nor is it clear how q is being mapped to 17 and w to 23...these are the ordered position within the alphabet?...one sec...let me think about this.

Last edited:
What the authors mean to say is the that the $a_i$ are terms of the alphabet and the subscript iterates over the items in the alphabet. But that was not clear to me...thank jgens.

Last edited:
The set of finite strings is countable, the set of infinite strings is not.

## 1. What is the meaning of "alphabet set is at most countable"?

The term "at most countable" refers to a set that has either a finite number of elements or a countably infinite number of elements. A countably infinite set is one that can be put into a one-to-one correspondence with the set of natural numbers.

## 2. What does "strings cnt" represent in this context?

"Strings cnt" refers to the number of possible strings that can be formed using the given alphabet set. This includes strings of any length, including the empty string.

## 3. Why is it important to prove that if the alphabet set is at most countable, then strings cnt?

This proof is important because it helps us understand the relationship between the size of an alphabet set and the number of possible strings that can be created from that set. It also has applications in computer science and linguistics, as we often use alphabet sets to represent characters or symbols in languages or computer programs.

## 4. Can you provide an example to illustrate this proof?

Sure, let's consider an alphabet set with only two letters, A and B. This set is clearly at most countable, as it has only two elements. Using this alphabet set, we can create an infinite number of strings, such as "A", "B", "AA", "AB", "BA", "BB", "AAA", and so on. Therefore, this example supports the proof that if the alphabet set is at most countable, then strings cnt.

## 5. Are there any exceptions to this proof?

Yes, there are some exceptions. For example, if we have an infinite alphabet set, such as the set of all real numbers, then the number of possible strings formed from this set is uncountably infinite, meaning it cannot be put into a one-to-one correspondence with the set of natural numbers. Therefore, this proof does not apply in cases where the alphabet set is uncountable.

• Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
551
• Set Theory, Logic, Probability, Statistics
Replies
8
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
14
Views
2K
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
7
Views
508
• Calculus and Beyond Homework Help
Replies
1
Views
766
• Calculus and Beyond Homework Help
Replies
6
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
55
Views
5K
• Topology and Analysis
Replies
2
Views
468