Infinite union of finite unions

Question

Is the following sound reasoning, and if so, why?

Letting $S$ be a language over the alphabet $\Sigma$,

$$ \bigcup_{i=0}^{\infty}\left(\bigcup_{k=0}^{i-1}S^k\right) = \bigcup_{i=0}^{\infty}S^i $$

Answer 1

On the left-hand side you have $$\begin{align} & S^0 \\ \cup & S^0 \cup S^1 \\ \cup & S^0 \cup S^1 \cup S^2 \\ & \qquad \vdots \\ \cup & S^0 \cup S^1 \cup \cdots \cup S^n \\ & \qquad \vdots \end{align}$$ On the right-hand side you have $$S^0 \cup S^1 \cup S^2 \cup \cdots S^n \cup \cdots$$ Why are these equal?

Hint: What is $A \cup A$ for an arbitrary set $A$?

You can be more rigorous about it by proving directly that $x \in \text{LHS} \leftrightarrow x \in \text{RHS}$.

Answer 2

More generally, let $\{X_{\beta}:\beta<\alpha\}$ be a family of sets indexed by the elements of a limit ordinal $\alpha$. The following holds:$$\bigcup_{\beta<\alpha}\bigcup_{\gamma<\beta}X_{\gamma}=\bigcup_{\beta<\alpha}X_{\beta}.$$

If $x\in\bigcup_{\beta<\alpha}\bigcup_{\gamma<\beta}X_{\gamma}$, then there exists $\beta<\alpha$ such that $x\in\bigcup_{\gamma<\beta}X_{\gamma}$. Again, there exists $\gamma<\beta<\alpha$ such that $x\in X_{\gamma}$. Hence $$\bigcup_{\beta<\alpha}\bigcup_{\gamma<\beta}X_{\gamma}\subseteq \bigcup_{\beta<\alpha}X_{\beta}.$$

The other inclusion can also be verified directly, though this is where we require $\alpha$ be a limit ordinal: if $x\in\bigcup_{\beta<\alpha}X_{\beta}$, then $x\in X_{\beta}$ for some particular $\beta<\alpha$. Since $\beta+1<\alpha$ as well and $x\in\bigcup_{\gamma<\beta+1}X_{\gamma}$, the result follows.

Applying this to the case at hand, the family is $\{S^n:n<\omega\}$, and the equation is $$\bigcup_{n<\omega}\bigcup_{m<n}S^m=\bigcup_{n<\omega}S^n$$