- #1
Matrim
- 3
- 0
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
<br /> \beta(emptyString) := 1<br />
<br /> \beta(a_{i_{0}}, ..., a_{i_{r}}) := {p_{0}}^{i_0 + 1} * ... * {p_{r}}^{i_r + 1}<br />
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:
<br /> \beta(qqwertyyyy) = 59^2 * 83^1 * 11^1 * 61^1*71^1*97^4<br />
If my interpretation is right, then we really need something more like,
<br /> \beta(emptyString) := 1<br />
<br /> \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...
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
<br /> \beta(emptyString) := 1<br />
<br /> \beta(a_{i_{0}}, ..., a_{i_{r}}) := {p_{0}}^{i_0 + 1} * ... * {p_{r}}^{i_r + 1}<br />
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:
<br /> \beta(qqwertyyyy) = 59^2 * 83^1 * 11^1 * 61^1*71^1*97^4<br />
If my interpretation is right, then we really need something more like,
<br /> \beta(emptyString) := 1<br />
<br /> \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...