# Understanding concatenating the empty set to any set.

I know that concatenating the empty set to any set yields the empty set. So, $A \circ \varnothing = \varnothing$. Here $A$ is a set of strings and the concatenation ($\circ$) of two sets of strings, $X$ and $Y$ is the set consisting of all strings of the form $xy$ where $x\in X$ and $y \in Y$. (You may want to take a look at page 65, Example 1.53 of Introduction to the Theory of Computation by Michael Sipser). However, I get somewhat puzzled when I try to intuitively understand this.

A wrong line of thinking will make one to ask, "If we concatenate $A$ with $\varnothing$, should not it still be $A$?"

Well, one way force myself to understand the correct answer, may be, to say that, since I am concatenating with an empty set, actually I will not be able to carry out the concatenation. The concatenation will not exist at all.

I am asking for help from experienced users to provide hints and real life examples which will help one to modify the thinking process and help one better to really understand the correct answer. I am putting more stress on real life examples.

I need to understand this. I am not happy simply memorizing the correct answer.

• Normally one concatenates functions or sequences, neither of which appears to apply here; exactly what is your concatenation operation? – Brian M. Scott Aug 21 '13 at 17:18
• I can’t, since I don’t own the book, and page $65$ isn’t included in the Amazon preview. However, there’s enough information there for me to see the relevant context, and I’ve answered the question on that basis. – Brian M. Scott Aug 21 '13 at 17:40
• Concatenate empty set to a sequence. Please see page 65, Example 1.53 of Introduction to the Theory of Computation by Michael Sipser. It concatenates the empty set to a sequence of characters. – Masroor Aug 21 '13 at 17:40
• I doubt it: I strongly suspect that it concatenates the empty set to a set of strings. – Brian M. Scott Aug 21 '13 at 17:43
• You might consider editing your post to specify the context, like this: "Edit Here $A$ is a set of strings and the concatenation of two sets of strings, $X, Y$ is the set consisting of all strings of the form $xy$ where $x\in X$ and $y\in Y$", perhaps with a reference to Sipser. The downvotes likely came from users who took a quick look at your post and didn't get the backstory. Remember that the vast majority of users here aren't CS theorists. – Rick Decker Aug 22 '13 at 16:31

## 4 Answers

It turns out from the comments that the context is regular sets. If $A$ and $B$ are sets, we define $A\circ B=\{ab:a\in A\text{ and }b\in B\}$. If $B=\varnothing$, there are no objects $b\in B$, so there are no objects $ab$ such that $a\in A$ and $b\in B$; thus, $A\circ\varnothing=\varnothing$.

• what about concatenating with epsilon ? say A={a,b} what is A o epsilon ? – Subham Tripathi Oct 30 '15 at 15:54
• @Subham: $A$ is a set of strings, and $\epsilon$ is a single string, so they’re not the same kind of object. If you mean $A\circ\{\epsilon\}$, however, that’s $\{a\epsilon,b\epsilon\}=\{a,b\}=A$. Similarly, $A\circ\{\epsilon\}=A$ for any set $A$ of strings. – Brian M. Scott Oct 30 '15 at 19:17
• @BrianM.Scott what about ∅*? Will it be ∅ or ϵ? Can you please elaborate this as well. – prajul Jan 31 at 16:00
• @prajul: $\varnothing^*=\{\epsilon\}$. – Brian M. Scott Jan 31 at 18:35

The wrong line of thinking is almost correct, in the following way. Let $\epsilon$ be the empty string. For any string $a$, we have $a\epsilon=a$. Let $\{\epsilon\}$ be the set containing exactly one element, namely the empty string. Then for any set of strings $A$, we have $A\circ\{\epsilon\}=A$.

The real issue, then, is confusing $\{\epsilon\}$ with $\varnothing$. The former is a set containing one string; the latter is a set containing zero strings.

(One potential trap is that some formalisms might identify $\epsilon=\varnothing$. Then we have to distinguish between $\{\varnothing\}$ and $\varnothing$. This is theoretically straightforward, but it means that you have to be careful with your notation.)

Note that there is a natural surjection from $A\times B$ onto $A\circ B$. If $B$ is empty, the product is empty and therefore the concatenation is empty.

This nice answer made me perfectly understand the issue from a mathematical point of view. I was also looking for some real life examples, as indicated in my original post, may be from a completely different domain, to make my intuitive understanding better.

Last night, one example came to my mind which I would like to share with all.

Let us use concatenation to indicate marriage between two groups of men and women.

Now, if our first set is a group of men, $M = \{M_1, M_2, M_3\}$ and the second set is a group of women, $W = \{W_1, W_2\}$, the group of possibly married couple will be the concatenated set, \begin{align*} C &= M\circ W\\ &= \{M_1,M_2,M_3\}\circ\{W_1,W_2\}\\ &=\{M_1W_1, M_1W_2, M_2W_1, M_2W_2, M_3W_1, M_3W_2\} \end{align*}

(Let us ignore here the issues like who can marry whom and multiple marriages, or should not be a couple written as ordered pair, just to keep it simple).

Now if the group of women is empty, $W = \varnothing$, there will no woman available for marriage, marriages will not happen, and the set, the group of married couple will be empty, $C = M\circ W =\varnothing$.

• Not quite: $\{M_1,M_2,M_3\}\circ\{W_1,W_2\}=\{M_1W_1, M_1W_2, M_2W_1, M_2W_2, M_3W_1, M_3W_2\}$ is the set of all possible marriages. – Chris Culter Aug 23 '13 at 0:34
• @ChrisCulter The point was to highlight that if the group of women is empty, no marriage can happen. Perhaps I will edit my post to indicate these as possible marriages. Thanks. – Masroor Aug 23 '13 at 0:49
• You can use the subset symbol to express that idea: $\{M_1W_1,M_3W_2\}\subset M\circ W$. But it's a good exercise to write out the whole set, because then you can see that the sizes of the sets are $3\times2=6$, whereas if $W=\varnothing$, we get $3\times0=0$. This works because the set of marriages is a Cartesian product. On the other hand, concatenation of sets of strings doesn't always obey a multiplication law. For example, $\{a, aa\}\circ\{a,aa\}=\{aa,aaa,aaaa\}$. – Chris Culter Aug 23 '13 at 0:52
• @ChrisCulter Again, you are right. But this real life scenario made me (at least me) clearly understand why the result of concatenation will be empty when the second set is empty. And thanks for showing why concatenation of sets of strings doesn't always obey a multiplication law. Since for the marriage example the two sets are completely disjoint, the simile will work. – Masroor Aug 23 '13 at 1:01