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.

  • 11
    $\begingroup$ 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." $\endgroup$ – Srivatsan Nov 9 '11 at 13:23
  • 3
    $\begingroup$ 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? $\endgroup$ – Zach Langley Nov 9 '11 at 13:29
  • $\begingroup$ Very nice question! $\endgroup$ – user12205 Nov 9 '11 at 16:44
  • 2
    $\begingroup$ 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$$ $\endgroup$ – ratchet freak Nov 11 '11 at 11:04

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.

  • $\begingroup$ Note that there are loads of things that work for infinite extensions, until the extension is countable/recursive/enumerable. $\endgroup$ – Raphael Nov 11 '11 at 21:31

The union of two regular languages is regular implies that finite unions are again regular, but you cannot conclude that the union of infinitely many languages is regular (and in fact this is not true).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.