All languages are regular, as unions of singleton languages

Question

We know that singleton languages (languages containing exactly one word) are regular. We also know that a finite union of regular languages is also regular.

Suppose there is a non-regular language $L$. For every finite subset $\{x_1,x_2,\ldots,x_i\}$ of elements of $L$, we can take the corresponding singleton languages and compute their union. This new language (which is a subset of $L$) should be regular. Now we do the same with rest of the language.

Finally, we must have $sL_1, sL_2,\dots, sL_n,\dots$ which are all subsets of $L$ that are finite regular languages. If we take the union of $sL_1, sL_2,\dots, sL_i$, where $i$ is finite, we again have a regular language. We do this for all languages obtained from $L$.

If we keep doing such "finite" unions of regular languages, we will eventually obtain $L$, which must be regular because we obtained it from a finite union of regular languages.

This obviously isn't right, but I don't understand why.

Answer 1

The same "argument" would show that $\mathbb{N}$ is finite since it's the union of finite sets $$\mathbb{N}=\{0\}\cup\{0,1\}\cup\{0,1,2\}\cup ...$$ The point is that knowing that a given property is preserved under a given operation does not mean that it's preserved under "infinite iterations" of that operation.

Answer 2

You proved that any finite languages are regular. All the languages that you generated are finite.

Answer 3

You need to keep doing it an infinite number of times before you reach any infinite languages. So your proof will involve transfinite induction. As Wikipedia says:

Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers.

Let P(α) be a property defined for all ordinals α. Suppose that whenever P(β) is true for all β < α, then P(α) is also true. Then transfinite induction tells us that P is true for all ordinals.

Usually the proof is broken down into three cases:

• Zero case: Prove that P(0) is true.
• Successor case: Prove that for any successor ordinal α+1, P(α+1) follows from P(α) (and, if necessary, P(β) for all β < α).
• Limit case: Prove that for any limit ordinal λ, P(λ) follows from [P(β) for all β < λ].

It is the limit case you won't be able to prove.