Concatenation of language to itself zero times

Question

I was solving this question:

Which of the following statement(s) is/are false?

1. $L^0=\{\epsilon\}$
2. $|L^0|=0$

The answer given was None. That is, none of these statements are false and both are true. However, I feel both are wrong. I feel

$L^1=L$ and
$L^0=\phi$

Also

$|L^0|=|\phi|=0$

Am I wrong with this?

Answer 1

$L^0$ is defined to be $\{\varepsilon\}$. (Since a string formed by concatenating zero strings together is the empty string).

This gives the answer to the first question - which is correct.

Now, $\{\varepsilon\}$ contains exactly one string - which is the empty string. Therefore: $|\{\varepsilon\}|=1$. (The given answer is wrong).

Note that $|\{\varepsilon\}|=1\ne0=|\varepsilon|$. Also, note that $\{\varepsilon\} \ne \emptyset$.

Answer 2

Mickey's answer is completely correct. But I'd like to explain a bit more thoroughly why that's the correct answer.

At first glance, it would make sense to have $A^0 = \varnothing$: that is, the empty set. But in practice, the special cases of this operation are defined in a way that lets useful theorems hold, and letting $A^0 = \varnothing$ doesn't prove as useful as letting $A^0 = \{\varepsilon\}$.

In particular, consider the concatenation operation on languages. If we have languages $A$ and $B$, then $AB$ is the language "any string from $A$ followed by any string from $B$". It follows that you can't concatenate anything with the truly empty language $\varnothing$: $A \varnothing = \varnothing$, and $\varnothing A = \varnothing$.

In the general case, we know that $A^x A^y = A^{x+y}$. For example, $A^2 A^3 = A^5$. And this is a useful rule for various proofs. But if we say that $A^0 = \varnothing$, then this breaks down: $A^2 A^0 = A^2 \varnothing = \varnothing$ rather than $A^2$.

If instead we define $A^0 = \{ \varepsilon \}$, then the rule still holds: $A^2 A^0 = A^{2+0} = A^2$. So we choose to use this definition, because it makes our system of rules more useful in general.

There are other mathematical reasons why this is more elegant. For example, $|A^n|$ can be thought of as "the number of ways to choose $n$ elements from $A$, with replacement", and there's exactly one way to choose zero elements from any set: choosing none of them at all.

But all of these different ways boil down to: we choose to use this definition, because it makes things work out nicely. Like with anything else in mathematics, it's a conscious choice to do it this way, rather than any universal law of nature; it's just a conscious choice that leads to interesting results, and thus a choice we consider useful.

Answer 3

Here is yet another answer complementing to already completely correct answers. As chi and Draconis state, the key property is $L^{m+n}=L^m L^n$. As Mickey states but does not explain why, this leads to $L^0=\{\epsilon\}$. Draconis' answer apparently makes it too easy to read as an "arbitrary" choice, or even that it is an artificial choice replacing some other, "more natural" choice.¹

Here's a somewhat more general perspective. Virtually always when we use the notation $x^n$ where $n$ is a natural number, we intend $x^{(-)}$ to be a monoid homomorphism from the natural numbers equipped with the additive structure. This means $x$ itself must be an element of some specified monoid. Usually, this is implicitly specified by being the one we multiplicative notation for for elements of the relevant set. The unit and operation of the additive monoid on natural numbers are $0$ and $+$. For $x^{(-)}$ to be a monoid homomorphism means $x^0=u$ and $x^{m+n} = x^m \star x^n$ where $u$ and $\star$ are the unit and operation of the specified monoid on the set containing $x$.

Now the set of finite sequences(or lists) on an alphabet $\Sigma$, often written $\Sigma^*$, is actually the free monoid² on $\Sigma$. The unit is the empty sequence $\epsilon$ and the operation is concatenation which I'll write as $\frown$ to have it be explicit. This leads to exactly the behavior you describe on the comment to the question. That is, for words $a$, $a^{m+n}=a^m\frown a^n$ and $a^0=\epsilon$. Next, given any monoid on a set $X$, we can define a new monoid on the powerset of $X$ (those elements are subsets of $X$). If $u$ and $\star$ are the unit and operation of a given monoid on $X$, then $\{u\}$ is the unit for the operation (which I'll call $\dot\star$), $S\ \dot\star\ T =\{s\star t\mid s\in S \land t \in T\}$. (Prove this.) This is, of course, exactly the monoid structure we're using when we talk about concatenating languages (i.e. subsets of $\Sigma^*$). This immediately leads to $L^0=\{\epsilon\}$ and $L^{m+n}=L^m\ \dot\frown\ L^n$.

There are many other monoid structures we can place on the power set of $X$. For example, for any set $X$ which need not be a monoid. We have the following two monoids on the power set of $X$: 1) unit $X$ and operation $\cap$, 2) unit $\varnothing$ and operation $\cup$. (Prove that these are monoids.) If you wanted $L_1 L_2$ to mean $L_1\cup L_2$, then we'd have $L^0 = \varnothing$ and $L^{m+n}=L^m\cup L^n$, but $L_1 L_2$ usually means $L_1\ \dot\frown\ L_2$ as above for which the unit, and thus $L^0$, is $\{\epsilon\}$. Choosing $L^0$ to be $\varnothing$ while still keeping $L_1 L_2$ as $L_1\ \dot\frown\ L_2$ means $L^{(-)}$ is no longer a monoid homomorphism. This will lead to all kinds of unexpected behavior, clumsy special-cases, and missed connections.

¹ Draconis' point is more that definitions can't be wrong. One is free to define things however they like no matter how clumsy, awkward, and confusing the result may be. However, some definitions are better than others.

² Formal language theory is very much a study of various monoids and operations upon monoids. It's pretty close to just being "Monoid Theory".