Kleene Star operation proofs

Question

Given are A and B which are subsets of {0,1}$^{*}$.

I am trying to prove the following statements. Below are my ideas.

1. A$^{+}$ $⊆$ A$^{*}$

2. (A)$^{*}$ $\cap$ (B)$^{*} ⊆$(A $\cap$ B)$^{*}$

   1. I think the statement is true as A$^{+}$ is by definition A* without the the empty word thus being a subset. Is this correct? How can I formally prove this?

   2. Intuitively, I'd say this is false, however, I cannot formally justify it.

Please help me prove the above statements. Thanks in advance!

Answer 1

1. You're right, this follows from the definition. We have $$A^*=\bigcup_{i=0}^{\infty} A^n$$ $$A^+=\bigcup_{i=1}^{\infty} A^n$$ where $A^n$ is a concatenation of n words in $A$. We can conclude from there that $A*=A^+ \cup A^0$ and therefore $A^+ \subseteq A^*$

2. Again you're right, this statement is not true. You only need to find one counterexample. Take $A=\{0\}$ and $B=\{00\}$. Then we have $A^*=\{0^n|n \in \mathbb{N}\}$ and $B^*=\{0^{2n}|n \in \mathbb{N}\}$ and $A^*\cap B^* = B$. However, $A \cap B = \emptyset$ and therefore $(A \cap B)^*=\{\varepsilon\}$. Hence $(A \cap B)^*\neq A^*\cap B^*$.