I am having problems with this question can someone please help? If $L_1 \subseteq L_2$ then $\min\{|x| : x \in L_1\} \ge \min\{|y| : y \in L_2\}$


I assume $L_{1,2}$ are finite; or looser, we have minima existing in both $L_{1,2}$ , because the "min" does not generally apply to infinite sets.

It's usual to think that inf of empty sets to be $+\infty$, thus if $L_1 =\emptyset$, or both are $\emptyset$, the inequality holds. (See discussion at Infimum and supremum of the empty set). But esp. for you question, you are already taking min of sets, I would assume the min of those sets exist (see my assumption in first paragraph).

In the case both are non-empty:

If $L_1 \subseteq L_2$ then $\forall x\in L_1$, we have $x\in L_2$.

Let $|x_0| = \min\{|x| : x \in L_1\}, x_0\in L_1$, then $x_0 \in L_2$. Thus $|x_0| \ge \min\{|y| : y \in L_2\}$.

We are done.

  • $\begingroup$ Instead if finiteness it is enough to assume the existence of both minima. $\endgroup$ – szw1710 May 13 '17 at 18:45
  • $\begingroup$ @szw1710 Yea, that could be a wider assumption, updated. $\endgroup$ – Yujie Zha May 13 '17 at 18:47
  • $\begingroup$ Let L1 and L2 be nonempty languages. $\endgroup$ – Benny B. Downs May 13 '17 at 18:49
  • $\begingroup$ @BennyB.Downs yep, I've edited the answer for the case of empty sets $\endgroup$ – Yujie Zha May 13 '17 at 18:55

Not the answer you're looking for? Browse other questions tagged or ask your own question.