Set which has a finite bounded string length

Question

I am trying to work on a proof. I know that using diagonalization argument, we can prove that set of languages over an alphabet is countable. But I am trying to prove that set of all languages over {0,1} with a bounded maximum string length is countable.

Answer 1

I don't think there's anything wrong with what you're arguing. Perhaps a bit more formally one could say:

Suppose we have some maximum string length $N$. Then there are $2^N$ strings of length $N$, $2^{N-1}$ strings of length $N-1$ and so on down to $2^0$ strings of length $0$. This makes for a total of $2^{N+1}-1$ possible strings. Then a language can either include or not include each of these strings, so there are $2^{2^{N+1}-1}$ total languages (since a language is defined by the words it includes). Note that this is a large but finite number.

Then, as you wanted to, you can say that for each $N \in \mathbb{N}$, the set of all such languages is a countable union of finite sets, which is countable.