# Is the Kleene star of an intersection contained in the intersection of Kleene stars?

I need to find if given two formal languages $L_1$ and $L_2$ $$(L_1 \cap L_2)^*\subseteq (L_1^* \cap L_2^*)$$ I think that it's true since this can be rewritten as $$\bigcup^\infty_{i=0}(L_1 \cap L_2)^i \subseteq (\bigcup^\infty_{i=0}L_1^i \cap \bigcup^\infty_{i=0}L_2^i)$$ and in general, $$(A \cap B) \cup (C \cap D) \subseteq (A \cup C) \cap (B \cup D)$$ I may be wrong since it has been a long time since i have done anything with set theory, and this is taken as given. Thanks

• If L1 just accepts "a", and L2 just accepts "aa", I believe that's a counterexample – Millie Smith Feb 17 '16 at 16:11
• No, $\subseteq$ relation is satisfied for your counter example. – Shreesh Feb 17 '16 at 16:28
• Ah, yes, missed that. – Millie Smith Feb 17 '16 at 16:29

The correct proof is as follows: $L_1 \cap L_2 \subseteq L_1$ and therefore $(L_1 \cap L_2)^* \subseteq L_1^*$. (argument: if $A \subseteq B$ then $A^* \subseteq B^*$). Similarly $(L_1 \cap L_2)^* \subseteq L_2^*$.
Therefore $(L_1 \cap L_2)^* \subseteq (L_1^* \cap L_2^*)$ (argument: if $A \subseteq B$ and $A \subseteq C$ then $A \subseteq B \cap C$).
Anyway you can not write $(A \cap B)^i \cup (C \cap D)^j = (A^i \cup C^j) \cap (B^i \cup D^j)$.
Correct relation is: $(A \cap B) \cup (C \cap D) = (A \cup C) \cap (B \cup D) \cap (A \cup D) \cap (B \cup C)$
However $\bigcup^\infty_{i=0}(L_1 \cap L_2)^i \subseteq (\bigcup^\infty_{i=0}L_1^i \cap \bigcup^\infty_{i=0}L_2^i)$ is correct because
$\bigcup^\infty_{i=0}(L_1 \cap L_2)^i \subseteq \bigcup^\infty_{i=0}L_1^i$ and $\bigcup^\infty_{i=0}(L_1 \cap L_2)^i \subseteq \bigcup^\infty_{i=0}L_2^i$.