Could anyone tell me the error in my reasoning:
- The set of strings of a given alphabet is a countable set.
- Every string can be determined by a regular language.
- The union of two regular languages is again regular.
- 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.
Best Answer
The answer was already given by Florian, but I'll elaborate a little: This is a private case of a general confusion in Mathematics: Something that is true/definable for two elements can be usually extended to any number of finite elements if it satisfies some associativity requirement, but not to an infinite number.
For example, addition: you know how to add two numbers and can extend this to any finite number of summands, but it does not imply you know how to sum an infinite number of summands (and indeed, summing infinite number of summands may result in an undefined or infinite result although for any finite number of summands the result is defined and finite). Another example is the topological result/definition that the intersection of two open sets is yet again a open set - this is easily extended to the intersection of any finite number of open sets, but is wrong for an infinite intersection.
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.