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

[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}<br /> *...$$

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...

 

[jgens]

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) = 2¹⁷3¹⁷5²³7⁵11¹⁸13²⁰17²⁵19²⁵23²⁵29²⁵.

 

[Matrim]

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.

 

[Matrim]

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.

 

[Hornbein]

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