Constructing The Integers

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

This is the next stage after Constructing The Counting Numbers.
If you haven't already, you probably should read that first.

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.

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

"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 $E_1^{~}$ and $E_2,$ take
a representative of each, $e_1$ and $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 $e_1$ and $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 )

E( c, d )

Prove that:

E( a+c, b+d )

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.

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

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.
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: $(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 ${\bb~N}$ inside Z;

$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,...) 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:
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.

My thanks to Gustavo Massaccesi for many small but important corrections and additions.

This page uses:

Links to this page / Page history / Last change to this page
Recent changes / Edit this page (with sufficient authority)
All pages / Search / Change password / Logout

	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