Cardinals of the set of all languages $L=L^*$ over $\Sigma=\{a\}$.

Question

Had an exam today and there was the following question:

Calculate the cardinality of the set of all languages $L$ over $\Sigma=\{a\}$ such that $L = L^*$.

I have no idea how to solve it. Is it possible to explain how to prove it?

Answer 1

A string over $\Sigma = \{a\}$ is just a string of some number of $a$'s, so it can be uniquely identified by its length. That is, we can identify the set of strings over $\Sigma$ with the set of natural numbers $\mathbb{N}$. Under this identification, concatenation of strings corresponds to addition.

A language over $\Sigma$ is just a set of strings over $\Sigma$, so we can identify a language with a set of natural numbers $L\subseteq \mathbb{N}$, and then $L^*$ is the set of all finite sums of numbers in $L$. So we have $L = L^*$ if and only if $L$ is closed under finite sums.

Thus we've reduced the problem to a number-theoretic one: What is the cardinality of the set of subsets of $\mathbb{N}$ which are closed under finite sums?

Certainly there are infinitely many. For each $n\in \mathbb{N}$, the set $\langle n \rangle = \{kn\mid k\in \mathbb{N}\}$ of multiples of $n$ is closed under finite sums. I claim that if $L\subseteq \mathbb{N}$ is closed under finite sums, then there exists some $N$ and $n$ in $\mathbb{N}$ such that $L\subseteq \langle n\rangle$ and $L\cap [N,\infty) = \langle n\rangle \cap [N,\infty)$, where $[N,\infty) = \{m\in \mathbb{N}\mid N\leq m\}$. Note that there are countably many choices of $n$ and countably many choices of $N$. And once we've fixed $n$ and $N$, $L$ is totally determined by which elements of $\{0,\dots,N-1\}$ are in it, so there are only finitely many ($2^N$) possibilities for $L$. Thus, the claim establishes that the set of subsets of $\mathbb{N}$ which are closed under finite sums has cardinality $\aleph_0$.

Proof of the claim: If $L = \emptyset$ or $L = \{0\}$, then we're done, taking $n = 0$ and $N = 1$. If not, then $L$ contains a non-zero element. Let $n$ be the gcd of $L$, and write $n = b_1c_1 + \dots + b_kc_k$ for some $b_1,\dots,b_k\in \mathbb{Z}$ and $c_1,\dots,c_k\in L$ by Bézout's identity. If you don't know about Bézout's identity, the following paragraph gives a quick proof.

Let $n$ be the least non-zero natural number such that there exist $b_1,\dots,b_k\in \mathbb{Z}$ and $c_1,\dots,c_k\in L$ with $n = b_1c_1 + \dots +b_kc_k$. I claim that $n$ divides every element of $L$. Indeed, if $m\in L$, then by long division we can write $m = qn + r$ where $q,r\in \mathbb{N}$ and $r < n$. If $r = 0$, then $n$ divides $m$. If $r\neq 0$, then $r = m - qn = 1m + (-qb_1)c_1 + \dots + (-qb_k)c_k$, which contradicts minimality of $n$.

Ok, so we have $L\subseteq \langle n \rangle$. The reason the reverse inclusion doesn't hold is because some of the $b_i$ may be negative. At the cost of reordering the $b_i$ and $c_i$, we may assume that $b_1,\dots,b_j < 0$ and $b_{j+1},\dots,b_k > 0$. Note that $D = -b_1c_1 + \dots + -b_jc_j\in L$, since it is a finite sum of the $c_1,\dots,c_j\in L$.

Let $qn$ be the least non-zero multiple of $n$ which is in $L$. Let $N = (q-1)D$. Now for any $m\in \langle n\rangle \cap [N,\infty)$, we can write $m = N + sqn + tn$, for some $s\in \mathbb{N}$ and $0\leq t \leq q-1$ (here $s$ and $t$ are the quotient and remainder when $(m - N)/n$ is divided by $q$). So we can write $m = N + sqn + t(b_1c_1 + \dots + b_kc_k)$. But then $m\in L$, since we can cancel the negative multiples $tb_1,\dots,tb_j$ of $c_1,\dots,c_j$ using the positive multiples of $c_1,\dots,c_j$ in $N = (q-1)D$. Explicitly, $m$ is a finite sum of the $c_1,\dots,c_j\in L$ (the ones in the definition of $N$ left over after cancelling), plus $qn\in L$ finitely many times, plus a finite sum of the $c_{j+1},\dots,c_k\in L$.