0

I've clicked through about a million questions on here and and on CS Stack Exchange and not yet come across an unequivocal "yes" or "no" to the following:

Is the empty string the same thing as the empty set?

Sipser ("Theory of Computation") defines a string as any tuple with elements from a given alphabet (the alphabet can be any nonempty finite set). As far as I can tell, it follows that this question is equivalent to "is the zero tuple the same as the empty set"? I am not sure about this in turn because the set-theoretic definition of tuple has some nested sets, so I could at least imagine the zero tuple being defined as the set containing the empty set or something like that.

EE18
  • 1,211
  • 1
    With the stated definition, and with standard definitions of $k$-tuples as being a function from $[k]$ to whatever codomain you were interested (the alphabet in this case)... yes, the empty string is equal as a set to the empty set. There can be specific nuance though with certain ways of defining things where it is not identically equal, such as if you were to define a function from $A$ to $B$ not simply as any old subset of $A\times B$ satisfying certain restrictions, but as a triple $(f,A,B)$ where the domain and codomain are "not forgotten" and are an intrinsic property of it... – JMoravitz Feb 10 '24 at 16:33
  • 2
    The punchline though is that it shouldn't matter. When we want them to be treated as "the same" then we can adjust definitions in such a way that they are in fact the same. When we want them to be treated as "different" we can adjust definitions in such a way that they are in fact different. There are many available definitions... and which definitions we officially use vary based on what it is we are trying to do and what set of definitions will be most useful for us to solve whatever problem it is we are working on. – JMoravitz Feb 10 '24 at 16:35
  • 1
    The problems and answers come first. The definitions are written in such a way to let us get those answers. – JMoravitz Feb 10 '24 at 16:36
  • I consider the empty string a character. It has many properties similar to the empty set but it's a string so it's ordered and sets aren't. It can be encoded as the empty set but I prefer to keep strings separate from sets as mathematical objects. – CyclotomicField Feb 10 '24 at 16:40
  • @CyclotomicField By "character" do you mean "element of the alphabet under consideration"? I am familiar with "symbol" for that so I wanted to check. – EE18 Feb 10 '24 at 16:50
  • Understood, thank you! @JMoravitz Happy to accept an answer with exactly that written if you'd like :) – EE18 Feb 10 '24 at 16:51
  • @EE18 yes by a character I mean an element of an alphabet. – CyclotomicField Feb 10 '24 at 17:17

1 Answers1

2

As JMoravitz describes, the short answer is it can, but it doesn't matter as long as your definition of empty string has the expected properties, such as being the identity under concatenation. If it's desirable for a string or tuple to potentially be non-finite and have trivial projection functions, as is common in computer science, then a convenient definition is that a $k$-tuple over $S$ be a function $\mathbb{N}_{<k}\to S$. In this case indeed the empty string is the trivial function from $\varnothing$, which has the usual encoding of $\varnothing$ as a set. Concatenation can be defined on these functions with some care.

But! To drive the point home, this isn't a typical set-theoretic definition of $k$-tuple, where one might instead usually use something like iterations of $A\times B\mapsto\{A, \{A, B\}\}$. In this case the empty set isn't an identity, so it can't be the empty string. It's instead a 1-tuple with element $\varnothing$! The notion of 0-tuple is not well defined here. This doesn't mean you can't make strings out of this notion, you just need a special symbol for the empty string (say, $S\cup\{S\}$ if $S$ is your symbol set) and to adjust your notions of concatenation, etc., appropriately.

Soundwave
  • 433
  • Just to be sure since my math is rusty, is $\mathbb{N}{<k}\to S$ defined as the set of natural numbers less than $k$, wherein you are including 0 as a natural number (so that $\mathbb{N}{<0} = \emptyset$) and then we have that the only function $\emptyset \to S$ is the empty set (function), as you say? – EE18 Feb 10 '24 at 19:19
  • Sorry, I meant $\mathbb{N}{<k}$ not $\mathbb{N}{<k}\to S$. – EE18 Feb 10 '24 at 19:26
  • @EE18 Exactly correct – Soundwave Feb 10 '24 at 19:26
  • Thanks again for your help! – EE18 Feb 10 '24 at 19:26