1
$\begingroup$

Why is $\emptyset$ CONCAT $S = \emptyset$?

The concatenation operation is defined:

If $A$ and $B$ are sets, we define $A\circ B=\{ab:a\in A\text{ and }b\in B\}$

If we concat something to an empty set, wouldn't it just equal to set itself?

If we think of an empty set as an empty string, then empty string + full string = full string?

$\endgroup$
  • 1
    $\begingroup$ Is it a multiplication in the definition of your concatenation? Is the operation of multiplication defined for $S$? $\endgroup$ – Mickey Jul 3 '17 at 20:26
  • 1
    $\begingroup$ If $x \in \emptyset \circ S$, this means there exists $a \in \emptyset$ and $b \in S$ such that $x = ab$. The problem is that there's no elements in $\emptyset$, hence no $a$ and consequently no $x \in \emptyset \circ S$. $\endgroup$ – Weaam Jul 3 '17 at 20:31
  • $\begingroup$ The emptyset is different than the set containing the emptystring. There exists no choice of $a\in \emptyset$ for which an element $ab\in \emptyset\circ B$ can be written. $\endgroup$ – JMoravitz Jul 3 '17 at 20:31
  • $\begingroup$ Think of the size of the sets. When $A,B \neq \emptyset$, $|A\circ B| = |A||B|$, for that to be true when $A$ (or $B$) is empty... $\endgroup$ – Henrik - stop hurting Monica Jul 3 '17 at 20:37
  • $\begingroup$ @Henrik not quite... instead $|A\circ B|\leq |A||B|$. It is possible that a concatenation has multiple representations. The conclusion still follows though. $\endgroup$ – JMoravitz Jul 3 '17 at 20:39
3
$\begingroup$

Quantifiers can be omitted provided it is clear which ones are being used. For instance, a notation such as $\{ab:a\in B\text{ and }b\in B\}$ is universally read as $$\{x\,\mid\, \exists a,\exists b, (a\in A\wedge b\in B\wedge x=ab)\}$$

In the case $A=\emptyset$, every predicate in the form $\exists a, (a\in A\wedge\mathfrak P)$ is automatically false. Therefore no $x$ satisfies the defining condition and $\emptyset\circ B=\emptyset$.

$\endgroup$
  • 1
    $\begingroup$ Not universally; one can also read this as related to the axiom of replacement rather than the axiom of subsets: that $a \in A, b \in B$ specifies the domain of the variables, and $ab$ is the function you are applying to elements of the domain. It amounts to the same end, of course, but it is a different way of thinking about how to get there. $\endgroup$ – user14972 Jul 3 '17 at 20:43
2
$\begingroup$

If $x \in \varnothing \circ S$, then there are $a \in \varnothing$ and $b \in S$ such that $x = ab$.

But this is impossible, since there aren't any $a \in \varnothing$ at all!

$\endgroup$
1
$\begingroup$

$\emptyset \ast A = \emptyset$ while $\{\varepsilon\} \ast A = A$, so one is a sort of $0$ and the other a sort of $1$... for the concatenation operation $\ast$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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