If the alphabet is countably infinite, then is the number of finite-length strings over this alphabet countably or uncountably infinite?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ What have you tried and where did you get stuck? (Note that this is a pure mathematics question.) $\endgroup$– Raphael ♦Dec 31, 2015 at 11:45
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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.
answered Dec 31, 2015 at 11:05
-
$\begingroup$ Tehe. That nitpicked, what are other operations and how common are they? Taking automorphisms $X \to X$ comes to mind (definitely common!) but that's even stronger than taking powersets. Is the power set operation the weakest one for getting uncountability? Looking at the function world, it's taking $X \to \{0,1\}$ so it may very well be, since mapping to the singleton set gets you $X$ itself. $\endgroup$– Raphael ♦Dec 31, 2015 at 12:27
-
$\begingroup$ For a sanity check, Σ* given a finite alphabet is countably infinite in size, and Σ* given a countably infinite alphebet is still countably infinite in size? (I ask because the closure of the Kleene star confused the daylights out of me before, and this seems related but arrives at a different answer than my intuition) $\endgroup$ Dec 31, 2015 at 17:59
-
$\begingroup$ Yes, $\Sigma^*$ is countable as long as $\Sigma$ is countable (or finite). $\endgroup$ Dec 31, 2015 at 18:02
$\begingroup$
$\endgroup$
2
For a countably infinite alphabet A; AxN is also countably infinite...where Nis the set of natural numbers.(finite product of countable sets)
A finite string is a finite subset of AxN.( An ordered set of symbols)
Set of all finite subsets of a countably infinite set is countably infinite.(why)
-
1$\begingroup$ > "A finite string is any finite subset of AxN.( An ordered set of symbols)." {(a, 0), (b, 0)} wouldn't be, right? Assuming you want to order the symbols based on the second index. There certainly is an injection from the set of finite sequences to the set of finite subsets of $A \times N$ though. $\endgroup$ Dec 31, 2015 at 12:39
-
$\begingroup$ A finite string is A finite subset of ...edited. @TimonKnigge $\endgroup$– ARiDec 31, 2015 at 12:44