A Little Arithmetic

[stoutfellow]

p_o_u_n_c_e_r wondered about the peculiar algebra I've set my Master's student to working on. Here's an attempt to explain the underlying idea.

Everything, both pedagogically and logically, starts with counting. We learn arithmetic by talking about collections of things: three strawberries, four horses, and what-have-you. We learn what "three" is by seeing lots of collections of, well, three things. We learn to add by putting collections together: a collection of three rocks, and another collection of four rocks, yields a collection of seven rocks. Multiplication is a little more complicated, but those collections of things always lie in the background.

Let's do this a little more carefully. The first concept is that of "having as many elements as", and that - logically as well as psychologically - comes before any actual concept of number. We think about sets, and we divide them up into classes: here are all the sets with just as many elements as {a,b,c}, there are the sets with as many elements as {red,blue}, and so on. We give those classes names: the former one is "three", and the latter is "two". These names we call "numbers".

Now, how do we add numbers? Well, to add "three" and "two", take a set A from the class "three" - say, {a,b,c} - and a set B from the class "two" - say {red, blue} - and put them together - in technical terms, take their union A U B, {a,b,c,red,blue}. Then you ask which class set this belongs to: "five". No matter which sets you take from the two classes, their union will belong to the class "five". (Well, almost: the two sets have to be chosen so as to have no overlap. Technically, they have to be "disjoint".) And, in essence, that's all there is to addition; it's derived from the concept of "disjoint union". The commutative and associative laws of addition come from the fact that A U B and B U A have the same number of elements, as do (A U B) U C and A U (B U C). [Don't let the symbols throw you; think about collections of objects!]

What about multiplication? Here we go beyond the elementary classroom. Given two sets A and B, we can form their "Cartesian product" AxB, whose elements are ordered pairs (x,y), where x is an element of A and y is an element of B. In the example above, the Cartesian product is {(a,red),(b,red),(c,red),(a,blue), (b,blue),(c,blue)}. What class does this one belong to? "Six", of course. And that's where multiplication comes from: to take the product of two numbers, pick a set from each class, take the Cartesian product, and determine which class that belongs to. The associative and commutative laws of multiplication follow from the behavior of Cartesian products. (Again, just think about it: AxB and BxA obviously have the same number of elements, and likewise for (AxB)xC and Ax(BxC).) The distributive law has to do with the interaction between Cartesian products and disjoint unions; if you just play around with a few examples, you'll see it.

Now we get a little stickier. How do you take powers? How, in other words, do you represent, say, 2^3 in terms of sets? Here, we need to introduce sets of functions. Look at our set of three elements, and consider the functions from it to our set of two elements. There turn out to be 2^3=8 possibilities, as follows:
f1(a)=f1(b)=f1(c)=red
f2(a)=f2(b)=red, f2(c)=blue
f3(a)=red,f3(b)=blue,f3(c)=red
f4(a)=red,f4(b)=f4(c)=blue
f5(a)=blue,f5(b)=f5(c)=red
f6(a)=blue,f6(b)=red,f6(c)=blue
f7(a)=f7(b)=blue,f7(c)=red
f8(a)=f8(b)=f8(c)=blue

You see, there are two choices of places for a to go, two choices for b, and two choices for c, yielding 2x2x2=2^3 choices all told. In general, then, if you have two sets A and B, the exponential set A^B is the set of all functions from B to A; if A has m elements and B has n, then A^B has m^n elements.

The laws of exponents are a little harder to derive, here, but they're possible. For example, the law that m^(n+r)=m^n x m^r basically says that, if you have three sets A,B,C, to describe a function from B U C to A, all you have to do is describe a function from B to A and a function from C to A.

So, the basics of arithmetic can be described purely in terms of sets, using three concepts: disjoint union, Cartesian product, and the exponential set. Where things get interesting is, as has been realized over the last sixty years or so, that these concepts make sense, and behave in the right ways, in other contexts than just sets. That's a story for another post, though.