Is the empty set in every language?

9.6k Views Asked by At

I know that in set theory, $\forall A:\emptyset \subseteq A$

My question is, does this apply to formal languages? In my mind, formal languages are just a set of strings that are over some set of letters, which can be looked at as a set of strings with size 1. If I look at it strictly from the formal language side, all non-empty alphabets cannot have an "empty" letter and there would not? be an empty set in every language. Note I am not looking at the set containing only the empty string, which I understand is not in every language.

However, would a predicate $P(w)=w\in AB \iff \exists a:\exists b:a \in A \land b \in B \land ab=w$ that tests the membership of string $w$ in the concatenation of two finite (non empty) formal languages ($A,B$) always be true if there is no string $w$ at all ergo $w$ is the empty set? I think but am not sure if it is just vacuously true that if there is no string at all, $P$ would be true by the fact that $\forall A:\emptyset \subseteq A$ is vacuously true, so for any set product $\forall A:\forall B:\emptyset \subseteq AB$ would also be vacuously true

Perhaps my confusion is due to misunderstanding the empty set with regards to language theory.

2

There are 2 best solutions below

4
On BEST ANSWER

Languages don't contain sets, they contain strings, It's true that for any language $L$, we have that the empty set is a subset of $L$, i.e. $\emptyset \subseteq L$, since this is true of any set. So if this is what you're asking, then yes, that is trivially true.

However, if you're asking whether $\emptyset \in L$ for every language, then this question doesn't really make sense, since languages don't contain sets. The analogous notion is the empty string $\varepsilon$, so it makes sense to ask whether $\varepsilon \in L$ for any language $L$, but the answer is of course no.

1
On

If you dissect the right hand side, $\exists a \in A \colon a \in A$ is false if $A = \emptyset$, so $P(\omega)$ isn't true in such a case. Unless I don't understand at all what you are asking...