# Proving $S=SL\implies S=\emptyset$

Let $$L\subseteq \Sigma^*$$ such that $$\{\epsilon\}\not\in L$$. Then for any $$S\subseteq \Sigma^*, S=SL\implies S=\emptyset$$.

So we suppose $$S=SL$$ and $$S\ne\emptyset$$. Then $$\exists w\in S$$ such that $$0\le|w|\le |v|$$ for some $$v\in S$$. Now $$|w|\ne 0$$, since $$|w|=0\implies\{\epsilon\}=w\in S=SL\implies \{\epsilon\}=xy$$ for some $$x\in S$$ and $$y\in L\implies x=y=\{\epsilon\}\in L$$ which contradicts that $$\{\epsilon\}\not\in L$$.
Thus $$w\ne\{\epsilon\}$$ and $$\{\epsilon\}\not\in S$$. So we have
\begin{align} w \in S &\implies w\in SL\\ &\implies w=sl\;\text{for some}\; s\in S\; \text{and}\; l\in L\\ &\implies |w|=|s|+|l| \end{align}
Here I'm stuck now. I think if I can show that $$|l|=0$$, then we can arrive at a contradiction.

You should consider (one of) the word $$w$$ of minimal length in $$S$$, and show that for this word in particular, you can reach the conclusion that $$|l| = 0$$.
• So taking $|w|=1$, I can say that either $|s|=0$ or $|l|=0$. But $|s|=0$ is impossible, since $\{\epsilon\}\not\in S$ and hence $|l|=0$, a contradiction. Am I going right? But there is no guarantee that $|w|=1$. – Manjoy Das May 26 at 20:49
• No need to do so much cases. Take $|w| = \min\{|u|, u\in S\}$. Then $w = sl$, but $s\in S$, so $|s| \geq |w|$, but we also have $|s| \leq |w|$ (since $w = sl$). – Nathaniel May 26 at 21:10
• This leads to $|l|=1$. I am not getting $|l|=0$. – Manjoy Das May 26 at 21:13
• No no, this leads to $|l| = 0$, since $|w| = |s|$. – Nathaniel May 26 at 21:15