Deleted text in red / Inserted text in green

WW

WM

HEADERS_END

Suppose we have the counting numbers !/ 0, 1, 2, 3, 4, ... !/ but

we don't have the negative numbers. That means we can

solve the equation /x+5=13,/ but we can't solve /x+13=5./

How can we fix this? What we want is some new, larger system of

things we call "numbers" that somehow extends the existing idea,

and allows these other, similar problems to be solved. Here's

one way to do that.

Consider all pairs /(a,b)/ of counting numbers, and declare that

two pairs /(a,b)/ and /(c,d)/ are equivalent if (and only if) /a+d=b+c./

(The idea here is that /(a,b)/ "means" /a-b,/ but we can't say that

formally because /a-b/ is a possibly-negative integer and at this point

we're supposed to know only about the counting numbers.)

We can check that this is a proper equivalence relation, and so we

have equivalence classes. Any pair /(a,b)/ is in exactly one

equivalence class. It's the equivalence classes we're interested in.

Given two equivalence classes /A/ and /C/ we define their sum /A+C/

as follows. Take a representative /(a,b)/ of /A,/ and a representative

/(c,d)/ of /C,/ and define /A+C/ to be the equivalence class containing

/(a+c,b+d)./ We need to check that the result is always the same no

matter which representatives you choose, but it turns out that this

definition is "well-defined."

Further, given an equivalence class /A/ we define the negative of /A/

as follows. Let /(a,b)/ be any representative of /A/ and define /-A/

to be the equivalence class containing /(b,a)./ Again, we need to

check that it doesn't matter what representative we choose, we always

get the same answer, but again, the concept is well-defined.

We can now show that for any counting number /a/ the equivalence

class that contains /(a,a)/ plays the role of a zero. Given any

other pair /(c,d),/ /(a+c,a+d)/ is in the same equivalence class

as /(c,d)./ Adding /(a,a)/ has no effect on which equivalence

class we're in.

Now we can see that /(b,a)/ acts as the negative of /(a,b)/ because

/(a,b)+(b,a)=(a+b,a+b)/ and we get the equivalence class that plays

the role of zero.

This is the next stage after Constructing The Counting Numbers. _

If you haven't already, you probably should read that first.

We also have a natural embedding of the counting numbers into the

collection of equivalence classes EQN:x\rightarrow(x,0)

----

So, we claim that we have the counting numbers. We should

double check that things work. I'm not going to do that

here, but broadly, we should check that what we have is the

same as what we get from the Peano Axioms.

[[[>50 The Peano Axioms are a set of axioms that try to

capture what we mean by the Counting Numbers. They are

expressed technically, as indeed they must be, but mostly

they seem like just a technical statement of common sense.

To that end we like to say that the system described by

the Peano Axioms /*is*/ the Counting numbers. It is

widely accepted to be so.

As such, if we claim we've constructed the counting nubmers

then we should check that what we've built is isomorphic

(technical term for "pretty much exactly the same as") the

one from PA. ]]]

Loosely speaking, here's the way we find the equivalence.

If we allow the empty collection to be a thing, then the

equivalence class containing the empty set is the zero.

The equivalence class containing the set { 0 } is "1".

We can add "1" to anything to get the next thing, and

things just work. The definition of equality works the

way we would expect, so everything just goes as we need.

So we can now do some algebra, should we feel so inclined.

We can solve problems of the form:

* x + 5 = 8 : what is the value of x ?

Problem is, we can't solve the very similar looking:

* x + 8 = 5 : what is the value of x ?

So here's what we'll do. Using the counting numbers

and the concept of addition, we'll define a collection

of things. We'll declare some of them to be equivalent,

and then we'll define an operation on them that we'll

call "addition."

You can see that this is pretty much exactly what we did

last time. Last time we took collections and defined an

equivalence relation, etc., etc. We'll do it again.

So here we go ...

[[[>50 "Pairs" are different from "Sets" because there is

specifically an ordering. Given a pair of numbers, there

is specifically a first number, and a second number. Moreover,

the numbers can be equal, and it's still a pair of numbers.

In contrast, with a set that has two things in it there is

no "first" or "second." Also, naming something twice in a

set doesn't mean it's there twice. A set is determined only

by the things in it, and naming something twice doesn't mean

it's there twice. The set "{ 1, 1 }" is actually the same as

the set "{ 1 }".

Many people find this confusing the first time they meet it,

and some never get over that confusion. Suffice to say that

this is a definition that mathematicians have found to be the

most useful in practice, so it's the one we stick with. ]]]

We have the counting numbers and addition. So consider

pairs of numbers. Last time we talked about collections,

this time we'll talk about these pairs of numbers. An

example is (2,3), another example is (8,5), another is

(0,0), and another is (3,7).

Last time we declared things to be equivalent if there

was a matching between them. This time I will declare

that (a,b) is equivalent to (c,d) if a+d=b+c. Here are

some examples. These are all equivalent:

* (3,5), (6,8), (10,12), (7,9)

You should check that.

These are equivalent:

* (4,1), (10,7), (23,20), (37,34)

You should check that. You should also check that the

items in the second group are not equivalent to the items

in the first group. You only need to check one, because

that's how equivalence relations work. If you don't see

that, you need to go back and revise the exercises on

them.

I didn't choose those particular pairs for any special

reason. There is no pattern to them, except that within

a row, the pairs are equivalent.

----

Exercise:

* Find two more pairs equivalent to those in row 1.

* Find two more pairs equivalent to those in row 2.

* For each row, find an equivalent pair whose total _ is as small as possible.

----

But now I hear you cry:

* Where does this definition of equivalence come _ from? What is the motivation for this?

So, where */does/* this definition come from? Here's one

explanation. It may not be the truth ...

In the 1400s Italy became the economic powerhouse of the

world, because they worked out how to do accounting without

having to do subtraction. Subtraction at that time was hard,

really hard. To be honest, many people today have trouble

with subtraction, and while today we can just reach for a

calculator, they were hard to come by in the 1400s.

So how did they do this? What they did was keep two columns

for the concept of "value". Things that were good, like cash

and inventory, went into the first column. Things that were

bad, like debt, went in the second. Thus when someone gave

you $147, you would add 147 to the first column, and they,

the person giving it to you, would add 147 to their second

column. Two entries have to be made for each transaction,

hence the phrase "Double Entry Accounting." (Yes, if you

know about these things you'll know that this is not entirely

true. Bear with me.)

So in modern parlance, the "value" of a company was given

by the first column minus the second. If your entries were

(147,236) then you were in trouble. If your entries were

(236,147) then things were significantly better.

So for the pairs (a,b) and (c,d) the conceptual values are

"a-b" and "c-d". If these are equal then the companies are

of equal value. Thus (a,b) is equivalent to (c,d) if a-b=c-d.

Unfortunately we don't have subtraction, so we're not allowed

to say that. However, we can turn it around:

* a - b = c - d

Add "d" to both sides:

* a - b + d = c

Add "b" to both sides:

* a + d = c + b (which is b+c)

So a+b = b+c.

Look familiar? This is the definition I gave just a few

lines above. We can declare these pairs to be equivalent

just by using addition - we don't need this complicated

concept of subtraction.

----

Recap ...

| | Last time | This time |

| Things we deal with: | Collections (sets) | Pairs of numbers |

| Two things are equivalent if: | There's a matching | a+d = b+c |

So we have some things (pairs of numbers) and an equivalence

relation. That means we have equivalence classes. We will

call the collection of equivalence classes Z.

Last time we defined "addition" of two sets by taking the

discriminated union. This time we define the sum of two

pairs to be the point-wise of component-wise sum, so

(a,b) + (c,d) = ( a+c, b+d ). Just add the numbers in

each place.

Again, we take equivalence classes, and ask: Does this

definition of addition on pairs transfer nicely to the

equivalence classes? We want to know if we can use this

definition of adding this pair to that pair to define a

concept of adding equivalence classes.

* Given two equivalence classes EQN:E_1^{~} and EQN:E_2, take _ a representative of each, EQN:e_1 and EQN:e_2 (they _ will be pairs of counting numbers). Take their sum, _ and consider the equivalence class of the result.

* Is it always the same, regardless of the choice _ of EQN:e_1 and EQN:e_2 ?

In other words:

* Let E be the equivalence relation between pairs _ as defined above. Let a, b, c, and d be _ pairs of numbers, and suppose: _

** E( a, b )

* and

** E( c, d )

* Prove that:

** E( a+c, b+d )

Thus the collection of equivalence classes acts as the integers.

In turns out that this is true, and we can prove it.

So that means that we can sensibly talk about addition

on the equivalence classes.

You may wonder why this is interesting. Why is this new

collection of equivalence classes (Z) different from our

previous collection of equivalence classes (N) ? Or more

useful?

Or even interesting?

It's time to introduce another concept - the function.

----

Detour through functions ...

We've already used functions, although not explicitly.

It's worth introducing the concept with a little detail,

and then putting more details in later.

So a function is like a black box that takes one (or more)

things, and gives back something else. The things given

back don't need to be different every time, but if you

feed in the same things, you always get the same result.

The answers don't need to be the same type of thing as

the inputs. For example, we could have a box that takes

a car and gives back the registration number. Or we

could have a box that takes a car and gives back the

engine number. Or we could have a box that takes a book

and returns the number of pages, or the number of words.

Or we could have a box that takes a set and gives back

the number of things in it.

Or, given two sets, we could have a box that takes something

from one of them, and gives back something from the other.

A little bit of notation. When we have a function, the

collection of all possible things we can feed to it is

called its "Domain." The collection of all things it

actually does give as answers is called the "Image" of

the function, sometimes also called the "Range." Any

set that includes the Image can be called the CoDomain.

[[[>50

!! Notation:

* Domain:

** The collection of things our function can take.

* Range (aka "Image"):

** The collection of all the things the function gives back

* CoDomain:

** A "natural" collection that contains the Range, and perhaps more besides.

]]]

For example, consider the squaring function that takes an

integer /x/ and produces EQN:x^2. The Domain is the things we

can feed the function, and that's the integers. The Range,

or Image, is the collection of values achieved, and that's

the counting numbers (including zero). That, in turn, lives

inside the integers, so we can say that the CoDomain is the

integers, even though not every value is "hit" or "obtained"

by the squaring function.

A little notation. We write things like /f:A->B/ to mean

that "f" is a function, "A" is the domain, and the value of

"f" is always inside the set "B" - "B" is the CoDomain. It

is not to be assumed that every element of "B" is hit by "f".

Nor is it to be assumed that every element of "A" is taken

to a different element of "B".

Hitting every element of the CoDomain, or only hitting things

at most once, are both additional conditions that may or may

not be satisfied by a particular function. There are special

names that add these sorts of conditions to "f".

* "injective" : nothing in "B" is hit more than once.

** Sometimes this is called "one-to-one"

* "surjective" : everything in "B" gets hit at least once.

** This can also be referred to as being "onto."

* "bijective" : it's both injective and surjective.

** Thus a "bijective" function is "one-to-one and onto."

* A function that's "injective" is said to be an "injection."

* A function that's "surjective" is said to be a "surjection."

* A function that's "bijective" is said to be a "bijection."

In fact, we've met bijections before. If "f" is a bijection

then it's a matching, pairing off elements from its domain

with elements of its CoDomain.

Further, being a bijection means that it's reversable. In

particular, suppose /f:A->B/ is a bijection. That means that

for every /b/ in /B/ there is one and only one /a/ in /A/ that gets

mapped to it. So /f(a)=b./

Define /g:B->A/ by /g(b)=a./

That means that if you start with /a,/ use /f/ to send it

over to /B,/ then use /g/ to send it back, you get back to

where it started.

You can instead start with /b/ in /B,/ use /g/ to send it over

to /A,/ then use /f/ to send it back to /B,/ and again, you're

back where you started.

That's why a bijection is sometimes called a matching, and

a Matching is what we used as our equivalence relation when

we constructed the counting numbers.

Final point, suppose we have a function f:A->B that's an

injection (so it's injective, defined above - go check) but

not a surjection (so it's not surjective. Again, go check).

We can convert /f/ into a surjection by restricting ourselves

to the Range (or Image) inside the CoDomain. Suppose /B'/

is the image of /f./ We define a new function /f/'/ that

goes from /A/ to /B'./ The new function /f/'/ actually does

exactly the same as the original function /f,/ but /f/':A->B'/

is a bijection (aka a matching).

Note: since /f/'/ has a different CoDomain, technically it's

not actually the same function. However, for each /a/ in /A/,

the function /f/'/ takes the same value as /f,/ so we often

use the same name, and if the difference becomes important,

we make it clear.

----

So why did I talk about functions? I'm going to take a

function from the counting numbers (which are equivalence

classes of sets using the equivalence relation "matching")

into this new thing we've constructed (equivalence classes

of pairs).

So for a number /n/ in /N,/ I need to say what it gets sent

to in /Z./

Remember, an element /z/ of /Z/ is an equivalence class of pairs

of elements from /N./ So if I specify a pair of elements

from /N,/ I can then talk about the equivalence class it

belongs to. And that's what I do.

* Let /T:N->Z/ be the function defined as follows:

** Given /n,/ define /T(n)/ to be the equivalence _ class containing /(n,0)./

And here's a thing. If I take two things in /N,/ add them,

then use /T/ to send the result over to /Z,/ I get the same

answer as if I send each of the values of to /Z,/ and then

add them there.

In symbols:

* T( n1 + n2 ) = T(n1) + T(n2)

Or, as a diagram (to be done properly at a future date):

{{{

N --- T --> Z

========== ============

n1 -- T -> T(n1) = z1 -------.

| |

| n2 -- T -> T(n2) = z2 +----. |

| | \/

| | T(n1)+T(n2) = z1+z2 <-.

| | \_ These two things

| \ / should be equal.

'--> n1+n2 -- T -> T(n1+n2) <---------'

}}}

The point is that it doesn't matter what route you take

to get to the endpoint, you should get the same answer.

If this happens then we say that the function /T/ "respects"

or "preserves" the addition operation. In a very real

sense, the image of /T/ (that is, the things that get hit

by the function /T/ ) is a copy of /N./ We have found, inside

/Z,/ a copy of /N./

[[[>50 You may wonder why we have two

sets of brackets. The function E takes a pair and returns

an equivalence class. That means we need to give it a pair.

The pair is "(a,b)", so that's what has to go inside the

brackets.

In fact, for notational convenience we will write E(a,b)

instead of the more technically accurate E( (a,b) ). ]]]

And here's the extra bit.

Given a pair of numbers, (a,b), let's call its equivalence

class E( (a,b) ).

It turns out that E(0,0) has a very special property:

when you add it to /z,/ the answer is /z./ [[[>50 Remember, we

are adding things in /Z,/ and things in /Z/ are equivalence

classes of pairs of numbers. ]]]

That means that E(0,0) behaves exactly like our

ordinary 0 in the numbers that we are so familiar with.

Now consider E(3,5), and add it to E(5,3). The

answer is E(8,8), and (8,8) is equivalent to (0,0),

so that means that:

* E(3,5) + E(5,3) = E(3+5,5+3) = E(8,8) = E(0,0)

In other words, adding E(5,3) to E(3,5) gives 0. Another

way to say that is that E(5,3) is the negative of E(3,5).

Now we can solve the equation:

* x + 8 = 5.

OK, so we start by converting over from /N/ to /Z,/ so our

equation is actually:

*x + E(8,0) = E(5,0)

By our rules we know that E(5,0) = E(8,3), because (5,0)

is equivalent to (8,3), because 5+3=0+8. So the equation

we want to solve is:

* x + E(8,0) = E(8,3)

And we can immediately see that the solution is x=E(0,3).

There is a solution!

So, to summarise ...

* We started with the counting numbers /N;/

* We had a concept of addition of counting numbers;

* We constructed a collection of things: pairs of numbers;

* We defined an equivalence: EQN:(a,b)\equiv(c,d) if a+d=b+c;

* We consider equivalence classes: E(a,b);

* We call the collection of equivalence classes, /Z;/

* We define addition: E(a,b) + E(c,d) = E(a+c,b+d);

* Using the function /T/ we find a copy of EQN:{\bb~N} inside /Z;/

** EQN:T:x\rightarrow(x,0)

* We find that /T/ preserves/respects the concept of addition;

And now we can solve equations of the form: x + 8 = 5.

----

The method above is not the only way to construct something that

behaves as the integers should, starting with only the counting numbers.

The usual way of writing integers suggests another way:

say that an integer is either a counting number (0,1,2,...)

The usual way of writing integers suggests another way.

Say that an integer is either a counting number (0,1,2,...)

or a nonzero counting number with "-" stuck in front of it (-1,-2,...);

and then define arithmetic operations on these things case by case.

So, for instance, to define addition on the integers

we need to consider the following cases:

[[[>50 This is even more tricky because at this stage the value

of "a-b" is undefined because we don't yet have subtraction, even

when the answer would be positive. ]]]

* (a)+(b) = (a+b)

* (-a)+(-b) = -(a+b)

* (a)+(-b) = (a-b) when a >= b

* (a)+(-b) = -(b-a) when a < b

* (-a)+(b) = (b-a) when a <= b

* (-a)+(b) = -(a-b) when a > b

This approach has the advantage of familiarity, and avoids the

technical machinery of equivalence classes; but it requires

a great deal of case-splitting. In contrast, the

equivalence-classes-of-ordered-pairs approach above

just says: (a,b) + (c,d) = (a+c,b+d), and that's that.

Which is better? Most mathematicians would choose the first way.

It's harder to understand at first, but the ideas it uses --

ordered pairs, equivalence relations, etc. -- turn out to be useful

throughout mathematics. (For instance, we can use a very similar idea

for constructing the rationals.) And the payoff in simplicity

and elegance is considerable.

----

[[[>50 My thanks to Gustavo ~Massaccesi for many small but

important corrections and additions. ]]]

This page uses:

* Equivalence class

* Equivalence relation

* Embedding