I have a question which may sound silly to you, but I'm confident that I don't understand Cantor's diagonal argument very well to use it. Any provided insight would be appreciated.

I was tasked with finding the cardinal number of the set $$A^{*} = \{\epsilon, a, b, c, aa, ab, ac ... \}$$

Which is the iterated set of set $A$, using Kleene's operator.

Now, at first I thought that the cardinality of this set is bigger than $\aleph_0$ because the set has infinitely many elements, but each string in the set can be up to infinite in length. I thought it was impossible to construct a bijection between $\mathbb{N}$ and $A^{*}$, but this simple observation did the trick: $1 \rightarrow \epsilon$, $2 \rightarrow a$, $3 \rightarrow b$, $4 \rightarrow c$, $5 \rightarrow aa$...

Question: Why can't we use Cantor's diagonal argument to prove that this set has a bigger cardinality than the set of natural numbers?

For example, if I have:

$s_1 = (A, a, c, b, a, c, ...)$

$s_2 = (c, B, b, c, c, a, ...)$

$s_3 = (a, a, C, a, c, a, ...)$

$s_4 = (b, c, a, A, c, c, ...)$

Each capital letter represents the letter at position $a_{ii}$. If I create a new string $d$ so that $d_1 \ne d_{1,1}$ etc, why isn't this a valid proof that the set's cardinality is bigger than $\aleph_0$?

  • $\begingroup$ You use Cantor's diagonal argument as if all those sequences are infinite and you are also making an infinite sequence that is none of the given ones. In reality, they are all finite and you should also be making a new finite sequence. $\endgroup$
    – user700480
    Jun 2 at 20:42

2 Answers 2


Every string in $A^*$ is finite. Your $s_1,s_2,s_3$ strings, and so on, appear to be infinite. So, none of those strings is in the set $A^*$. Furthermore, the string $d$ is infinite, so it is not in $A^*$.


This set is a countable union of finite sets $X_i$ where $X_i$ is the set of strings of length exactly $i$. Each $X_i$ has $|X_i| < \mathbb{N}$, so we have an inclusion into $\mathbb{N}$, and the countable union of countable sets is countable, by countable choice, so an upper bound for this set's cardinality is that of $\mathbb{N}$. On the other hand, the set is evidently infinite, so this is the cardinality.

Cantor's argument doesn't work because the string you obtain is not actually in the set.


Not the answer you're looking for? Browse other questions tagged .