# Constructing The Counting Numbers

 So the other day a friend asked me to go over again the stuff I'd been talking about some time earlier - how to construct the real numbers. I couldn't remember what I'd been saying, so I figured the thing to do would be to start over again. As I was doing so it occurred to me that I really should write it all down. Not least, my friend would then be able to review it when I wasn't around, but maybe other people would also find it interesting. If I could persuade a few others to read it, then maybe their comments would help improve it, and I might, in the end, have something worth having. So this is my attempt to write it all down. It's not finished, and it's not in a single, linear, logical order, because this is just how it comes. And the formatting needs fixing, and there will be mistakes. However, unless you start, nothing will get done. So this is a start. It's not intended to be perfect at this stage. If no one wants it then perfecting it, or even polishing it, would be wasted effort. If enough people are interested then I'll look to refine it.
We're going to talk about constructing the real numbers. If that doesn't mean much to you, with any luck it will become clear as we go. To begin with, though, we need to talk about numbers.

## 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 }
You can argue about the philosophy of these things, but I don't want to get into sophisticated discussions of what things are, and so on. Let's just be simplistic.

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."

• 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.
Re-phrasing that:

• 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)
 This version is more technical, and we're using the idea that R is a function that takes a pair and, for that pair, returns either "Yes" or "No", or, equivalently, "T" or "F", thinking of "T" as "True" and "F" as "False". If you go down that route it's very easy to get into discussions about Truth with a capital "T". I don't want to go there, we just want to know, given two things, are they equivalent. However, it's important to realise that given two things there are only two options. They are equivalent, or they aren't.
And another rephrasing, this time in symbols:

• 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
For brevity we will sometimes simply write R(a,b) as a shorthand for R(a,b) = T. Further, when convenient, we can write the R in between things, similar to the way we put an equals sign between the things being said to be equal. Sometimes we use the symbol $\equiv$ in a similar way to using the equals sign, but meaning "equivalent" rather than "equal." I know, some of this sounds really obvious, but if I don't say it now I'll have to say it later when you've got confused. I'll probably say it later anyway.

 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
So now we can start to test your understanding of the formal nature of what we're doing. Here are a few exercises:

### 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).
Remember, you can't use your intuitive understanding of what an equivalence relation is, you can only use the technical definition - you can only use rules 1, 2, and 3 as quoted above.

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:

In other words, show that:

• 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 }
We can find another collection that's equivalent to that:

• { Car, Book }
Then we can find another:

• { Telephone, Computer }
And so on. In fact, we can, conceptually, think of all the collections that are equivalent to { Car, Book }. We can then think of that entire collection - all the things that are equivalent to this one collection. And because of the definition of "Equivalence Relation", if they're all equivalent to the seed collection, then they are all equivalent to each other as well.

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

and so on.

So we have the equivalence classes. What next?

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 }
 OK, more technically ... Given two sets A and B, we form discriminated sets A' and B' as follows: A' = { (a,"Blue") : a in A } B' = { (b,"Green") : b in B } We haven't really coloured them, we've tagged them. Then the discriminated union is: D = { d : d in A' or d in B' } Note now that A' consists of things that are themselves pairs, so we are more abstract. I did warn you that we'd get levels and levels of abstractions. Stay with me ...
That would be 2+2=3, and that's not a good idea. We actually get around this by colouring all the things in one collection blue, and all the things in the other collection green, and then we can tell the difference. There's a technical term for this - is called a "discriminated union" and it avoids the problem of repeated items.

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 will mean that if A and B are in the same equivalence class, E_1, and C and D are in the same equivalence class, E_2, then the results of the discriminated unions are equivalent, so they are in the same equivalence class.

 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 }
And guess what - that is in the equivalence class most easily just called "4".

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:

We could now show that what we have is equivalent to the system that arises from the Peano axioms. We could define multiplication.
 My thanks to snapey1979 for comments on an early draft.

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