# Is the empty set in every language?

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.

• Can we all just call it "the empty set", please? That is completely unambiguous, where as a "null set" has several meanings, and the usual meaning is much more general than just "no elements". – Chappers Oct 4 '15 at 23:59
• @Chappers fixed – TTT Oct 5 '15 at 0:02
• Thank you, much better! :) – Chappers Oct 5 '15 at 0:03

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.
• To make sure I understand you, if $\emptyset \subseteq L$, the substitution L=AB $\emptyset \subseteq AB$ must also be true? Thanks for the answer. – TTT Oct 8 '15 at 17:22
• @rpg711 Well, yes, but I think there is still some confusion. I assume that by $AB$ you mean the language (set) of all strings of length two where the first symbol is from some alphabet $A$ and the second symbol is from alphabet $B$. Then, yes, if you can show that $L = AB$, then $\emptyset \subseteq AB$, but notice that this is also true even if $L \neq AB$. As long as $AB$ is a set (and all languages are sets of strings), we have $\emptyset \subseteq AB$. – mrp Oct 9 '15 at 12:20
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...
• Sorry, I was not clear enough in my question. A and B are some finite languages, and I would like to test the membership of the empty set in the concatenation AB so essentially, I am wondering if it follows that if for any set A, $\forall A: \emptyset \subseteq A$, then would it follow that for any two non-empty, finite languages, $\forall A: \forall B: \emptyset \subseteq AB$ – TTT Oct 5 '15 at 0:02