I have this question in my Theoretical Computer Science class on the topic of Automata and Formal Languages.
$$ λ ∈ L \iff L^2 ⊆ L^3$$
I thought of showing it by proving the contrapositive but I was only able to complete half of the proof (since it is a bidirectional proof) and on top of that I am not even sure it is correctly written in a formal form.
I wanted to prove that if
$$λ ∉ L \implies L^2 \nsubseteq L^3$$
But since it is a bidirectional proof, I must also show that
$$L^2 \nsubseteq L^3 \implies λ ∉ L$$
right?
This is what I have so far:
1) $λ ∉ L \implies L^2 \nsubseteq L^3$
$ \lambda \notin L \implies \forall w \in L, n_0(w) \geq 1$
$ L^2 = L * L \implies \forall w_2 \in L^2, n_0(w_2) \geq 2 $
$ L^3 = L * L * L \implies \forall w_3 \in L^3, n_0(w_3) \geq 3 $
$\forall w_3 \in L^3 \land \forall w_2 \in L^2, n_0(w_3) > n_0(w_2)$
$ \therefore L^2 \nsubseteq L^3$
So first of all, is this correct?
Secondly, how would I go about showing the second part of my proof where
$$L^2 \nsubseteq L^3 \implies λ ∉ L$$
Thank you!
As Orest mentioned in the comments, $$\forall w_3 \in L^3 \land \forall w_2 \in L^2, n_0(w_3) > n_0(w_2)$$ is false. To give a correct proof of this direction, instead take $w_1 \in L$ to be a word of minimal length and show the concatenation $w_1w_1$ is in $L^2$ but not in $L^3$
For the other direction, assume $\lambda \in L$ and concatenate any word in $L^2$ with $\lambda$ to find a word in $L^3.$