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.
$\endgroup$ 114 Answers
$\begingroup$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$.
$\endgroup$ 6 $\begingroup$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.)
$\endgroup$ $\begingroup$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.
$\endgroup$ $\begingroup$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$.
$\endgroup$ 4
