4
$\begingroup$

It has been asked before why $\emptyset^\star=\{\epsilon\}$. The answer boils down to $\emptyset^\star$ being defined as $$ L^\star = \bigcup_{i=0}^\infty L^i, $$ where a word in $L^i$ is the concatenation of $i$ words from $L$. So, for the empty language this leaves empty sets for all $i>0$, "but $L^0 = \{ \epsilon \}$ since $\epsilon$ is the concatenation of zero words from $L$. It doesn't matter if $L$ is empty or not, since we are choosing zero words from $L$." (quoted from the answer.)

And that's what I'm curious about: is there a good reason to say that the concatenation of zero words is $\epsilon$ even for the empty set? Can you compare it to $0^0=1$ in arithmetics (where it's just more or less arbitrary) or is there a strong logical reason for this to be true?

$\endgroup$
3
  • 2
    $\begingroup$ This is discussed in Yuval's answer there and comments on it; what more do you want? $\endgroup$
    – Raphael
    Commented Jul 2, 2016 at 15:56
  • $\begingroup$ You're right, I didn't see the second answer - sorry! $\endgroup$ Commented Jul 2, 2016 at 16:30
  • $\begingroup$ The misconception starts at calling 0^0=1 arbitrary. a product with zero factors is logically the neutral element of multiplication, nothing arbitrary about that. $\endgroup$
    – peter
    Commented Dec 10, 2021 at 10:58

1 Answer 1

6
$\begingroup$

Strings with concatenation and the empty word form a monoid.

In monoids, the empty concatenation/sum/product yields the neutral element, i.e. $\varepsilon$/0/1.

An empty concatenation does not need any words to start with, so $\emptyset^0 = \{\varepsilon\}$.

Intuitively, if you specialize

$L^n$ is the set of all words obtained by $n$-fold concatenation of words in $L$

to

$L^0$ is the set of all words obtained by zero concatenations (of words in $L$)

you can just stop reading after "concatenations" and the contents of $L$ do not matter; we don't even need it to be non-empty.

$\endgroup$
4
  • 1
    $\begingroup$ N.B. the only reason this argument does not apply with equal force to justify $0^0 = 1$ is that exponentiation is not a monoid. $\endgroup$
    – zwol
    Commented Jul 2, 2016 at 21:29
  • 2
    $\begingroup$ @zwol: I don't think you've quite thought that through. Neither $L^n$ nor $m^n$ is a monoid operation. Raphael is using $L^n$ to denote repeated application of a monoid operation (namely concatenation); if you use $m^n$ the analogous way (to denote repeated multiplication), then $0^0 = 1$ is actually correct. The reason this argument doesn't apply to $0^0$ in general is that $x^y$ doesn't always denote repeated multiplication; $0^{0.1}$ (for example) has no monoid-related interpretation, and $\lim\limits_{x\to 0}0^x \ne 1$. $\endgroup$
    – ruakh
    Commented Jul 2, 2016 at 22:54
  • $\begingroup$ @ruakh where exactly does the continuity of any (arbitrary) function enter into the definition of 0^0? $\endgroup$
    – peter
    Commented Dec 10, 2021 at 11:03
  • $\begingroup$ @peter: I notice that you write of "the definition of 0^0", and from your recent comment to the OP, you seem to believe that the definition of 0^0 is "a product with zero factors". If you start with that definition, and refuse to brook any suggestion that that definition might have limitations or that other definitions might be considered, then -- don't worry, continuity doesn't enter into it at all, and you can continue to live happily in your angry bubble. :-) $\endgroup$
    – ruakh
    Commented Dec 10, 2021 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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