Is the set of languages over an alphabet Σ missing k words from Σ* countable?

Question

My original question is whether $\mathscr{L}$, the set of all languages over an alphabet $Σ$, each of which missing finitely number of words from $Σ$* is countable. I think I can prove the set is countable by proving it is $\bigcup_{k=0}^{}S_k$ where each $S_k$ is the set of languages missing $k$ words from $Σ$*. Now, is there a way to prove each $S_k$ is countable? Is it enough to say each $S_k$ is also a union of subsets of $Σ$*?

Answer 1

Yes.

Fix a bijection $f\colon \Bbb N \to \Sigma^*$. ($\Sigma$ is finite, so there is such an $f$.) Let $\mathscr{L}$ be the class of all languages $L\subseteq \Sigma^*$ such that $\Sigma^*\setminus L$ is finite. Then for every $L\in \mathscr{L}$, $f^{-1}(L)$ is a cofinite subset of $\Bbb N$, and conversely for every cofinite set of integers $C$, $f(C)\in\mathscr{L}$. Thus, $\mathscr{L}$ is bijectable with the cofinite sets of integers, which are bijectable with the finite sets of integers. Finally, note that the set of finite sets of integers is countably infinite.

More directly, if $\mathscr{F}$ is the set of finite languages over $\Sigma$, then $L\mapsto (\Sigma\setminus L)$ bijects $\mathscr{F}$ and $\mathscr{L}$, and $\mathscr{F}$ is countable.