What is the cardinality of a string set with finite alphabet?

1.2k Views Asked by At

We can construct a language $\mathcal L$ with the finite alphabet $\mathcal A $ (e.g. $\{0,1,\dots,9\}$):

$$ \mathcal L=\{string|string=x^* \land x\in \mathcal A\} $$

$x^*$ is $x$'s Kleene Closure, which means repeat $x$ for zero or more times.

I got two conflicting results with two different ways.

Method 1

Let: $$ \mathcal A=\{0,1,\dots,9\}\cup\{.\}\\ \mathbb{R}^{(0,1)}=\{x|0<x<1,x\in\mathbb{R}\} $$

then: $ \forall x \in \mathbb{R}^{(0,1)}$, $x$ can be writen in format of $0.231\dots$, so $ string\_of(x) \in \mathcal L$.

So: $card(\mathcal L) \ge card(\mathbb{R}^{(0,1)}) = \aleph_1$

Method 2

We can arrange elements of $\mathcal L$ in aspect of string length:

Let $\mathcal A=\{0,1,\dots,9\}$, $num\_of(string)$ is the decimal value of the $string$

$$ \mathcal{L} = \bigcup_{i=0}^\infty \mathcal{L}_i \\ \mathcal{L}_0 = \{string|string \in \mathcal L \land len(string)=0\} \\ \mathcal{L}_1 = \{string|string \in \mathcal L \land len(string)=1\} \\ \mathcal{L}_2 = \{string|string \in \mathcal L \land len(string)=2\} \\ \dots $$

And for each $\mathcal{L}_i$ can be arranged as:

$$ \mathcal{L}_i=\{string_i^0, string_i^1,\dots,\dots,string_i^n\} \\ $$ where $n={\|\mathcal{A}\|^i}, \forall j,k, 0 \lt j \lt k \lt n, num\_of(string_i^j) \lt num\_of(string_i^k) $.

so I can arrange all of $\mathcal{L}$'s element in order, which means $card(\mathcal{L}) \le \aleph_0$

I cannot figure out the mistake of these two methods, can anyone help me? Thanks a lot.

1

There are 1 best solutions below

5
On BEST ANSWER

Your mistake is that the decimal expansion of a real number is not a finite string, so it is not in the Kleene closure of the alphabet.

If you agree that "Eventually $0$" can be exchanged with "finite" in this case, then you still didn't even manage to get $\frac13$ into your Kleene closure, let alone any irrational number.