[Solved]: Number of finite strings over a countably infinite alphabet

Problem Detail: 

If the alphabet is countably infinite, then is the number of finite-length strings over this alphabet countably or uncountably infinite?

Asked By : Vivek Barsopia

Answered By : David Richerby

It's countable. The set $S_\ell$ of strings of length $\ell$ is $\Sigma\times\dots\times\Sigma$, which is a finite product of countable sets, so is countable. Now, the set of all finite strings is $\bigcup_{\ell\geq 0}S_\ell$, which is a countable union of countable sets, which is countable.

Usually, you can only get an uncountable set from countable ones by taking the power set.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51319