# Every language is regular?

Could anyone tell me the error in my reasoning:

1. The set of strings of a given alphabet is a countable set.
2. Every string can be determined by a regular language.
3. The union of two regular languages is again regular.
4. Thus: by taken a countable union of regular languages, we can form any possible language, and as this language is the union of regular languages, it must be regular as well.

Obviously this is not true, but I fail to see my error.

• The logic breaks down in going from (3.) to (4.). It might be easier to understand the mistake if you look at the related fake-proof: "The union of two finite sets is finite. Hence, by taking a countable union of finite sets, every countable set is also finite." Commented Nov 9, 2011 at 13:23
• Are you familiar with the NFA construction that shows regular languages are closed under union? What do you get when you apply this construction infinitely many times? Commented Nov 9, 2011 at 13:29
• Very nice question!
– user12205
Commented Nov 9, 2011 at 16:44
• similar proof that $e \in \mathbb Q$: $\frac1{!n} \in \mathbb{Q}$ and adding is closed over $\mathbb Q$ so $$\sum_{i=0}^\infty{\frac1{!i}} \in \mathbb Q$$ Commented Nov 11, 2011 at 11:04

This error can be traced to a wrong interpretation of mathematical induction; by induction you usually show that some result holds for any natural number $n$; it does not imply that the result holds for an infinite number. So in our case it is easy to deduce from 3 by induction that the union of any $n$ regular languages is regular, but you cannot infer that the union of an infinite number of regular languages is regular.