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 $SigmatimesdotstimesSigma$, which is a finite product of countable sets, so is countable. Now, the set of all finite strings is $bigcup_{ellgeq 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
