# What is the difference between the set containing the empty string and the set containing nothing at all?

It's an exercise question from chapter 0 of Michael Sipser's book Introduction to the Theory of Computation.

e. The set containing the empty string
f. The set containing nothing at all

I guess the empty string is still something, which is not nothing. Would this be the difference?

• An empty string is a string. $\{s\}\ne\emptyset$. For the same reason that $\{\emptyset\}\ne\emptyset$. Jan 10 at 15:43
• I feel like there's some sort of CS koan awaiting discovery here. "The set containing the empty string contains the empty string." Jan 10 at 21:22

Yes, that's it.

One important difference could be seen using concatenation: let $$L$$ be any nonempty language.

Then $$\{\varepsilon\}L = L$$, but $$\emptyset L = \emptyset$$. Clearly those are different.

The difference is essentially structural.

In the case of the set containing the empty string, the set has a length of 1.

In the case of the set containing nothing, the set has a length of 0.

A string is typically conceived as a container of characters (as opposed to say an int, which is not typically conceived as a container of numbers or bits).

The string, as a container, can be present, but contain no characters - the string can have length 0, even though the set which contains the string has length 1.

In this way, there are two levels of containment when talking of sets containing strings, and what the set contains is not to be conflated with what the string contains.

This is distinct from "nothing" in the set, which is where even the string-as-a-container is absent from the set.

It might have been slightly clearer if Sipser had phrased himself as:

e. The set containing the empty string.

f. The set that doesn't contain anything.

• Sets don't have a length, rather a size. Jan 10 at 19:38
• @CalebStanford, I assume the words are synonymous? In computer science (which is the only context where a "string" has the relevant meaning), we don't really have "sets", we have arrays. Jan 10 at 19:54
• I don't mind if you use them synonymously, but "size" is less ambiguous as it distinguishes between sets and strings. Your latter statement is not quite true. Sets are an abstract data type. They can be implemented, e.g. as hashtables, binary trees, or (inefficiently) as arrays. Jan 10 at 20:05

A general way to check if two sets are equal: two sets $$S_1$$ and $$S_2$$ are equal if (i) all of the elements in $$S_1$$ are in $$S_2$$, and (ii) all of the elements in $$S_2$$ are in $$S_1$$. This property is called "extensionality".

In your case, let's apply the definition. Our first set, $$S_1$$ is the set containing the empty string $$\epsilon$$. Our second set, $$S_2$$ is the empty set. To check property (i), we look at all elements in $$S_1$$: that's just one element, $$\epsilon$$. But $$\epsilon$$ is not in $$S_2$$, since $$S_2$$ is the empty set (and thus contains no elements). So the two sets are not equal.

• Implicitly, you are asserting that the "empty string" is an element in the set, but you are not explaining why a string consisting of nothing should be regarded as something, or why the distinction (between the set containing the empty string, and the empty set) should or must exist. Jan 10 at 19:58
• @Steve Note that this is precisely the definition of "the set containing the empty string", that it contains the empty string. I agree and the other answers cover that point well; this answer offers another perspective. Jan 10 at 20:09

Think of the set containing the empty string as one, and the empty set as zero.

A Kleene algebra is essentially an idempotent semi-ring, plus the Kleene closure operator. Ignoring the Kleene closure (a.k.a. Kleene star) operator, the ordered "multiplication" corresponds to string concatenation and "addition" corresponds to set union. Most of the axioms should look very familiar:

$$\begin{eqnarray*} a + (b + c) & = & (a + b) + c \\ a \cdot (b \cdot c) & = & (a \cdot b) \cdot c \\ a + b & = & b + a \\ a\cdot (b + c) & = & a \cdot b + a \cdot c \\ (b + c) \cdot a & = & b \cdot a + c \cdot a \\ 0 + a & = & a + 0 = a \\ 1 \cdot a & = & a \cdot 1 = a \\ 0 \cdot a & = & a \cdot 0 = 0 \end{eqnarray*}$$

Those last three show the difference between the empty set ($$0$$) and the set containing the empty string ($$1$$): the empty set is the identity for set union, and the empty string is the identity for string concatenation. The empty set also annihilates string concatenation.

That's a lot of terminology, but I think it's much easier to understand if you write it in this algebraic notation, rather than in regular expression notation:

$$\begin{eqnarray*} \emptyset \,|\,a & = & a\,|\,\emptyset = a \\ \epsilon a & = & a \epsilon = a \\ \emptyset a & = & a \emptyset = \emptyset \end{eqnarray*}$$

Just for completeness, the thing that makes addition correspond to set union is that it is idempotent:

$$a + a = a$$

All of the other axioms of a Kleene algebra define the Kleene closure operator $${}^*$$, which is important, but isn't relevant to your question. See the link above if you're interested.

It might be clearer to ask yourself whether a set containing an empty set is the same as an empty set. Russell and Whitehead say, "No."

• Russell is not a reliable source about logic. "[In] Principia Mathematica [...] the syntax is never precisely described, and the axioms and rules of inference are presented in a way that mixes together the syntax with its intended meaning. The formalism appears to be inextricably tied to its informal interpretation. [...] it is this last feature of Russell’s logic that seems to have led to some misunderstandings on his part." Jan 11 at 3:10
• Russell himself admitted as much in a postscript to a 1943 article by Godel: "His great ability, as shown in his previous work, makes me think it highly probable that many of his criticisms of me are justified. The writing of Principia Mathematica was completed thirty-three years ago, and obviously, in view of subsequent advances in the subject, it needs amending in various ways. [...] I must therefore ask the reader to give Dr. Gödel’s work the attention that it deserves, and to form his own critical judgment on it." Jan 11 at 3:10
• @user21820, this was a reference to W&R using some variant of naive set theory to derive the properties of arithmetic. Whatever criticism may be made of their symbology or derivation of logic, the cardinality of the two sets does differ by 1. Jan 12 at 4:54
• If you want to state a fact, state a fact. Don't cite a dubious source unless you want your own credibility to be doubted. Jan 12 at 7:24