# Prove that a formal language is infinite

I'm having trouble with the following exercise:

Let $\Sigma = \{a,b,c\}$ and $L$ be a formal language, that consists of all words which contain all three letters at least once. Show that $L$ is infinite.

I figured out that I could define a word

$w_0 = abc, w_0\in L$

so the condition is met, and then say

$w_i = w_0\cup_{i = 1}^{\infty}a, w_i \in L$

..which shows that you could add infinitely many letters(a's in this case) to it and therefore you can get infinitely many words.

Now I don't know how to show that the rule above does indeed produce infinitely many words, isn't it just obivous? I'm also not sure about the notation - should I just add "This shows that L is infinite" ? And finally I don't know if I'm allowed to use a specific pre-condition like "abc"

• Argue by contradiction, suppose there was a last word $w_n$ then you could just add an a onto this to get a new word... Commented Oct 20, 2012 at 17:03
• Though you cannot add infinitely many letters to $w_0$, you can only add arbitrarily many letters to it (which gives you infinitely many different words). Commented Oct 20, 2012 at 17:24

One way to formally prove that a language is infinite is to give an explicit mapping from $\mathbb{N}$ to $L$ which maps every $n$ to a distinct word $w \in L$. Using your reasoning about words $a\ldots abc$, you could use $f: \mathbb{N} \to L$, $$n \to a^nabc$$
Now, since the length $|f(n)|$ of $f(n)$ is $3+n$, $f(n) \neq f(m)$ if $n \neq m$, since words with different lengths cannot be equal. $f$ thus has the necessary propertiers, hence $L$ is infinite.