I have the following problem in an assignment in my introduction to automata and formal languages course:
Prove that $L^2 \subseteq L$ if and only if $L = L^+$
But this problem highlights some ambiguity I have regarding languages:
I know that given any alphabet $\sum$, I can create the empty string $\lambda$. But, does every language contain $\lambda$? As far as I understand it, it's perfectly acceptable to define a language without $\lambda$, in which case the "if and only iff" clause seems to break:
Say I define a Language with alphabet {$a,b$}. so:
$L = L^+ = \{ a , b , aa , ab , ba , bb , aaa , aab ...\}$
$L^2 = \{aa, ab, ba, bb, aaa, ...\}$
In which case, obviously, if $L^2 \subseteq L$
But, this also works with:
$L = L^* = \{\lambda, a , b , aa , ab , ba , bb , aaa , aab ...\}$
$L^2 = \{a,b, aa, ab, ba, bb, aaa, ...\}$
Here, again, $L^2 \subseteq L$
so, why the if and only if?
Your second example is not a counterexample to the "only if". In that case, $L$, $L^+$, $L^*$ and $\{a,b\}^*$ are all equal.
Claim. Let $L$ be a language. Then $L^2 \subseteq L$ if and only if $L = L^+$.
Proof. ($\Leftarrow$) Suppose that $L = L^+$. Then $L^2 \subseteq L$, since $L^2 \subseteq L^+$.
($\Rightarrow$) Suppose that $L^2 \subseteq L$. We prove by induction that $L^n \subseteq L$ for all $n \geq 1$. For $n = 1$, this is trivial; for $n = 2$, this is the assumption. So, let $n \geq 2$ and assume that $L^n \subseteq L$. Then \begin{align*} L^{n+1} & = L L^n \\ & \subseteq L^2 \text{ (using the induction hypothesis)} \\ & \subseteq L \text{ (by assumption).} \end{align*} So, for all $n \geq 1$, $L^n \subseteq L$ and therefore $L^+ = \bigcup_{n\geq 1}L^n \subseteq L$. Since also $L \subseteq L^+$, it follows that $L = L^+$.