Regular expression. Proof.

Question

Let $A = \{a,b,c\} $ be an alphabet. Let $\alpha $ be a regular expression. And: $$ 1) \epsilon \in \alpha \\ 2) a\alpha \subset \alpha \\ 3) b\alpha \subset \alpha $$ Prove, that: $$(a+b)^* \subset \alpha $$ Intuitively, it is obvious. But I have a problem with formal proof. I think about induction.

Answer 1

I don't understand your second idea. But induction will work. Recall that $$ (a+b)^* = \bigcup_n (a+b)^n $$ We will show by induction that $(a+b)^n \subseteq \alpha$.

For $n=0$, this is true by 1), as $(a+b)^0 = \{\epsilon\}$.

Now, suppose $(a+b)^n \subseteq \alpha$ holds and consider a word $w \in (a+b)^{n+1}$. Then $w = w_1w'$ with $w_1 \in \{a,b\}$ and $w' \in (a+b)^n$. By induction $w' \in \alpha$. But now, by 2) or 3) respectively, $w_1w' \in \alpha$. Hence $w \in \alpha$, but as $w$ was arbitrary, $(a+b)^{n+1}\subseteq \alpha$.