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.