What's wrong with this proof? (Regular languages)

77 Views Asked by At

We want to show that for any fixed $n$, $\bigcup_{i=1}^n L_i$ is regular when all $L_i$ are regular.

I understand that this is only true for finite $n$. However, what's wrong with the following proof for infinite $n$ by induction?

Define $L^k$ to be $\bigcup_{i=1}^k L_i$.

For the basis step, we choose $n=1$. Then we have $L^k = L^1 = L_1$ which is regular by definition.

For the inductive hypothesis, let us assume that $L^k$ is regular with $k < n$. Then by the definitions of regular expressions, $L^k \bigcup L_{k+1}$ is also regular. But this is $L^{k+1}$ and so $L^{k+1}$ is regular.

Again, I understand why $n$ cannot be infinite. I am interested as to what point this proof is wrong.

1

There are 1 best solutions below

0
On BEST ANSWER

If you want to prove something for all ordinals, you usually need to do transfinite induction and you have two inductive steps to deal with: (i) successor ordinals: from $\phi(\alpha)$ conclude $\phi(\alpha+1)$ and (ii) limit ordinals: from $\phi(\alpha)$ for all $\alpha < \lambda$, conclude $\phi(\lambda)$. If you only do the successor case, you have proved that $\phi(n)$ holds for all finite $n$, but you can't conclude that $\phi(\alpha)$ holds for any infinite $\alpha$ (the canonical counter-example is when $\phi(\alpha)$ is defined to mean $\alpha$ is finite).