Here I'm having some confusion on what exactly is the empty string $\epsilon$. I'm going to list some prerequisite definitions I have surrounding the string, so please correct them as necessary. I bolded what I felt were keys to understanding the empty string.
Other than that, these definitions (minus the parenthetical label) are verbatim from Introduction to the Theory of Computation by Michael Sipser.
(String) A string over an alphabet is a finite sequence of symbols from that alphabet.
(Alphabet) Any nonempty finite set.
(Finite Sequence) A sequence of objects is a list of these objects in some order.
(String Length) If $w$ is a string over $\Sigma$, the length of $w$, written $|w|$, is the number of symbols that it contains.
(Empty String) The string of length zero is called the empty string.
Note: Later on, for NFA's, Sipser defines their modified alphabet as some $\Sigma \cup \epsilon$.
Based on the above definitions, the empty string—being a string—is a sequence of symbols from an alphabet. Since it has length zero, it must be the empty sequence. Furthermore, since it has length zero, it must have zero symbols from any alphabet. Since it has no symbols from any alphabet it violates the definition of a string. Therefore, the empty string is not a string over any alphabet.
Note that Sipser's alphabet definition does not include the empty set.
I was informed by Robert Israel a few days ago that my logic above is wrong. I just don't see where.
Is the actual precise definition of empty string: the seqence of zero symbols from any nonempty alphabet? Are we taking as an axiom that we can take zero elements from a sequence? And if so, why does Sipser include the union of an alphabet with the empty string in his definition of NFA's? What is the difference between the empty string's relationship to an alphabet compared to it's role as member of a set like $\Sigma \cup \epsilon\, $?
Best Answer
Your mistake is a common one in mathematics, of thinking "an x of ys" has to contain at least one y, when what we really mean is it can't contain anything else. In other words, you thought the definition used an existential quantifier, but it actually uses a universal one. Let's try formalising this (without any MathJax, because quotation environments don't like it):
"All" does not imply "some"; when there are no objects to be either examples or counterexamples, "all" is vacuously satisfied while "some" is violated. This may be surprising the first time you learn it, but in the long term it makes definitions, theorems etc. much easier, because you avoid a need to work around edge cases. (It also means you can get by with just one quantifier if you're prepared to negate all over the place, e.g. $\forall x\phi(x)$ means $\neg\exists x\neg\phi(x)$.) For example, there are $|\Sigma|^l$ length-$l$ strings on the above account for any non-negative integer $l$; $l=0$ isn't an exception.