{\huge Thinking Out of the Notation Box}

How we cope with overloaded words and symbols

\vspace{.3in}

Georg Cantor invented not only the concepts of transfinite cardinal and ordinal numbers, but also the notation we still use for them today. He accented the novelty and grandeur of the cardinals by reaching into the Hebrew alphabet for its head letter, $latex {\aleph}&fg=000000$ (aleph). Thus $latex {\aleph_0}&fg=000000$ denotes the cardinality of the natural numbers, $latex {\aleph_1}&fg=000000$ the least infinite cardinal above $latex {\aleph_0}&fg=000000$, and so on. For ordinals, however, he recycled the Greek letter $latex {\omega}&fg=000000$. While Cantor's remains the only use of $latex {\aleph}&fg=000000$ in mathematics noted by Wikipedia, $latex {\omega}&fg=000000$ competes with many uses including the complex roots of unity. It is easy to imagine a paper employing $latex {\omega}&fg=000000$ in both senses, not to mention proving an $latex {\omega(n)}&fg=000000$ lower bound for some algorithm involving ordinals and/or roots.

Today in the spirit of Labor Day we lead a fun discussion on how words and symbols are asked to work overtime shifts.

To be sure, Cantor had a devout motivation for his choices, and I (Ken) wonder whether and how far the following speculation goes beyond documentary knowledge. In the New Testament, God is called the Alpha and Omega ($latex {A~\Omega}&fg=000000$) for the first and last letters of the Greek alphabet. By choosing the corresponding, similar-sounding Hebrew letter aleph, Cantor reflected both the Hebrew Bible and the Jews among his ancestors. Among reasons not to use a capital Omega are the hypothesis that the symbol $latex {\infty}&fg=000000$ for infinity, which was already standard, derives from $latex {\omega}&fg=000000$ to begin with, and this thought of mine: To indicate the least cardinal above the progression

$latex \displaystyle \aleph_0,\aleph_1,\aleph_2,\dots,&fg=000000$

Other long-standing notation has had less thought. Wikipedia cites a speculation that $latex {\pi}&fg=000000$ was chosen in 1706 to mean ``periphery.'' Leonhard Euler put his stamp on this usage, but may not have intended to name the constant $latex {e}&fg=000000$ after himself, when he first used it in a paper on explosions in cannons. We recently noted that Alonzo Church once replied to a query on why he chose $latex {\lambda}&fg=000000$ for lambda-calculus by writing on a postcard, ``Eeny, meeny, miny, moe.''

O(n) and O(n) and On\dots

Dick conceived this post idea during discussions last week at Georgia Tech with the visiting Noga Alon, in which an algorithm arose that runs in linear time in the case of orthogonal matrices. The group of such matrices is standardly denoted by $latex {O(n)}&fg=000000$, thus the result could be summarized by saying

$latex \displaystyle O(n) \text{~is~} O(n).&fg=000000$

The $latex {O}&fg=000000$ in $latex {O(n)}&fg=000000$ is really a capital Greek omicron, which literally means ``little oh.'' That makes more sense for the $latex {o}&fg=000000$ in $latex {o(n)}&fg=000000$, but there is a common meaning: the ``micron'' part suggests functions that are lower. Similarly omega is just Greek for ``big oh''---they really didn't have a more intimate name for these letters---and suggests functions that are greater. The crossbar in the $latex {\Theta}&fg=000000$ of $latex {\Theta(n)}&fg=000000$ suggests parity of growth. Thus Donald Knuth, in his famous article promoting these symbols in computer science, found them to be well-thought-out mnemonics. One can argue they should have pride of place over uses such as

$latex \displaystyle \Omega(n) = \text{the number of prime factors of~} n \text{~with multiplicities}.&fg=000000$

This kind of overloading is apart from the issue of whether one should write $latex {f(n) = O(n)}&fg=000000$ or $latex {f(n) \in O(n)}&fg=000000$, the latter so that $latex {O(n)}&fg=000000$ denotes a set of functions. I once insisted on the latter usage, but later realized that such purism demands writing ``$latex {f \in O(n)}&fg=000000$,'' which however subtracts clarity when the reader should emphasize that $latex {f(n)}&fg=000000$ is a running time.

Type and Type and Human Type

I am also reminded of a footnote in the famous text Complex Analysis by Lars Ahlfors:

Modern students are well aware that $latex {f}&fg=000000$ stands for the function and $latex {f(z)}&fg=000000$ for a value of the function. However, analysts are traditionally minded and continue to speak of ``the function $latex {f(z)}&fg=000000$.''

There is also a note about the benign overload of writing $latex {f(A)}&fg=000000$ to denote $latex {\{f(a) : a \in A\}}&fg=000000$ where $latex {A}&fg=000000$ is a set. To my mind stating the type signature of the function $latex {f}&fg=000000$ completely removes ambiguity here. However, type theory is far from a cure-all for ambiguity in familiar programming languages. The C++ standard has recently opted to overload its keywords {\tt typename} and {\tt base} with new uses to avoid compiler issues connected with template classes.

Symbols used to be limited to the fonts available for journal and book composition. The upside-down $latex {\forall}&fg=000000$ and backwards $latex {\exists}&fg=000000$ in logic were convenient for hard-metal compositors because they could simply invert existing letters. Here on this blog, Dick and I still feel the limitation of early \TeX systems to the symbols that our WordPress \LaTeX support can understand. Sometimes we resport to manual HTML fixup.

But now that Unicode has expanded the old ASCII universe to a new standard, scientists have no fetters to embracing new characters as well as typefaces. We previously discussed the freedom and power of the big APL programming language character set, but first we ask a simpler question:

Why not use more Hebrew letters, and Russian and other alphabetic characters? Why not some nice Chinese for vivid special uses?

Maybe this is a silly question with a simple answer: we use what we feel our readers will be familiar and comfortable with, let alone ourselves. And we may find a greater human answer by considering how we overload existing words, where exotic characters are not an issue.

Word Examples

This year we have been celebrating Alan Turing as progenitor of the computer. At the time of his famous 1936 paper, the word denoted a person doing computation, but any ambiguity from that meaning quickly disappeared. For most of our lives the computer has marched from glory to glory, which prefixing the word ``personal'' did not diminish. But now hear how the names for the most-sold units of Turing's conception have devolved:

• Desktop.
• Notebook.
• Laptop.
• Tablet.
• Smartphone.

Turing would have recognized the first four common English words, and might have figured the last as the kind of speech-encryption device he worked on during WW II, but would he have associated any of them with computer? It's odd enough that we take two tablets to relieve headache while Moses took two tablets down from Mount Sinai. Even odder is that the new computer usage primarily denotes a size factor, one that is probably smaller than any tablet used in antiquity or in old-style schoolhouses, and displaces the recent technological meaning of a graphical input device.

We would love to see creative new names for these devices, but names grow by association and diffusion. I'm sure there are Hebrew or Russian words for them that would sound great, but would they sell?

Wordplay and Math Overloads

Word overloading is most fun to recognize when there is a change in accent or pronunciation. This is different from having 645 different meanings for ``run'' all pronounced the same, or my uses of ``type'' above, or having échecs in French mean both ``chess'' and ``failures'' (checks). Here are some English examples:

• She spoke Polish with polish.
• He could lead if he would get the lead out.
• The farm was used to produce produce.
• The overfilled dump had to refuse more refuse.
• Why did the nomads desert the desert?
• No time like the present to present the present.
• The bass trombonist fished for bass.
• When shot at, the dove dove into the bushes.
• I did not subject the object to close analysis, or object to its subject matter.
• The insurance was invalid for the invalid.
• The bandage was wound around the wound.
• The budget cuts caused a row three meetings in a row.
• The vote to close the meeting was close.

Can we find analogous examples in mathematics or science? We recently noted overloads of definitions such as ``normal.'' Can you combine some of them in a believable formal statement? Have you been confused by a usage that you originally took to be a different meaning, either of a symbol or a term? For instance, a paper might use $latex {\epsilon}&fg=000000$ to mean the identity of an algebraic structure as well as a tiny quantity.

Open Problems

Will we expand our range of symbols now that they are easily at our disposal?

Can you find mathematical ``homonyms'' that are humorous, and/or cause real ambiguity?