Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Today in Coding/Cryptography class, we were talking about basic definitions, and the professor mentioned that for a set $A=\left \{ \left. a, b, \dots, z \right \} \right.$ (the alphabet) we can define a set $A^{*}=\left \{ \left. a, ksdjf, blocks, coffee, maskdj, \dots, asdlkajsdksjfs \right \} \right.$ (words) as a set that consists of all finite sequences of the elements/letters from our $A$/alphabet. My question is, is this set $A^{*}$ countably or uncountably infinite? Does it matter how many letters there are in your alphabet? If it was, say, $A=\left \{ \left. a \right \} \right.$, then the words in $A^{*}$ would be of form $a, aa, aaa, \dots$ which, I think, would allow a bijection $\mathbb{N} \to A^{*}$ where an integer would signify the number of a's in a word. Can something analogous be done with an alphabet that consists of 26 letters (Latin alphabet), or can countability/uncountability be proved otherwise? And as mentioned before, I am wondering if the number of elements in the alphabet matters, or if all it does is change the formula for a bijection.

P.S. Now that I think of it, maybe we could biject from $\underset{n}{\underbrace{\mathbb{N}\times\mathbb{N}\times\mathbb{N}\times\dots\times\mathbb{N}}}$ to some set of words $A^{*}$ whose alphabet $A$ has $n$ elements? Thanks!

share|improve this question
5  
You can enumerate first the one-letter words, then the two-letter words, etc. For each word length, you can order all the words of that length lexicographically and then count through them. –  joriki Mar 28 '11 at 22:16
add comment

2 Answers 2

up vote 3 down vote accepted

Proposition. If the alphabet $A$ is countable, the set $A^*$ of all finite strings in that alphabet is also countable.

Proof. $A, A^2 = A \times A, A^3 = A \times A \times A$, etc. are all countable and well-ordered (under the lexicographic ordering induced by the well-ordering of $A$), and $$A^* = \bigcup_{n=0}^{\infty} A^n$$ and the union of countably many well-ordered countable sets is again countable, so $A^*$ is countable. Note this does not require the axiom of (countable) choice.

However, the set $A^{\mathbb{N}}$ of all countably-infinite strings is countable if and only if $A$ is empty or is a 1-letter alphabet.

share|improve this answer
add comment

Suppose the 26 letters are "digits" in base-26. Any finite string of letters can be thought of as a unique positive integer in base-26. The positive integers are countable, so your set of strings must be as well.

(Actually, to be precise: letting the symbols in your set be non-zero digits establishes a bijection between your set and a subset of the natural numbers, so the cardinality of your set is less than or equal to that of the natural numbers; letting the symbols in your set be digits, including a "zero" digit, establishes a surjection from your set onto the natural numbers [leading zeros cause multiple digit strings to hit the same natural number], so the cardinality of your set is greater than or equal to that of the natural numbers; so since the cardinality of your set is ≥ and ≤ that of the natural numbers, they are equal in cardinality, so your set is countable.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.