# Proof that the complement of a finite language is always an infinite language

Let's say that we have a language $$L$$ that is finite.
How can I prove that the complement of $$L$$, i.e., $$\bar{L}$$, is always an infinite language?

Obs.: infinite language in this case means that is possible to construct an infinite set of words that are acceptable by $$\bar{L}$$.

The set $$\Sigma^*$$ is an infinite set (you can build a bijection between the naturals and the words in $$\Sigma^*$$ if you wish to prove this, or you can observe that, for every $$k \in \mathbb{N}$$, $$\Sigma^*$$ contains at least one word of length $$k$$).

Let $$L$$ be a finite language and suppose towards a contradiction that $$\overline{L} = \Sigma^* \setminus L$$ is finite. Then $$\Sigma^* = L \cup \overline{L}$$ must also be finite (since it's a finite union of finite sets). This provides the sought contradiction.

Here is a formal proof for the statement (warning, this really is a formal proof, and hence is not very intuitive):

Let $$\Sigma$$ be a non-empty alphabet (either finite or infinite), and let $$L\subset \Sigma^*$$, with $$|L|\in \mathbb{N}$$ ($$L$$ is finite).

Let $$\alpha \in \Sigma$$. By definition of the klenee-star operator, we can construct a function $$g:\mathbb{N}\rightarrow \Sigma^*$$ by $$g(k)=\alpha^k$$ ($$\alpha$$ repeated $$k$$ times). This function is one-to-one, since $$|g(k)|=|\alpha^k|=k$$ (where $$|w|$$ denotes the length of the string $$w$$), and thus for any $$k_1, k_2$$ with $$g(k_1)=g(k_2)$$ we must have $$k_1=|g(k_1)|=|g(k_2)|=k_2$$.

Thus, we proved that $$\aleph_0=|\mathbb{N}|\le |\Sigma^*|$$.

Now, let us begin showing that $$\aleph_0\le |\Sigma^* \setminus L|$$. Denote by $$n_{max}:=\max\{|w|\mid w\in L\}+1$$, and define $$f:\mathbb{N}\rightarrow (\Sigma^*\setminus L)$$ by $$f(k)=\alpha^{n_{max}+k}$$.

First, we have to show that this really is a function (by showing that $$f(k)\in \Sigma^*\setminus L$$ for all $$k\in\mathbb{N}$$). Indeed, if we assume towards contradiction that $$f(k)\in L$$ for some $$k$$ - we get that $$|f(k)| by the definition of $$n_{max}$$. But $$|f(k)|=|\alpha^{n_{max}+k}|=n_{max}+k \ge n_{max}$$ which is clearly a contradiction (we got that $$n_{max}).

Now we have to show that $$f$$ is one-to-one. By a similar argument to what we did before to prove that $$\Sigma^*$$ is infinite, we can conclude that $$f$$ is one-to-one, and hence $$\aleph_0=|\mathbb{N}|\le |\Sigma^*\setminus L|=|\bar L|$$ which is exactly what we wanted to show.

Lets denote $$n:=|L|\in \mathbb{N}$$.

For any nonempty $$\Sigma$$, it is clear that $$\Sigma^*$$ is infinite.

By definition, $$\bar L = \Sigma^*\setminus L$$. Therefore, $$|\bar L| = |\Sigma^*\setminus L| = |\Sigma^*|-|L| = \infty - n=\infty$$.

It is not a formal proof (neither a valid one), but it should suffice for you as intuition to understand why $$\bar L$$ is infinite.

• Sorry, in your answer you mean that $\Sigma$ is a finite alphabet? In this case, what do you mean by $\Sigma^*$ ? Nov 19 '21 at 17:44
• -1, I find subtracting cardinalities is handwavy at best and wrong at worst (and in all cases potentially confusing to beginners). For example, $|\mathbb{Z}\setminus\mathbb{N}| = \infty - \infty = 0$, despite negative integers existing. Nov 19 '21 at 18:18
• Yes, I agree with @ComFreek. This is not a valid proof. Nov 19 '21 at 18:25
• I never said this is a valid proof. Its just intuition. Substracting cardinalities is only well-defined when the RHS of the subtraction is finite (as in this case) Nov 19 '21 at 18:36
• Ok, you didn't said that this was a valid proof. Nov 19 '21 at 18:42