# Recursive String Proof

Have I done this right? I have shown that every element of Σ exists in Σ*, so is it ok to do what I did in step 5?

 If Σ = {s,i, n, g}, show that singing is in Σ*.
Solution: (in 5 steps)
1) Since λ ∊ Σ* and i ∊ Σ, i ∊ Σ*.
2) Since i ∊ Σ* and n ∊ Σ, in ∊ Σ*.
3) Since in ∊ Σ* and g ∊ Σ, ing ∊ Σ*.
4) Since ing ∊ Σ* and s ∊ Σ, sing ∊ Σ*.
5) Since sing ∊ Σ*, and ing ∊ Σ*, singing ∊ Σ*.

-

This can't be optimal. Either your definition of the Kleene star permits arbitrary concatenation, in which case you can do everything in one step, or it doesn't, in which case you need seven steps. Your step 5 is essentially using the theorem that $\Sigma^\star=\Sigma^\star \Sigma^\star$.
Well, if you have the theorem I mention, then you can do it in five steps as you have it. Or, you could generalize that theorem as below, and do it in one step: $\Sigma^\star=\Sigma^\star\Sigma^\star\Sigma^\star\Sigma^\star\Sigma^\star\Sigma‌​^\star\Sigma^\star\supseteq \Sigma\Sigma\Sigma\Sigma\Sigma\Sigma\Sigma\ni singing$ – vadim123 Jun 16 '13 at 23:54
@vadim123 One could argue that the 'generalization' of the theorem from $\Sigma^*=\Sigma^*\Sigma^*$ to arbitrary concatenations also takes some steps... – Steven Stadnicki Jun 16 '13 at 23:56