Most recent change of ConstructingTheCountingNumbers

Edit made on February 23, 2015 by ColinWright at 13:07:15

Deleted text in red / Inserted text in green

WM
HEADERS_END
[[[>50
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."

[[[>50
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"
* It doesn't matter which order you put the things in.
* 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)

[[[>50 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)/
** Rule 1: For all /a,/ /R(a,a)/=/*T*/
** Rule 2: /R(a,b)/ /=/ /R(b,a)/
** Rule 3: /R(a,b)/ and /R(b,c)/ implies that /R(a,c)/
** Rule 3: /R(a,b)/=/*T*/ and /R(b,c)/=/*T*/ implies that /R(a,c)/=/*T*/

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. We won't do that. Sometimes we use the symbol
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
EQN:\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.

[[[>50 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)/ EQN:\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:

* Show that M is an equivalence relation.

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

[[[>50 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

* 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,

and so on.

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.

----
"We've taken two specific sets and formed their union" Suggest: ""
----

Only, we haven't. we've taken two collections and formed a new one,
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 }

[[[>50 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
So take two equivalence classes, EQN:E_1 and EQN: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
others. So EQN:E_1 is a collection of sets, and EQN:E_2 is a collection of
sets.

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.
[[[>50 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 EQN:e_1 from EQN:E_1, and EQN:e_2 from
EQN: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_1, and
So we do that. We take the discriminated union of EQN:e_1 and EQN: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.

[[[>50 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:

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

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

Instead we'll forge on and look at the integers, and how to construct them

----
My thanks to snapey1979 for comments on an early draft.
Instead we'll forge on and look at the constructing the integers.