I tried the following induction proof:
- $\sum \neq \emptyset$
- $A,B \subseteq \sum^{*}$
- $A^{+} := \bigcup_{n\geq 1} A^n $
- $A^{n} :=$ "$n$-wise-concatenation of $A$ to itself"
- $AA := \{ab | a \in A \wedge b \in A\}$
To proof: "$A\subseteq B$ implies $A^+ \subseteq B^{+}$
a. Induction basis:
- $n=1$: $A^{1}\subseteq B^{1}=A \subseteq B. $
b. Induction step:
- Induction assumption: for a fixed $n$, $A\subseteq B$ implies $A^n \subseteq B^n$.
- Induction hypothesis: for a fixed $n$, $A\subseteq B$ implies $ A^{n+1} \subseteq B^{n+1}$.
- Proof of hypothesis: $ A^{n+1} = AA^{n}\subseteq BA^{n}= B \subseteq B B^{n}=B^{n+1}$.
Last subset-relation holds because of the induction assumption, and the one before, because of the assumption $A \subseteq B$.
Is this a correct proof for this implication? What can I improve?
Your proof says that, for every $n\in\mathbb{N}$, you have $A^n\subseteq B^n$, not more. You can't say that $A^+\subseteq B^+$, because there is no $m\in\mathbb{N}$ such that $A^m=A^+$ and $B^m=B^+$.
To finish the proof, consider some $a\in A^+$, then, there must be some $k\in\mathbb{N}$ such that $a\in A^k$. Therefore, by your proof by induction, you have that $a\in B^k\supseteq A^k$, therefore, $a\in B^+$. And this proves that $A^+\subseteq B^+$.