How ∅ versus {ε} can be a life-and-death difference

 Cropped from source

Jeff Skiles was the co-pilot on US Airways Flight 1549 from New York’s LaGuardia Airport headed for Charlotte on January 15, 2009. The Airbus A320 lost power in both engines after striking birds at altitude about 850 meters and famously ditched in the Hudson River with no loss of life. As Skiles’s website relates, he had manual charge of the takeoff but upon his losing his instrument panel when the engines failed,

“Captain Chesley Sullenberger took over flying the plane and tipped the nose down to retain airspeed.”

Skiles helped contact nearby airports for emergency landing permission but within 60 seconds Sullenberger and he determined that the Hudson was the only option. His front page does not say he did anything else.

Today we tell some stories about the technical content of forms of emptiness.

I am teaching Buffalo’s undergraduate theory of computation course again. I like to emphasize early on that an alphabet need not be only a set of letter or digit symbols, even though it will be ${\{0,1\}}$ or ${\{a,b\}}$ or similar in nearly all instances. The textbook by Mike Sipser helps by having examples where tokens like “REAR” or “<RESET>” denoting actions are treated as single symbols. An alphabet can be the set of atomic actions from an aircraft or video game console. Some controls such as joysticks may be analog, but their output can be transmitted digitally. What’s important is that any sequence of actions is represented by a string over an appropriately chosen alphabet.

I go on to say that strings over any alphabet can be re-coded over ${\{0,1\}}$. Or over ASCII or UTF-8 or UNICODE, but those in turn are encoded in 8-bit or 16-bit binary anyway. I say all this justifies flexible thinking in that we can regard ${\{0,1\}}$ as “the” alphabet for theory but can speak in terms of a generic char type for practice. Then in terms of the C++ standard library I write alphabet = set<char>, string = list<char>, language = set<string>, and class = set<language>. I go on to say how “${M = (Q,\Sigma,\delta,s,F)}$” abbreviates object-oriented class notation in which set<State;> Q; and alphabet Sigma; and State start; and set<State> finalStates; are fields and delta can be variously a map or a function pointer or a set of tuples regarded as instructions.

## Emptiness

In the course I’m glad to go into examples of DFAs and NFAs and regular expressions right away, but reaching the last is high time to say more on formal language theory. I’ve earlier connected ${\cup}$ and ${\cap}$ to Boolean or and and, but concatenation of languages needs explaining as a kind of “and then.” One point needing reinforcement is that the concatenation of a language ${A}$ with itself, written ${A\cdot A}$ or ${A^2}$, equals ${\{xy: x \in A \wedge y \in A\}}$, not ${\{x^2: x \in A\}}$. The most confusion and error I see, however, arises from the empty language ${\emptyset}$ versus the empty string ${\epsilon}$ (or ${\lambda}$ in other sources).

I explain the analogy between multiplication and concatenation although the latter is not commutative, and that the operation between languages naturally “lifts” the definition of ${x \cdot y}$ for strings. I then say that ${\emptyset}$ behaves like ${0}$ and ${\{\epsilon\}}$ behaves like ${1}$ under this analogy, but I don’t know how well that catches on with the broad range of students. So not always but a few times when lecture prep and execution has left 6–10 minutes in the period, I wrap a story into an example:

Let ${\text{\tt CESSNA}}$ denote the alphabet of controls on a typical twin-engine Cessna business jet. I will define two languages over this alphabet—you tell me what they are:

1. ${L_1 = \{x \in \text{\tt CESSNA}^*: x}$ represents an appropriate sequence of actions for the co-pilot to initiate if 1 engine fails at 100 meters altitude, and with ${x}$ there is a non-miraculous chance of saving the plane${\}}$.

2. ${L_2 = \{x \in \text{\tt CESSNA}^*: x}$ represents an appropriate sequence of actions for the co-pilot to initiate if 2 engines fail at 2000 meters altitude, and with ${x}$ there is a non-miraculous chance of saving the plane${\}}$.

After carefully writing this on board or slide, I say, “you have enough information to answer this; it could be a pop quiz.” I let 15–20 seconds go by to see if someone raises a hand amid bewildered looks in silence, and then I say, “OK—I’ll tell a real-life story.”

## The Story

My father Robert Regan was a financial reporter specializing in aluminum and magnesium. Once in the 1970s he covered a meeting of aluminum company executives in North Carolina. One of the executives failed to show for the first evening, and the news of why was not conveyed until he appeared in splint and bandages at breakfast the next morning.

He told how his twin-engine crew-of-two jet had lost all power immediately after takeoff. With no time or room for turning back, the pilot spotted the flat roof of a nearby bowling alley and steered for it as little he could. The jet pancaked on the roof and bounced into the mercifully empty parking lot. Everyone survived and could thank the way the force of impact had been broken into two lesser jolts. The end of the executive’s tale and interaction with my father in the breakfast-room audience went about as follows:

Exec: I have never seen such a great piece of quick thinking and calm control in my lifetime of business, to say nothing of the sheer flying skill. That pilot ought to get a medal.

RR: The co-pilot deserves a medal too.

Exec: Why? He didn’t do anything.

RR: Exactly.

Maybe only then the significance of the words “appropriate for the co-pilot to initiate” in my definitions of ${L_1}$ and ${L_2}$ dawns on the class, as well as the Boolean and. The appropriate string ${x}$ is ${\epsilon}$ in both cases: the co-pilot should not “initiate” any actions.

As witnessed by the stories above, in the case of ${L_1}$ there is a good chance even if both engines fail, so the second clause is certainly satisfied. Thus ${L_1 = \{\epsilon\}}$. Perhaps the example of Sullenberger and Skiles at 850 meters makes it too pessimistic for me to say ${L_2}$ is a goner at 2,000 meters, but the point of the example is that an unsatisfied conjunct in a set definition makes the whole predicate false even if the part depending on ${x}$ is true. Thus the intent is ${L_2 = \emptyset}$.

There it is: the difference between ${\{\epsilon\}}$ and ${\emptyset}$ can be one of life and death. How much the story helps burnish the difference is hard to quantify, but at least much of the class tends to get a later test question involving this difference right.

## Zero to the Zero

Whether I tell the story or not, I next have to convey why ${\emptyset^*}$ turns around and becomes ${\{\epsilon\}}$. I say that the convention ${A^0 = \{\epsilon\}}$ helps make the power law ${A^{m+n} = A^m \cdot A^n}$ true for all ${m,n \geq 0}$, but why is this law relevant for ${A = \emptyset}$? Why do we need to define ${\emptyset^0}$ anyway, let alone stipulate that it equals ${\{\epsilon\}}$?

If I say it’s like ${0^0 = 1}$ in arithmetic, the students can find various sources saying ${0^0 = 1}$ is a “convention” and “controversial.” So I say it’s like the convention that a for-loop

for (int i = 0; i < n; i++) { ... }

naturally “falls through” when ${n = 0}$. Even if the loop is checking for conditions that might force your code to terminate—and even if the body is definitely going to kill your program on entry—if the loop executes 0 times then you’re still flying. It’s a no-op represented by ${\{\epsilon\}}$ rather than a killing ${\emptyset}$, so the whole flow-of-control analysis is

$\displaystyle \emptyset^0 = \{\epsilon\}.$

Thus it comes down to the logical requirement that a universally quantified test on an empty domain defaults to true. Not just they but I can feel this requirement better in programming terms.

To go deeper—usually as notes for TAs if time permits in recitations or as a note in the course forum—I connect ${0^0}$ to logic and relations. I’ve defined a function from a set ${A}$ to a set ${B}$ as a relation ${R \subseteq A \times B}$ that satisfies the test

$\displaystyle T = (\forall x \in A)(\exists y \in B)\!: xRy \wedge (\forall y' \in B)[xRy' \longrightarrow y' = y].$

Is the empty relation a function?

There’s an impulse to answer, “of course it isn’t—there aren’t any function values.” But when ${A = \emptyset}$ the test ${T}$ becomes a universally quantified formula over an empty domain, and so it defaults to true. Thus ${\emptyset: \emptyset \longrightarrow B}$ counts as a function regardless of what ${B}$ is, even if ${B = \emptyset}$ too.

Because ${\emptyset \times B = \emptyset}$, the only possible relation on ${\emptyset \times B}$ is ${R = \emptyset}$. So the cardinality of the set of functions from ${\emptyset}$ to ${B}$ is ${1}$. The notation for the set of functions from a set ${A}$ to a set ${B}$, namely ${B^A}$, is motivated by examples like ${\{0,1\}^5}$ being the set of binary functions on ${[5] = \{0,1,2,3,4\}}$. There are ${2^5 = 32}$ such functions, and in general

$\displaystyle \left|B^A\right| = |B|^{|A|}.$

With ${A = B = \emptyset}$ all this gives ${0^0 = 1}$. Thus ${0^0 = 1}$ and ${\emptyset^* = \{\epsilon\}}$ are needed for the universe of mathematics based on sets and logic to come out right.

## Emptiness and Type

The same analysis shows that an empty relation on a nonempty domain is not a function. This means that even when stuff is empty, the type signature of the stuff matters too. One student in my course told me last week that the realization that “empty” could come with a type helped him figure things out.

Real advances in mathematics have come from structure channeling content even when the content is degenerate or empty. There are more hints of deeper structure even in basic formal language theory. I generally encourage the notation ${r + s}$ for regular expressions over Sipser’s ${r \cup s}$ in order to leverage the analogy between concatenation and multiplication, even though ${r + r}$ equals ${r}$ not any notion of “${2r}$.” The property ${(\forall r)\;r + r = r}$ does not hold over any field, except for the possibility of the “field of one element” ${\mathbb{F}_1}$ which we discussed some time back.

Now consider the suggestive analogy

$\displaystyle \begin{array}{rcl} \;A^*\; &=& \{\epsilon\} \cup A \cup A^2 \cup A^3 \cup \cdots\\ \frac{1}{1-a} &=& \;\,1 \,\;+\, a + a^2 + a^3 \,+ \cdots \end{array}$

What substance does it have beyond optics? The latter equation holds provided ${|a| < 1}$ even over the complex numbers, and also holds in a sense for ${a = 1}$. The analogy ${A = \emptyset}$, ${a = 0}$ works in both equations to yield ${\{\epsilon\}}$ and ${1}$. We then find it disturbing, however, that substituting ${A = \{\epsilon\}}$, ${a = 1}$ fails because ${\{\epsilon\}^* = \{\epsilon\}}$ which is not infinite.

Does it really fail? Perhaps it succeeds in some structure that embraces both equations—perhaps involving ${\mathbb{F}_1}$? Our earlier post and its links noted that ${\mathbb{F}_1}$ has an awful lot of structure and connections to other parts of mathematics despite its quasi-empty content.

We know several ways to build a universe on emptiness. In them the supporting cast of structure rather than ${\emptyset}$ is the real lead. The new actor in town, Homotopy Type Theory, aims to find the right stuff directly in terms of types and the identity relation and a key notion and axiom of univalence. As related in a recent survey by Álvaro Pelayo and Martin Warren in the AMS Bulletin, the object is to make ${\emptyset}$ and other sets emerge from the framework rather than form its base.

## Open Problems

Does handling ${\emptyset}$ and ${\epsilon}$ right take care of everything?

February 23, 2015 7:01 pm

That’s like P=NP… It’s ε percent false, but not zero percent! 🙂

2. February 24, 2015 12:55 am

I don’t know about Cessnas, but if I’m not mistaken, a lot of aircraft can glide and attempt to find a safe landing that way, even if all the engines give out. Now, if a wing comes off, that’s another story…

3. February 24, 2015 8:30 am

Very interesting! (as usual)

The last paragraph about the free monoid construction, and the analogy with the formula $\frac{1}{1-a} = 1 + a + a^2 + \dots$ is also discussed in this post https://golem.ph.utexas.edu/category/2013/04/iterating_the_free_monoid_cons.html

Also, I don’t know if it is completely unrelated or not, but there is this weird “Euler-Maclaurin” formula
$$1 + 1 + 1 + \dots = – 1/2$$
(as discussed e.g. here https://terrytao.wordpress.com/2010/04/10/the-euler-maclaurin-formula-bernoulli-numbers-the-zeta-function-and-real-variable-analytic-continuation/ )

Is there any relation with the free monoid construction ? I have no idea …

Regards,
pb

4. February 24, 2015 10:08 am

Very interesting post. Re the benefit of “not doing anything,” I remember my flight instructor describing the first two steps in the event of an emergency: Step 1: Stop, and take a deep breath. Step 2: Stop, and take *another* deep breath.

5. February 24, 2015 10:18 am

This brings to mind an old puzzle that I puzzle over from time to time —

That’s an old write up — I think I can improve it with a little thought.

February 25, 2015 3:56 am

Dear Dick & Ken,

I had a paper submitted (to the most prestigious conference) about the empty string. I got the following feedback:

======================================================
On a personal note, I am sincerely worried about you. Your obsession with the
empty string might be due to a medical problem. Please talk to a doctor about
it. I am not trying to dismiss you, and I am not making a joke. Your
considerable mental energy should have a healthier focus.
=========================================================

According to the TCS communit: Aristtle, Descartes should consult a doctor because they suffer from a medical problem.

Your post proposes the inconsistency conjecture:”0=1″.

Leave the proof for your students.

Best,

Rafee Kamouna.

7. February 25, 2015 10:01 am

Interesting thoughts here. I especially enjoy the story of the pilots. Thanks for sharing.

8. February 26, 2015 6:54 am

The description of your class lesson reminds me of a question that I had as a student.
On the undecidable problem of computing the halting of a Turing Machiner with the empty string as input what is the difference of when
a) the tape of the machine has nothing printed on and
b) when the tape has printed on the character # which we define that it represents emptyness.
At that time I had thought that it must be pretty much the same.

February 26, 2015 9:42 am

Paradoxical being # and empty at the same time. Your question is banned among all TCS journals/conferences. Why? because you proved P=NP Iff P!=NP.

best,

Rafee Kamouna.

• February 26, 2015 12:09 pm

Check this book chapter

http://www.cs.um.edu.mt/gordon.pace/Teaching/Complexity/CoursePage/Notes/chapter5.pdf

see in page 59 the definition of blank symbol; it could be #.
So, as a student I thought of the case where the empty string consists of blank symbols, like #. Such a string would represent emptyness, meaning no information.
Think of it in Java terms, what’s the difference between declaring
String myvar;
and
String myvar = “”;
In the first case we have a declared string with no information in the second case a declared and defined empty string.
It may sound paradoxical but it is not.

February 27, 2015 1:27 am

myvar=”” has an internal form which must not be empty. Thus, if it is empty, then it is not empty.

best,

Rafee Kamouna.

11. February 27, 2015 6:11 am

I found the cessna analogy more confusing than helpful, particularly since as you say the distinction isn’t true.

Honestly I find it clearer without symbols, just writing {} and {{}} the difference is obvious as the difference between 0 and 1 (particularly since for one model of the naturals that’s exactly what it is). And then the idea that {}* = {{}} is obvious, just as the power set P({}) = {{}} – that is, the set of all subsets of the empty set is the set containing the empty set. (If this is confusing, it becomes less so when you remember that P({x}) = {{}, {x}}). Likewise the piece about relations is just that a function is a “mapping” of every element of its domain – so just as {x → y} is a valid function from {x} to {y}, {} is a valid function from {} to {}.

I’m not at all convinced that the final “analogy” is valid – it holds for 0 as you say, but does it hold for any other values? To my mind any definition of + under which r + r = r for r != 0 is too different to justify using the symbol.

• February 27, 2015 5:18 pm

I don’t wish to identify {ε} with {{}} or {∅} since set-emptyset has type set-of-languages in the type classification. It is the class of languages containing ∅ and nothing else, an entity that might come up in a discussion of Rice’s Theorem later on, for instance. Nor do I wish to involve Church numerals, and I don’t see the lower-level explanatory power in the reference to “mapping”.

In answer also to Sniffnoy above, the issue for me is the presentation value of keeping the alliteration of “L_1, 1 engine, 100m” versus “L_2, 2 engines, 2000m” with everything else unchanged so the intended contrast is clear—while also avoiding the “downer” of writing something actually hopeless like losing a wing…

February 27, 2015 6:28 am

All mathematical systems have an empty set and an empty element (string). Thus, 2 different models of the natural numbers. If a number theory result is proved on one model, it remains ridiculously open on the other.

In any case, all mathematicians who love numbers will feel that this is UGLY.

They will run away. They will never attempt the inconsistency conjecture. I feel sorry for them. Imagine someone proved to Beethoven that music is wrong, what response do you expect?

best,

Rafee Kamouna.

Well, in rational power series theory, $r + r$ is indeed $2r$, and the term *rational* itself comes from the power series expansion of $\frac{1}{1-a}$. Taking the underlying semiring to be the Boolean one, $2r = r$. Arguably, we should skip all of this regular language nonsense and go directly to rational formal power series 🙂