Putting sets together

The goal of our program here is to understand arithmetic as an operation that “has something we do with sets.” This means that before we go further, I’ve got to explain the structure of sets a little more.

I’ve got to be honest here: part of the reason it took me so long to write this post is because making basic set theory interesting is hard. My impression of it upon first exposure was that it was an attempt to take something extremely simple and obscure it with elaborate jargon. Actually the truth is only slightly different: it’s an attempt to take something extremely simple and describe it very precisely. The jargon is just a side effect.

This is just a blog, not a serious attempt to build a foundation for the entirety of deductive thought, so I can afford to be a bit looser with my terms than a real set theorist. I hope I’ll be able to explain enough to get to the good part, without mystifying folks (on the one hand) or insulting their intelligence (on the other).

Unions

The simplest two operations we can define on sets are the union and the intersection. The union of two sets is just the set of everything contained in either one. This is a pretty common operation in ordinary life, and it’s pretty common in mathematics too.

  • The union of “all the undergrad students at my university” and “all the grad students at my university” is “all the students at my university”.
  • The union of “the fingers on my left hand” and “the fingers on my right hand” is “all my fingers”.
  • The union of {0,1,2} and {0,4} is {0,1,2,4}.
  • The union of “my cats” and “my dogs” is “my cats” (since I don’t have any dogs).

There’s a notation for this: the union of sets A and B is called A∪B.

Since the union involves “putting two sets together”, you might think we’ve reached our goal already. Just define addition to work so that if set A has, say, 3 elements, and set B has 2 elements, their union has 3+2 elements.

Sadly, this won’t quite work—at least not in the simple form presented. Just look at the third example above: the set {0,1,2} has 3 elements, and the set {0,4} has 2 elements, but I don’t really think we want to say that {0,1,2,4} has 3+2 elements. More to the point, {0,1,2}∪{0,4} isn’t even the same size as something like {0,1,2}∪{3,4}. Our ‘operation’ isn’t even well-defined, let alone the one we want.

But this is the right track. Addition is about somehow putting two sets together—that’s the first use we ever get for it in elementary school: answering questions like, “If you have four apples, and Bobby has three apples, then how many apples do the two of you have?”

If you and Bobby have joint custody of an apple, addition won’t let you answer that question either. That’s not addition’s fault.

It actually wouldn’t be to hard to insert some sort of hack to turn the union into something we could work with. For example, I’ve seen at least one approach that defined addition as just giving an upper bound on the size of a union. But if we wanted to live with clever hacks, we’d be happy with the recursive definition of addition. So let’s keep looking.

Intersections

The intersection of two sets is the set of those things contained in both of them. Again, this is a pretty useful operation in everyday life.

  • The intersection of “all the paperclips in the world” and “all the stuff in my house” is “all the paperclips in my house”.
  • The intersection of {0,1,2,3} and {0,2,4,6} is {0,2}.
  • The intersection of “all the fingers on my left hand” and “all the fingers on my right hand” is the empty set.

And yet again, notation: the intersection of sets A and B is called A∩B.

If we wanted to go with the approach of hacking on the union operator, this would be the cleanest possible way: declare two sets to be disjoint if their intersection is the empty set. Then say that, if A and B are disjoint sets of size n and m, the sum of n and m is the size of A∪B. A nitpicker might point out that we still have to prove this works—i.e. that if we pick two different disjoint sets, we’ll get the same answer—but that argument isn’t actually very hard. If you have a set the same size as A (let’s call it Y), and one the same size as B (let’s call it Z), then there must be bijections between A and Y and between B and Z, and it’s pretty easy to put them together and get a bijection between A∪B and Y∪Z.

This is very close to my ideal method of defining addition, and in fact I think it’s good enough for right now: + is the unique operator on the natural numbers such that, given two disjoint sets A and B (with sizes given by |A| and |B|),

|A|+|B|=|A∪B|.

I’ll probably refine this a bit later, but first let’s move on to multiplication.

PRODUCTS

Well, at least the name is straightforward.

Suppose you want to buy a car. There are three models for sale, excitingly named A, B, and C. Each one comes in four colors: black, white, red, and jonquil.

You can represent the car models as a set: {A, B, C}. And you can represent the car colors as a set: {red, white, black, jonquil}.

And you can even represent all possible cars you can buy as a set. There’s sort of a standard way of doing this: write the ordered pair of two ‘things’ x and y to be (x,y), and represent “Model C in red”, for instance, as (C,red). Then the set of all possible cars you can buy is

{(A,red), (A,white), (A,black), (A,jonquil), (B,red), (B,white), (B,black), (B,jonquil), (C,red), (C,white), (C,black), (C,jonquil)}.

Another name for this set is the Cartesian product, or the direct product, or just the product of the sets {A, B, C} and {red, white, black, jonquil}. We can also write the product using the symbol ×, so that this example is {A, B, C} × {red, white, black, jonquil}.

One thing worth noting about ordered pairs is that they’re, well, ordered. The ordered pair (Timon,Pumbaa) and the ordered pair (Pumbaa,Timon) aren’t the same thing, for example. Compare this with sets, which are entirely defined by who’s in and who’s out, so that {Timon, Pumbaa} and {Pumbaa, Timon} are the same set.

Anyway, let’s try something slightly different. Instead of sets of sizes 3 and 4, how about the product of 3 and 4 themselves? Well, 3 is the set {0, 1, 2} and 4 is the set {0, 1, 2, 3}. So their product looks like

{(0,0), (0,1), (0,2), (0,3), (1,0), (1,1), (1,2), (1,3), (2,0), (2,1), (2,2), (2,3)}.

And what is the size of that set? It looks like… 12. Also known as 3⋅4.

With this in mind, I propose the following definition: ⋅ is the unique operator on natural numbers such that, for any two finite sets A and B (with their sizes denoted by |A| and |B|),

|A|⋅|B| = |A×B|.

Unlike the previous debacle with the union, in this case there’s nothing to fix. We really will get the same answer no matter which particular sets we choose. (Again, the proof of this involves coming up with an explicit bijection.)

And this definition, to me, is perfect. It captures completely the essence of the product. Describing multiplication as “repeated addition” obscures its real purpose: counting sets of things whose traits vary along two different “dimensions,” such as model and color.

Our first real theorem

Which isn’t to say that multiplication isn’t repeated addition, in the sense that adding repeatedly will get you the right answer. In fact, we can even prove it.

Theorem. If n and m are natural numbers, then nm is the same as n+n+⋅⋅⋅+n, with n added to itself m times over.

Proof. Consider the following list of sets A0, A1, A2, …, Am-1.

  • A0 is the set n×{0} , or {(0,0), (1,0), (2,0), …, (n-1,0)}.
  • A1 is the set n×{1} , or {(0,1), (1,1), (2,1), …, (n-1,1)}.
  • A2 is the set n×{2} , or {(0,2), (1,2), (2,2), …, (n-1,2)}.
  • And so on, up through Am-1.

There are m such sets, and each one has size n. If we want to count their union, there are two different ways. We could notice that all the sets are disjoint, and so by definition their union has size n+n+⋅⋅⋅+n, with n added to itself m times over. Or we could notice that their union is just n×m, and so it must have size nm. So these two numbers must be the same. ∎

A very similar sort of proof will show that addition is just repeated succession.

So if at the end we just get the same answer we’ve always gotten, why did we go through all this work?

Well, my usual reason is: because it’s fun. I like thinking about this sort of thing, breaking down seemingly simple concepts into their constituent atoms and building them back up again. This is all the justification I really need.

But perhaps an even better reason is: because arithmetic is a good case study in the art of abstraction. Most mathematical abstractions proceed in much the same way.

  1. We notice that we often have to solve some type of problem (in this case “How do I know whether this set or that set has more?”)
  2. We explicitly identify the essence of the relationship we’re interested in (bijective correspondence).
  3. We invent simplified stand-ins for the objects of interest, ignoring all properties except the ones we care about (natural numbers as essence of quantity).
  4. We look for structures within our simplified objects that will tell us something about the original objects (addition and multiplication).

This pattern repeats itself over and over again. It’s essentially how all the higher number systems—the integers, rationals, reals, and complex numbers, as well as some more obscure systems—were invented. It’s one way in which new abstractions are invented today. I’m probably going to apply it a few more times right in this blog.

I still haven’t talked about exponents, and I’m still not perfectly happy with this treatment of sums, but I think this is a good stopping point for the current post. More to come on this topic.

Advertisements

3 responses to “Putting sets together

  1. wait until multilinear algebra. then addition is the dimension of the direct sum and multiplication is the dimension of the tensor product

    • Good point—there are a lot of different ways to define the naturals depending on what you want to do with them. That’s actually a decent argument for the axiomatic approach, where you define “the” natural numbers to be any structure satisfying certain properties, and don’t worry too much about what they’re actually made of.

      I’m probably going to cover that when I get to other number systems, since “closure under subtraction” is a much simpler way to explain the integers than actually constructing them.

  2. Pingback: Commutativity and all that | Irrational Inquiries

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s