[FOM] Which is clearer, "integer" or "symbol"?

Vaughan Pratt pratt at cs.stanford.edu
Sun Jan 2 16:30:29 EST 2011


A third alternative is "word."  There is no mathematical reason to 
distinguish the monoid of natural numbers from the free monoid on one 
generator, aka words over a one-letter alphabet.  And there is no 
natural reason to limit alphabet size to one, in fact tally notation is 
downright inconvenient compared to two, ten, 16, or 26.

Most of us are exposed to and learn words before we learn to count. 
Instead of spending hundreds of pages getting ready to prove 1 + 1 = 2, 
Russell and Whitehead could have taken the words they were communicating 
with as illustrative of the concept of "word," developed an elementary 
theory of words under concatenation, defined a natural number to be a 
word over the alphabet {I}, and defined addition to be synonymous with 
concatenation.

This would have made short work of the theorem I + I = II.

For integers one can do a similar thing with the free group on one 
generator I, writing say J for its complement -I (more generally B = -A, 
D = -C, etc.), with the complication that not all words are well-formed. 
  A word is well-formed when it contains no adjacent complementary 
pairs.  Theorem: In the one-letter case, well-formed iff homogeneous 
(all I's or all J's).

 From there it's an easy step to abelian groups and Z^n as the free 
abelian group on n generators.  Very fundamental.

The irony is that Whitehead was one of the earliest proponents of 
universal algebra.  It is too bad the central importance of free 
algebras to universal algebra was not clearer in those days.  The 
concept is obvious today, and its instantiation in the category of 
monoids even more so.

Vaughan Pratt


More information about the FOM mailing list