Constructing The Counting Numbers

AllPages RecentChanges Links to this page Edit this page Search Entry portal Advice For New Users

Counting numbers.

This, by the way, isn't an historical reconstruction. This isn't how number came to be, and most likely it's not even the right order of emergence of the different ideas. This is different.

So let's talk about collections of things. We're going to be pretty simplistic here, but we'll talk about collections of discrete things. We can have a collection of cars, or a collection of pieces of fruit, or a collection of species of fruit, or whatever. The items in the collection don't need to be the same type of thing, and some could be concrete, and others abstract. We could have a collection with a car, a dream, and the state of mind of confusion. We would say that such a collection has three things in it, but we don't yet know what numbers are, so we can't talk about "three."

Well, obviously we do know what numbers are, but I'm trying to get at the idea of number in a semi-formal fashion. We want to talk about the number of things in a collection, so we need to be a little careful. Does "water" count as one thing? Or is it gazillions of things, because there are so many molecules? Well, I want to be naive and simplistic, so if you say "water" then I'll interpret that as "the idea of water" and count it as a single item. Better perhaps if you don't think of water, and only think about things that are obviously single things.

So consider the following collections:

• { A car, Nimrod the hunter, The colour Green }
• { An Apple, The colour Orange, A Grape }
• { A Chair, A Table, A Stool }
• { A Book, A Candle, A Key }
• { A Tiger, A Lion, An Elephant }
• { An Uncle, An Aunt, A Cousin }

There's something that all these collections have in common. In particular, if you take two of them you can pair off the items in one with the items in the other, leaving nothing out from either side. There is a matching between the items in the two collections.

So in this regard, each collection is equivalent to the others. Using informal language, and anticipating where we're going, we'd say that each collection has the same number of items. I don't want to do that . I want to say that for any pair of these collections, the items can be matched with each other.

(By the way, as we go on we will be piling abstraction on abstraction, and we'll have collections of collections of collections, etc. Don't panic - mostly you won't need to worry about retracing the details.)

I've been taking a long time over this, I know. Bear with me. We're going to do, in detail, an operation you're most likely not familiar with, so I'm going to do it here, with something you're familiar with. Later we'll be following through the same process when we're in unfamiliar territory - the practice now is necessary.

So we're going to declare that in this context, two collections are said to be "equivalent" (and that will be a technical term) if the items of one can be matched with the items in the other with none left over in either.

Equivalence Relations

I need to talk about the term "Equivalence Relation."

A problem a lot of people have with this sort of thing is that people will use their understanding of the ordinary words. "Equivalent" will mean something to you, and you will naturally use your understanding of that term. It's important that you don't do that. It's important that you only use the information you are explicitly given. So we'll just take a quick excursion into what equivalence relations are.

Suppose we have a collection of things. An equivalence relation, basically, says that some things are equivalent to others. We can think of an equivalence relation as a box with two slots on the front and two lights on top. The lights are labelled "Yes" and "No", and when you put an item in each slot it lights the appropriate light to say whether they are going to be considered "equivalent."

There's not much we know about this, except:

• If you put the same thing in each slot, you get "Yes"
• For any two things, putting them in either way round gives the same result.
• Also, time order is irrelevant - everything is thought of as instantaneous.
• If a and b make "Yes" light up, and b and c make "Yes" light up,
  then a and c will make "Yes" light up.

• For all a, a is equivalent to a. (reflexive)
• a is equivalent to b if (and only if) b is equivalent to a (symmetric)
• If a is equivalent to b, and b is equivalent to c,
  then a is equivalent to c. (transitive)

• If R is an equivalence relation, then
• Rule 1: For all a, R(a,a) = T
• Rule 2: R(a,b) = R(b,a)
• Rule 3: R(a,b) = T and R(b,c) = T implies that R(a,c) = T

Here we are using R both to denote a function from pairs to the set {T, F}, and also to itself be a set of pairs. The idea is that the set R consists of those pairs (a,b) for which the function R takes the value T. This mixing of notations between equivalent forms can be confusing, but can be very convenient.

So in summary, the following are all equivalent:

• R(a,b) = T
• R(a,b)
• a R b
• (a,b) $\in$ R

Exercise 1:

Suppose R is an equivalence relation, and we use lower case letters to refer to things of interest.

• 1a) Suppose R(a,b), R(a,c), and R(c,d). Prove that R(b,d).
• 1b) Suppose now that it's not the case that R(x,y), but it is
  the case that R(y,z). Prove that it's not the case
  that R(x,z).

OK, so let's get back to our collections of things, and saying that two of them are "equivalent" if we can pair the items in one collection with the items of the other, and have nothing left over from either collection. Such a pairing off is called a "matching" between the two collections. Note that this is simply item by item, with no regard as to what the items might be.

So we say that two collections are "equivalent" if there's a matching (a pairing off) between them, but is "There's a matching" actually an equivalence relation? What do we mean by that?

Well, recall what it means to be an equivalence relation. Let's say that given two collections, A and B, if there's a matching then we'll write that as M(A,B). We want to know if M satisfies the necessary conditions to be an equivalence relation. That means we need to know that:

Exercise 2:

• Show that M is an equivalence relation.

• For all A, B, and C, then
• M(A,A)
• M(A,B) implies M(B,A)
• M(A,B) and M(B,C) implies M(A,C)

Using Equivalence Classes

A piece of notation - I'm going to start writing collections using braces. Later I might retrace my steps and talk more properly about "sets," but for now I'll take some things for granted.

So now let's take a collection. Suppose we have this one:

• { Apple, Table }

• { Car, Book }

• { Telephone, Computer }

You could picture things that are equivalent as being joined by a bit of string, then you can take one and start pulling. The things that are equivalent come with you, and you end up with the entire equivalence class.

So, once again looking ahead, all the things with two items are equivalent. Together they form an equivalence class.

So we have equivalence classes, lots of them. Again, allowing ourselves to borrow from the future, we get

• the equivalence class of all the collections with exactly one item,
• the equivalence class of all the collections with exactly two items,
• the equivalence class of all the collections with exactly three items,

So we have the equivalence classes. What next?

Defining addition.

With our collections (and soon I'll forget to call them collections and start calling them sets) we can define addition. If I have a heap of things, and another heap of things, I can add the two heaps by just creating a single heap made up of all the things. (Yes, this seems obvious, bear with me. As you might imagine, it gets complicated ...)

So we take the collection { Car, Book } and the collection { Apple, Telephone, Dream } and form the combined collection to get { Car, Book, Apple, Telephone, Dream }. Obviously (for some definition of "obvious") we have just added two and three to get five.

Only, we haven't. We've taken two collections and formed a new one, consisting of all the members of the original collections. This is where we start talking about sets - we have taken two specific sets and formed their union. Even then there's a problem, because if there were an item that occurred in both sets, the result would not match our normal concept of addition, because we don't get to count the same thing twice in our union.

Thus:

• { Car, Book } "+" { Book, Dream } is { Car, Book, Dream }

But this isn't addition of numbers. This is unions of sets, and specific sets at that. But here's the fun bit. We can use this to define "addition" of the equivalence classes.

So how does that work?

We want to define addition of "numbers", and "numbers" are the equivalence classes. So given two equivalence classes, we need to define another equivalence class that is the "sum" of them.

So take two equivalence classes, $E_1$ and $E_2.$ Recall that an equivalence class is a collection of sets, each equivalent to the others. So $E_1$ is a collection of sets, and $E_2$ is a collection of sets.

Remember, when we take the discriminated union of two sets we tag them so we don't get any confusion from overlaps. A red car from one set and a red car from the other are still recognised as different things, because one is tagged "From the left set" and the other is tagged "From the right set".

Take a representative of each. So take $e_1$ from $E_1,$ and $e_2$ from $E_2.$ So now we have sets, and we know how to take the union of sets. In particular, we know how to take the discriminated union of two sets.

So we do that. We take the discriminated union of $e_1$ and $e_2,$ and we get another set. Call it "s".

But that's a set, and we need an equivalent class. But that's easy. The set "s" belongs to some equivalent class, so let's just use that.

So

       E_1   "+"   E_2   c/f   F

        |           |          ^
        V           V          |

       e_1    u    e_2   -->   s

That gives us a rule that takes two equivalence classes and produces another. But there's potentially a problem. What if the particular representatives we choose produce a different result? That would mean that "adding" two equivalence classes doesn't always give the same result. That would be a disaster.

So here's the challenge: Prove that it doesn't go wrong.

To be more specific:

• Let M be the equivalence relation "There is a matching",
  and let A, B, C, and D be collections.
• Prove that if M(A,B) and M(C,D), then
• M( A u C , B u D )

This term "Well defined" is an interesting one, and lots of people have trouble over it. The problem is that just because you define something to be so, that doesn't mean the definition makes sense. You always need to check that nothing will go wrong. Too often we define a term expecting it to capture our intuition, only to find that we've got too much, or got too little, or it harbours an inconsistency. In this case we define a result by taking two specific representatives. What if we chose different representatives - might we get a different answer? That needs to be checked. If the answer depends on the specific choices, then the definition is not a good one - there would be no consistency. A tricky idea.

To re-phrase that, suppose we want to "add" two equivalence classes. We choose any representative of each, take the discriminated union, and look at the equivalence class of the result. It will always be the same. That means that this process gives a well-defined result.

Pause ...

Summarising ...

So what do we have? We have these equivalence classes, and we have a concept of addition of equivalence classes. And a funny thing happens. The equivalence classes, along with this defined "addition", corresponds to the counting numbers that we know and love.

Again, drawing from our more advanced knowledge, the equivalence class to which the collection { Car, Book, Computer } belongs can be thought of more simply as the number "3". After all, all the sets in that equivalence class have exactly 3 items in them.

Similarly, the equivalence class to which the set { Chair } belongs can be thought of more simply as the number "1". If we use those specific sets and take the discriminated union we get:

• { Car, Book, Computer, Chair }

So 3+1=4. And that's good.

What we have is a formal construction of a thing. This thing is a collection of equivalence classes, along with a way of combining two equivalence classes to get another.

Brief meta-discussion ...

All the above is going to seem really picky, and possibly quite tedious. And I guess that's fair enough. The thing is, we've now laid the foundations for the next three or four stages. We'll use these ideas to build the integers, then to build the rationals. Then we'll take a side-excursion to talk about sequences, before launching into a construction of the reals.

In two different ways. Then another. And probably another.

But we really need the idea of an equivalence relation, and from that an equivalence class. Then we need the idea of operations on equivalence classes by using representatives and checking that this is well defined. We've now met these ideas in the process of building the counting numbers, something most people are familiar with. We'll practice again in familiar territory, but we will be going into the unknown. (Unless you already know this, in which case, why are you reading?)

Next steps

So we've constructed the counting numbers - they are equivalence classes of sets under the equivalence of "There is a matching." To add two counting numbers:

• Each number is an equivalence class
• Take a representative of each equivalence class
• Form the discriminated union of the representatives
• Take the equivalence class of that union
• That's a number, and that's our result.

Instead we'll forge on and look at the constructing the integers.