1
$\begingroup$

Is my understanding of cardinality of sets of strings correct?

1) A finite set of symbols (containing $x$ symbols) and strings of finite length $n$ gives us $x^n$ finitely many strings.

2) A finite set of symbols (containing $x$ symbols) and strings of countably infinite length $\aleph_0$ gives us $x^{\aleph_0}$ uncountably many strings.

3) A countably infinite set of symbols (containing $\aleph_0$ symbols) and strings of finite length $n$ gives us $\aleph_0^n$ countably infinitely many strings.

4) A countably infinite set of symbols (containing $\aleph_0$ symbols) and strings of countably infinite length $\aleph_0$ gives us ${\aleph_0}^{\aleph_0}$ uncountably many strings.

And I've learned that there are countably infinite number of strings of finite lengths given a set of finitely many symbols, which is different from saying $x^n$, since it's talking about all values of the finite number $n$. Is there a formula to capture this notion in relation to $x^n$?

$\endgroup$
  • 1
    $\begingroup$ 2 is wrong unless 1 < x. Simplify the cardinality given in 3. $\endgroup$ – William Elliot Nov 23 '19 at 15:11
  • 1
    $\begingroup$ The correct notation for the cardinality of countably infinite sets is $\aleph_0$; I replaced your $\aleph$ accordingly. $\endgroup$ – Andrés E. Caicedo Nov 23 '19 at 15:11
  • 1
    $\begingroup$ Thank you both. Could you answer the question at the bottom when you get a chance? $\endgroup$ – csp2018 Nov 23 '19 at 15:15
  • $\begingroup$ @WilliamElliot: Why would it be wrong for $x=1$? As far as I can see, with only one symbol, there is only one string with length $\aleph_0$, and $1^{\aleph_0}=1$. $\endgroup$ – celtschk Nov 23 '19 at 15:29
  • $\begingroup$ @celtschk I wrote that it would be uncountably many, so I'm assuming it's wrong when x is less than or equal to 1 since there would be 1 string? $\endgroup$ – csp2018 Nov 23 '19 at 15:34
2
$\begingroup$

Apart from the issue about $x$ pointed out in the comments, your assertions are correct.

For the last one, if $X$ is a finite set of cardinality $x$, let $X^n$ denote the set of words of length $n$ on the alphabet $X$ (a finite set of cardinality $x^n$, as you observed). Note that, for $n = 0$, $X^0$ is the singleton containing the empty word. Then the set of all finite words, usually denoted $X^*$, is the union $\bigcup_{n \geqslant 0} X^n$. As a countable union of finite sets, it is countable, and hence its cardinality is $1$ if $x = 0$ and $\aleph_0$ otherwise.

$\endgroup$

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.