{\huge The Right Stuff of Emptiness}
How $latex {\emptyset}&fg=000000$ versus $latex {\{\epsilon\}}&fg=000000$ can be like life and death
\vspace{.25in}
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 $latex {\{0,1\}}&fg=000000$ or $latex {\{a,b\}}&fg=000000$ or similar in nearly all instances. The textbook by Mike Sipser helps by having examples where tokens like ``{\tt REAR}'' or ``{\tt
I got on to say that strings over any alphabet can be re-coded over $latex {\{0,1\}}&fg=000000$. 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 $latex {\{0,1\}}&fg=000000$ as ``the'' alphabet for theory but can speak in terms of a generic {\tt char} type for practice. Then in terms of the C++ standard library I write {\tt alphabet = set
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 $latex {\cup}&fg=000000$ and $latex {\cap}&fg=000000$ 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 $latex {A}&fg=000000$ with itself, written $latex {A\cdot A}&fg=000000$ or $latex {A^2}&fg=000000$, equals $latex {\{xy: x \in A \wedge y \in A\}}&fg=000000$, not $latex {\{x^2: x \in A\}}&fg=000000$. The most confusion and error I see, however, arises from the empty language $latex {\emptyset}&fg=000000$ versus the empty string $latex {\epsilon}&fg=000000$ (or $latex {\lambda}&fg=000000$ 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 $latex {x \cdot y}&fg=000000$ for strings. I then say that $latex {\emptyset}&fg=000000$ behaves like $latex {0}&fg=000000$ and $latex {\{\epsilon\}}&fg=000000$ behaves like $latex {1}&fg=000000$ 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 {\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:
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:
\noindent 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.
Maybe only then, the significance of the words ``appropriate for the co-pilot to initiate'' in my definitions of $latex {L_1}&fg=000000$ and $latex {L_2}&fg=000000$ dawns on the class, as well as the Boolean and. The appropriate string $latex {x}&fg=000000$ is $latex {\epsilon}&fg=000000$ in both cases: the co-pilot should not ``initiate'' any actions.
As witnessed by the stories above, in the case of $latex {L_1}&fg=000000$ there is a good chance even if both engines fail, so the second clause is certainly satisfied. Thus $latex {L_1 = \{\epsilon\}}&fg=000000$. Perhaps the example of Sullenberger and Skiles at 850 meters makes it too pessimistic for me to say $latex {L_2}&fg=000000$ 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 $latex {x}&fg=000000$ is true. Thus the intent is $latex {L_2 = \emptyset}&fg=000000$.
There it is: the difference between $latex {\{\epsilon\}}&fg=000000$ and $latex {\emptyset}&fg=000000$ 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 $latex {\emptyset^*}&fg=000000$ turns around and becomes $latex {\{\epsilon\}}&fg=000000$. I say that the convention $latex {A^0 = \{\epsilon\}}&fg=000000$ helps make the power law $latex {A^{m+n} = A^m \cdot A^n}&fg=000000$ true for all $latex {m,n \geq 0}&fg=000000$, but why is this law relevant for $latex {A = \emptyset}&fg=000000$? Why do we need to define $latex {\emptyset^0}&fg=000000$ anyway, let alone stipulate that it equals $latex {\{\epsilon\}}&fg=000000$?
If I say it's like $latex {0^0 = 1}&fg=000000$ in arithmetic, the students can find various sources saying $latex {0^0 = 1}&fg=000000$ is a ``convention'' and ``controversial.'' So I say it's like the convention that a for-loop
{\tt for (int i = 0; i < n; i++) \{~\dots~\}}
naturally ``falls through'' when $latex {n = 0}&fg=000000$. 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 ($latex {\{\epsilon\}}&fg=000000$) rather than a kill ($latex {\emptyset}&fg=000000$), so the whole flow-of-control analysis is $latex \displaystyle \emptyset^0 = \{\epsilon\}. &fg=000000$
To go deeper---usually as notes for TAs if time permits in recitations or as a note in the course forum---I connect $latex {0^0}&fg=000000$ to logic and relations. I've defined a function from a set $latex {A}&fg=000000$ to a set $latex {B}&fg=000000$ as a relation $latex {R \subseteq A \times B}&fg=000000$ that satisfies the test $latex \displaystyle T = (\forall x \in A)(\exists y \in B): xRy \wedge (\forall y' \in B) xRy' \implies y' = y. &fg=000000$
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 $latex {A = \emptyset}&fg=000000$ the test $latex {T}&fg=000000$ becomes a universally quantified formula over an empty domain, and so it defaults to true. Thus $latex {\emptyset: \emptyset \longrightarrow B}&fg=000000$ counts as a function regardless of what $latex {B}&fg=000000$ is, even if $latex {B = \emptyset}&fg=000000$ too.
Because $latex {\emptyset \times B = \emptyset}&fg=000000$, the only possible relation on $latex {\emptyset \times B}&fg=000000$ is $latex {R = \emptyset}&fg=000000$. So the cardinality of the set of functions from $latex {\emptyset}&fg=000000$ to $latex {B}&fg=000000$ is $latex {1}&fg=000000$. The notation for the set of functions from a set $latex {A}&fg=000000$ to a set $latex {B}&fg=000000$, namely $latex {B^A}&fg=000000$, is motivated by examples like $latex {\{0,1\}^5}&fg=000000$ being the set of binary functions on $latex {[5] = \{0,1,2,3,4\}}&fg=000000$. There are $latex {2^5 = 32}&fg=000000$ such functions, and in general $latex \displaystyle \left|B^A\right| = |B|^{|A|}. &fg=000000$
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 $latex {r + s}&fg=000000$ for regular expressions over Sipser's $latex {r \cup s}&fg=000000$ in order to leverage the analogy between concatenation and multiplication, even though $latex {r + r}&fg=000000$ equals $latex {r}&fg=000000$ not any notion of ``$latex {2r}&fg=000000$.'' The property $latex {(\forall r)\;r + r = r}&fg=000000$ does not hold over any field, except for the possibility of the ``field of one element'' $latex {\mathbb{F}_1}&fg=000000$ which we discussed some time back.
Now consider the suggestive analogy $latex \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} &fg=000000$
Does it really fail? Perhaps it succeeds in some structure that embraces both equations---perhaps involving $latex {\mathbb{F}_1}&fg=000000$? Our earlier post and its links noted that $latex {\mathbb{F}_1}&fg=000000$ 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 $latex {\emptyset}&fg=000000$ 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 {\'A}lvaro Pelayo and Martin Warren in the AMS Bulletin, the object is to make $latex {\emptyset}&fg=000000$ and other sets emerge from the framework rather than form its base.
Open Problems
Does handling $latex {\emptyset}&fg=000000$ and $latex {\epsilon}&fg=000000$ right handle everything?
RR: The co-pilot deserves a medal too.
Exec: Why? He didn't do anything.
RR: Exactly.