Notation And Thinking
Does notation shape our thinking?
Kenneth Iverson was a mathematician who is most famous for designing APL. This was the name of his programming language, and it cleverly stood for “A Programming Language.” The language is unique—unlike almost any other language—and contains many powerful and interesting ideas. He won the 1979 Turing Award for this and related work.
Today I want to talk about notation in mathematics and theory, and how notation can play a role in our thinking.
When I was a junior faculty member at Yale University, in the early 1970′s, APL was the language we used in our beginning programming class. The reason we used this language was simple: Alan Perlis, the leader of the department, loved the language. I was never completely sure why Alan loved it, but he did. And so we used it to teach our beginning students how to program.
Iverson had created his language first as a notation for describing complex digital systems. The notation was so powerful that even a complex object like a processor could be written in his language in relatively few lines of code: the lines might be close to unreadable, but they were few. Later the language was implemented and had a small but strong set of believers. Clearly, Alan was one of them who once said:
A language that doesn’t affect the way you think about programming, is not worth knowing.
The language APL was great for working with vectors, matrices, and even higher order objects. It had an almost uncountable number of built-in symbols that could do powerful operations on these objects. For example, a program to find all the primes below is:
This is typical APL: very succinct, lots of powerful operators, and no keywords. The explanation of this program is here.
One comment about APL is:
Famous for its enormous character set, and for being able to write whole accounting packages or air traffic control systems with a few incomprehensible key strokes.
Not quite right, not very nice, but this comment actually captures the spirit of Iverson’s creation: make complex functions expressible as very short expressions was an interesting idea. For example, Michael Gertelman has written Conway’s Game of Life as one line of APL:
This should make it clear that this language was very powerful, perhaps too powerful.
When I had to learn APL in order to teach the beginning class I decided to start a project on building a better implementation. The standard implement of the language was as an interpreter and one of my Yale Ph.D. students, Tim Budd, eventually wrote a compiler for APL. We also proved in modern terms a theorem about the one liners of the language. Each one liner could be implemented in logspace: this was not completely trivial, since the operators were so powerful. Perhaps another time I will discuss this work in more detail. For now see this for Tim’s book on his compiler.
Let’s turn to discuss various notations used in math and theory.
It is hard to imagine but there was a time when mathematicians did not even have basic symbols to express their ideas. Many believe that the notation helps to shape the way that you think, clearly without basic symbols modern mathematics would be impossible. Or at least extremely difficult.
Robert Recorde is credited with introducing the equality symbol in 1557. He said
to avoid the tedious repetition of these words: “is equal to,” I will set (as I do often in work use) a pair of parallels of one length (thus ), because no two things can be more equal.
René Descartes is know for the first use of superscripts to denote powers:
François Viète introduced the idea of using vowels for unknowns and consonants for known quantities. Descartes changed this to: use letters at the end of the alphabet for unknowns and letters at the beginning for knowns.
Descartes thought that would be equally used by mathematicians. But it is this and that The story—may be a legend only—is that there is a reason that became the dominant letter to denote an unknown. Printers had to set Descartes papers in type, and they used many ‘s ‘s, since the French language uses them quite a bit. But it almost never uses , so Descartes’ La Géométrie used as the variable most of the time.
Isaac Newton and Gottfried Leibniz invented the calculus. There is a controversy that continues to this day on who invented what and who invented what first. This is sometimes called the calculus war—see here for some information.
Independent of who invented what they did use different notations, at least that is without controversy. Newton used the dot notation and Leibniz the differential notation. Thus Newton would write while Leibniz would write for the same thing. The clear winner, most agree, is the better notion of Leibniz. It is even claimed that the British mathematicians by sticking to Newton’s poorer notation lagged behind the rest of Europe for decades.
Leonhard Euler introduced many of the common symbols and notation we still use today. He used and for the famous constants and for the square root of . For summation Euler used and also introduced the notation for functions: . One can look at some his old papers and see equations and expressions that look quite modern—of course they are old, but look modern because we still use his notation.
Johann Gauss introduced many ideas and proved many great theorems, but one of his most important contributions concerns the congruence notion. Leonhard Euler earlier introduced the notion, but without Gauss’s brilliant notation for congruences, they would not be so easy to work with. Writing
is just magic. It looks like an equation, can be manipulated like an equation—well almost—and is an immensely powerful notation.
Paul Dirac introduced in 1939 his famous notation for vectors. The so called bra-ket notation is used in quantum everything. It is a neat notation that takes some getting used to, but seems very powerful. I wonder why it is not used all through linear algebra. A simple example is:
The power of the notation is that can be a symbol, expression, or even words that describe the state values.
For a neater example, the outer-product of a vector with itself used in the APL program for primes above is written this way in Dirac notation:
which flips around the inner product . Now to multiply the matrix formed by the outer product by a row vector on the left and a column vector on the right, we write
The bra-kets then associate to reveal that this is the same as multiplying two inner products. Another neat feature is that versus captures the notion of a dual vector, and when has complex entries, the notation implicitly complex-conjugates them.
Albert Einstein introduced a notation to make his General Relativity equations more succinct. I have never used the notation, so I hope I can get it right. According to his rule, when an index variable appears twice in a single term, once as a superscript and once as a subscript, then it implies a summation over all possible values. For instance,
where are not powers but objects.
Dick Karp introduced the notation to complexity theory in our joint paper on the Karp-Lipton Theorem. Even though the notation was his invention, as a co-author I will take some credit.
Not all notation that we use is great, some may even be called “bad.” I would prefer to call these good with a question mark. Perhaps the power of notation is up to each individual to decide. In any event here a few “good?” notations.
John von Neumann was one of the great mathematicians of the last century, who helped invent the modern computer. He once introduced the notion
where the number of parentheses modified the function . It does not matter what they denoted, the notation could only be used by a brilliant mind like von Neumann’s. This notation is long gone as used by von Neumann, but in ideal theory is not the same as . Oh well.
The letter for pi is is fine, but maybe it denotes the wrong number? Since denotes the full unit circle and occurs all the time in physics, maybe we should have used the symbol for that number? Lance Fortnow and Bill Gasarch once posted about this here, with many interesting comments.
Why is the charge of the electron negative? Evidently it is because Benjamin Franklin believed the flow of an unseen fluid was opposite to the direction the electron particles were actually going.
Why has humanity been unable to establish that means proper subset and only means subset, by analogy to and ? Hence for proper subset one often resorts to the inelegant notation.
I will end with one example of notation that many feel strongly is “good?”: to denote the derivative of a function. See here for a lively discussion.
Does good notation help make mathematics easier? Are there some notions that are in need of some better notation? Would you rather discover a great theorem or invent a great notation?