How we cope with overloaded words and symbols

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, ${\aleph}$ (aleph). Thus ${\aleph_0}$ denotes the cardinality of the natural numbers, ${\aleph_1}$ the least infinite cardinal above ${\aleph_0}$, and so on. For ordinals, however, he recycled the Greek letter ${\omega}$. While Cantor’s remains the only use of ${\aleph}$ in mathematics noted by Wikipedia, ${\omega}$ competes with many uses including the complex roots of unity. It is easy to imagine a paper employing ${\omega}$ in both senses, not to mention proving an ${\omega(n)}$ lower bound for some algorithm involving ordinals and/or roots.

Today, in the spirit of Labor Day, we lead a lighthearted 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 Book of Revelation, God is called the Alpha and Omega (Α Ω) 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 ${\infty}$ for infinity, which was already standard, derives from ${\omega}$ to begin with, and this thought of mine: To indicate the least cardinal above the progression

$\displaystyle \aleph_0,\aleph_1,\aleph_2,\dots,$

Cantor’s notation logically calls for ${\aleph_\omega}$. It may have felt devoutly less seemly to subscript a capital letter taken as standing for God.

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

## O(n) and O(n) and On…

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 ${O(n)}$, thus the result could be summarized by saying:

$\displaystyle O(n) \text{~is~} O(n).$

I mis-recalled the same name being used in John Horton Conway’s book On Numbers and Games—it is On without the parentheses, and the book focuses on “the curious field On${_2}$.”

The Ο in ${O(n)}$ is really a capital Greek omicron, which literally means “little oh.” That makes more sense for the ο in ${o(n)}$, but there is a common meaning: the “micron” part suggests functions that are lower. Similarly omega is just Greek for “big oh”—the Greeks didn’t have a more intimate name for these letters—and suggests functions that are greater. The crossbar in the Θ of ${\Theta(n)}$ 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

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

This kind of overloading is apart from the issue of whether one should write ${f(n) = O(n)}$ or ${f(n) \in O(n)}$, the latter so that ${O(n)}$ denotes a set of functions. I once insisted on the latter usage, but later realized that such purism demands writing “${f \in O(n)}$,” which however subtracts clarity when the reader should emphasize that ${f(n)}$ 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 ${f}$ stands for the function and ${f(z)}$ for a value of the function. However, analysts are traditionally minded and continue to speak of “the function ${f(z)}$.”

There is also a note about the benign overload of writing ${f(A)}$ to denote ${\{f(a) : a \in A\}}$ where ${A}$ is a set. To my mind stating the type signature of the function ${f}$ 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 typename and 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 ${\forall}$ and backwards ${\exists}$ 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—as this sentence exemplifies. Sometimes we resort 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?

 Composite of src1, src2, and src3.

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 two and fourth as 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?

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.

• 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.

• When you do arithmetic, remember the arithmetic mean.

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 ${\epsilon}$ 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 more easily at our disposal?

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

1. September 4, 2012 4:31 pm

The second Hebrew letter beth is used to denote a sub-sequence of the cardinals, and Cantor himself used the last letter, tav, to denote the totality of all the cardinals. I decided to cut the topic of different pronunciations of people’s names as not being germane, but wish to share this limerick of my devising:

A single ballplayer named Jeter
Liked a runner and wanted to meet her.
So he wrote a love letter
To the sprinter named Jeter,
But ‘no dice’ said our gold Carmelita.

2. September 4, 2012 5:52 pm

The Russian letter Ш is used in topology and number theory.

September 4, 2012 9:10 pm

Among philosophers the stars of the constellation Cassiopeia are read as forming the initial of either “Malcolm” or “Wittgenstein”. 🙂

September 5, 2012 4:19 am

I wonder if the human mind doesn’t need some ambiguity to function properly. Otherwise, how to explain the failure of a constructed language like Lojban, which was designed to remove any syntactic – if not semantic – ambiguity from human communication? I think most of us like the freedom to choose our desired meanings on the fly, rather than always pick them up in a dictionary…

• September 6, 2012 1:00 am

I’ve actually become an evangelist of the idea that ambiguity in language is a Good Thing. And more is better, so long as the language can still be generally understood.

The reason: generation of ideas. Suppose I tell you “I just ordered a bible,” but you here “I just bought a ‘buy’ bull.” You haven’t heard of that before, but you think it’s probably a bull that sits on your desk and lights up when the market is hot. Now I have to explain that it’s not what I said; such a thing doesn’t exist. But maybe it should exist, and you can manufacture it! An idea just popped out of a misunderstanding.

That example is obviously absurd, but hopefully it carries the point: ambiguous communication allows us to summon find ideas neither of us would have imagined when using “lossless” communication of ideas. More often for me, though, a plausible misinterpretation just gives me a (much-appreciated!) chuckle in a perhaps otherwise dull conversation.

September 7, 2012 10:44 am

Quite right: just like in mechanics, one has to leave some play in the works of the brain. But wait: why not try to leave some play in the works of computers as well? I think that’s what they call fuzzy logic and it does wonders…

September 5, 2012 5:05 am

Back when I was a mathematician, I was always frustrated by texts using gothic symbols. I found them hard to parse/internalise and they mostly seemed gothic squiglies. The internalisation went something like this: ‘Gothic squigly thingamjig of n applied to foo’. My peculiarity no doubt, but I agree with your simple answer. Exotic symbols, especially if more than one are used, are hard to internalise.

September 6, 2012 3:57 am

This is especially true of schemes in algebraic geometry in uppercased Gothics and of ring ideals in commutative algebra in lowercase Gothics. At least they could provide the reader with their version of the Gothic alphabet but they never bother to do that.

September 5, 2012 7:45 am

If we were to adopt Chinese characters, why limit ourselves to 25 which look (if you squint) like Latin letters? Pick the ones that are meaningful (perhaps one day we’ll arrive at meaningful variable names in mathematics via the route of learning Chinese). After all, it used to be that one had to learn German or Latin to do mathematics.

September 5, 2012 12:11 pm

but Chinese mathematicians use Latin letters for variables!

• September 6, 2012 4:03 pm

I chose an illustration with Latin-ish ones because they have fewer strokes. There are probably several hundred ones that would be suitable, as well as Japanese hiragana and katakana. Did Chinese mathematicians use variables before exposure to the West?

September 5, 2012 7:47 am

Exotic symbols are very culture dependent – 19-th century European mathematicians were obviously comfortable with Gothic letters, as well as Greek; most of us (professors) are comfortable with Greek letters, but to many students they are exotic (and sometimes hard to internalise, I see it in classes). But overall, I’d prefer an exotic symbol (or a multi-letter symbol, which is acually a popular choice in CS) to an overload. Overloading creates confusion.
So does the equality before O(n); I have seen too many errors due to this notational abuse.
I would certainly prefer $\in O(n)$.
Do you find that in $f\in O(n)$ you are missing an $n$ on the left hand side? You are right; the proper form is $\lambda n. f(n) \in O(n)$. It may be regrettable that the use of lambda-expressions is so uncommon in TCS. However, a good compromise may be to use inequality: $f(n) \le O(n)$. I find that this conveys the intention, looks like an “ordinary” comparison of functions, but reminds the reader that it is about an upper bound (so one will not go on to conclude that $3n=2n$ since both “equal” $O(n)$…)

September 5, 2012 7:48 am

Besides topology, Ш is also used in computer science to denote the shuffle operation on strings.

September 5, 2012 8:18 am

Cantor was a paranoid anti-semitic …

• September 6, 2012 4:07 pm

Can you substantiate the latter part? Wikipedia’s bio mentions an anti-semitic letter by his brother, but apart from references to E.T. Bell’s account (as being unreliable), I can’t easily find such a reference. I was influenced greatly as a child by Hugh and Lillian Lieber’s book on “S.A.M.” and Cantor, and they were Jewish.

September 5, 2012 9:50 am

Amir suggests $\lambda n. f(n) \in O(n)$, but formally this doesn’t help at all, since the lambda binding of n doesn’t include O(n). The correct solution is to note that O is a function with type $O : (N^N) -> 2^(N^N)$ (it maps a function to a set of functions) and therefore its argument must be a function, so formally we should write $(n \mapsto 3n) \in O(n \mapsto n)$. I prefer $x \mapsto y$, but $\lambda x. y$ is equivalent — it just substitutes an meaningless Greek letter for a somewhat meaningful arrow.

September 5, 2012 10:14 am

One consideration not mentioned is the need for readers to have a word/pronunciation to go with the use of a new symbol. Many years ago I read a paper with an unfamiliar symbol and found that I couldn’t maintain focus on the content of the text without substituting a pronounceable sound to go with the symbol.

September 5, 2012 10:22 am

@KWRegan: Have you been confused by a usage that you originally took to be a different meaning, either of a symbol or a term?

If you rationalize, you lose your roots.

• September 6, 2012 4:08 pm

Yes. Can’t immediately think of an example. Love your quip…

13. September 6, 2012 5:10 am

I have thought about this idea of symbology and came to the conclusion that it really comes down to a question of how many distinict symbols can be represented in some area. The idea was actually driven with respect to Cantor and the thought that continously variable symbols would be the surest way to get past Godel, since one could in principle represent real numbers as elements of a system of logic. Unfortunately, one can’t actually contemplate having infinite precision in the position of the ink, so invariably some symbols would begin to blur and become ambiguously similar to others. This leaves one forced to use some sort of abstract formalism to represent a real number. Unfortunately, this puts one in the situation were there are not enough abstract representations using discrete symbols to show all the real numbers simultananeously. So now we find ourselves in a horrible pickle.

September 8, 2012 4:31 am

… so much so that some folks around here have even wondered if Cantor’s proof that R is uncountable was right!

September 6, 2012 11:26 am

Hebrew letters shouldn’t be used for mathematics variables, because they already have meanings assigned to them, unlike all other languages. In the language of mathematics, they are not variables – they are constants. Greek is the perfect alphabet for math.

It is interesting that Cantor chose the Hebrew letter Aleph for infinity, since in Hebrew, aleph represents God, Who is infinite in that He has no limits.

September 6, 2012 11:50 am

Greek letters also have traditional constant assignations, exactly like Hebrew.

September 6, 2012 12:19 pm

Not exactly like Hebrew.

Pi is a Greek letter representing the sound p. Mathematicians traditionally use this letter to represent the area of a circle of radius 1, but this meaning is not intrinsic to the letter.

The Hebrew letter Peh represents the sound p (and f), but also means “mouth”. The meaning “mouth” is intrinsic to the letter.

September 6, 2012 10:03 pm

I think using obscure characters is a terrible idea. It obfuscates what is going on. Using aleph_0 for the cardinality of N is profoundly dumb: |N| would work just as well, and is far far easier to write.

September 7, 2012 6:43 am

Backwards E, Upside down A, Sideways 8 are used in math all the time. Maybe mathematicians should use this idea for other things.

September 7, 2012 8:48 am

i’ve run into trouble searching for online versions of algorithms online.

18. September 8, 2012 8:51 am

“We would love to see creative new names for these devices, but names grow by association and diffusion.”

I’m rather fond of the slang name for a tablet device (which I’ve seen on UK site the register.co.uk and is perhaps their own) : “fondleslab”.

19. September 8, 2012 2:17 pm

why discete symbolization?