Edit made on January 01, 2022 by ColinWright at 16:37:52
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