1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ What have you tried and where did you get stuck? (Note that this is a pure mathematics question.) $\endgroup$ – Raphael Dec 31 '15 at 11:45
7
$\begingroup$

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.

$\endgroup$
  • $\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 '15 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$ – Cort Ammon Dec 31 '15 at 17:59
  • $\begingroup$ Yes, $\Sigma^*$ is countable as long as $\Sigma$ is countable (or finite). $\endgroup$ – David Richerby Dec 31 '15 at 18:02
0
$\begingroup$

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)

$\endgroup$
  • 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$ – Timon Knigge Dec 31 '15 at 12:39
  • $\begingroup$ A finite string is A finite subset of ...edited. @TimonKnigge $\endgroup$ – ARi Dec 31 '15 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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