# How many languages exist over a finite alphabet?

I'm currently reviewing my Automata and Languages Theory course and I stumbled upon the following exercise exams. Link

In "Exercises for ACS 1, Fall 2004, sheet 1", exercise 1 item C, the question is,

How many languages exist over the symbol sets from (a)?

Question (a) describes the alphabets $S=\{a,b\}$ and $S=\{1\}$. The answer to the question as provided in the same link is

In both cases, $|Σ^*| = \mathbb N$, that is, there are $2^{\mathbb N}$ many languages over these alphabets – indeed, over any finite alphabet there are $2^{\mathbb{N}}$ languages.

Here $\mathbb{N}$ is the set of all natural numbers. I am confused as to how the author came to this conclusion.

Update: In my understanding, since {a,b} is a set of strings of {a,b}, it follows that it is a subset of {a,b}* or the set of all strings over {a,b}. So, as per set theory, the cardinality of a set containing the subsets of all strings over {a,b} = powerSet({a,b}*) whose cardinality is equal to $2^{\mathbb{N}}$. Is my understanding correct?

• This is really a question on set theory. I suggest you review set theory first, and then see if you can understand the answer. – Yuval Filmus Mar 19 '16 at 10:22

The number of possible words is countably infinite, since we can list them in increasing order of length: $$\epsilon,a,b,aa,ab,ba,bb,\ldots \\ \epsilon,1,11,111,1111,11111,\ldots$$ This is why $|\Sigma^*| = \aleph_0$ (to use a more common notation). The set of all possible languages is the set of all subsets of $\Sigma^*$ (known also as the power set of $\Sigma^*$), which by definition has cardinality $2^{\aleph_0} = \aleph$.