# 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." –  Srivatsan Nov 9 '11 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? –  Zach Langley Nov 9 '11 at 13:29
Very nice question! –  user12205 Nov 9 '11 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$$ –  ratchet freak Nov 11 '11 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.