Saturday, August 14, 2004

non-numeric algebras

The algebra of algebra textbooks is the branch of mathematics where you manipulate numbers by exploiting various rules. For example, if we are given the equation x-1=0, we can exploit the following rule to find out what x is:

inverse of subtraction
: a-b+b=a

We add 1 to both sides and find out that x=1. Here are some more rules for the algebra of numbers, but by no means all:

identity: a+0=a, a*1=a
commutativity: a+b=b+a, a*b=b*a
associativity: (a+b)+c=a+(b+c), (a*b)*c=a*(b*c)

There are lots of algebras. Many of them are algebras over different sets of numbers and many of them are not. The set of values that an algebra operates on is called the sort. For common high school algebra the sort is the complex numbers.

There is also an algebra over the sort of sets. The objects are sets and the operations are union, intersection, and complement of sets. The rules look similar to the rules for the algebra of complex numbers. In fact, if we use the symbol "+" to stand for union and "*" to stand for intersection, the rules of commutativity and associativity look identical for sets as for numbers. If we also let "0" stand for the empty set and "1" stand for the universal set, then the identity rules looks the same too. The arithmetic rule of distribution also looks the same:

distribution of *: a*(b+c)=(a*b)+(a*c)

however, the algebra of sets adds the complementary rule

distribution of +: a+(b*c)=(a+b)*(a+c)

This rule doesn't hold for numbers, only sets. If we let "-a" stand for the set complement of a, then the rule of double negation holds for both systems:

double negation: -(-a) = a

The minus sign represents an inverse operation in both algebras. An
inverse operation is one that can be combined with another operation to
produce the identity element for that operation:

inverse: a+(-a)=1, a*(-a)=0

Obviously these inverse rules apply only for sets, not numbers.

Another algebra is the algebra of functions. Let f be a function, a mapping that takes a number and returns a number. The value of f at x is written f(x). Let g be a function also. Then f*g (read "f compose g") is another function. Since f*g is a function, we can find the value of x at f*g and we write it (f*g)(x). It's defined as the value of f at the value of g at x, or (f*g)(x)=f(g(x)). The operation of function composition forms an algebra over the sort of functions with the following rules (I'm leaving out some important restrictions here. Exercise: what restrictions?):

identity:f*1=1*f=f
associativity:f*(g*h)=(f*g)*h

The symbol "1" represents the identity function --the function such that for all x, 1(x)=x. Since function composition is not commutative it is necessary to spell out both the left and right identity rules. Some algebras have an identity element that only works on the left or only on the right.

There is also an algebra of strings with concatenation. A string is just a sequence of letters like "abc" or "xyz". Concatenation (represented by the "+" sign joins two strings together: "abc" + "xyz"="abcxyz". The operation of string concatenation forms an algebra over the sort of strings. I'll leave the rules as an exercise for the reader.

CORRECTION: I'm sure many of my readers noticed that I made some errors in the section on the algebra of sets. First, traditionally an inverse for a binary operation is another binary operation. That is, the inverse for a+b is a-b, not just -b. I was being too terse and failed to distinguish between an inverse operation and an operation that produces an inverse of an element.

Second, it should have been clear from my definition of "inverse" and my rule inverse, that set complement is not a true inverse. If a and -a are inverses with respect to an operation +, then a+(-a)=0, where 0 is the identity element for +. With sets, a+(-a)=1, which is not the identity element for +, it is the identity for *.

For fifteen years, I have just known that Boolean algebras (the algebra of sets is a Boolean algebra) have true inverses. I never thought to question it. Now it seems obvious that they don't. It's like finding out that the world is flat after all.

No comments: