- Let A be the set N x N and define a relation
r on N x N by saying that (a, b) is related to
(a’, b’) if a + b’ = a’ + b. Then this relation is an equivalence
relation.
- If [(a,b)] and [(a’, b’)] denote the equivalence classes
containing (a, b) and (a’, b’), respectively, and if we define
addition and multiplication of those equivalence classes as:
- [(a,b)] + [(a', b')] = [(a + a', b + b')]
- [(a,b)] * [(a’, b’)] = [(a * b’ + b * a’, a * a’ + b * b’)]
- then these operations are well-defined and the resulting set of all
equivalence classes has all of the familiar properties of the integers (it
therefore serves to define the integers based only on the natural numbers).
Proof:
We first have to prove reflexivity, symmetry, and transitivity to show that
the relation is an equivalence relation. The first two properties are easy,
and are left as an exercise. As for transitivity:
- Take (a,b) ~ (a', b’), i.e. a + b’ = a’ + b
- Take (a', b’) ~ (a’’, b’’), i.e. a’ + b’’ = a’’ + b’
Adding, we get (a + b’) + (a’ + b’’) = (a’ + b) + (a’’ + b’).
Canceling a’ and b’ on both sides yields
- a + b’’ = a’’ + b, i.e. (a, b) ~ (a’’, b’’)
Hence, transitivity is proved.
Next, we will have to show that the way that the definition of addition and
multiplication is well-defined. In particular, we need to show that the
definition of these operations does not depend on the particular representative
of the equivalence classes that we chose. The idea of that proof is clear:
pick different members of a class, and show that their sum or product results
in the same class. Thus, suppose:
- (a, b) and (c, d) are related
- (a’, b’) and (c’, d’) are related.
- Then [(a,b)] + [(a’, b’)] = [(a + a’, b + b’)]
- and [(c, d)] + [(c’, d’)] = [(c + c’, d + d’)]
- Because (a, b) ~ (c, d) we know: a + d = c + b
- Because (a’, b’) ~ (c’, d’) we know that a’ + d’ = c’ + b’
Adding both of those equations we get that:
- (a + a’) + (d + d’) = (c + c’) + (b + b’)
which means, in other words, that the two elements are related in turn. Hence:
- [(a + a’), (b + b’)] = [(c + c’), (d + d’)]
which is exactly what we wanted to show.
Finally, we need to show that multiplication is also well-defined. Therefore,
suppose:
- (a, b) and (c, d) are related, i.e. a + d = c + b
- (a’, b’) and (c’, d’) are related. i.e. a’ + d’ = c’ + b’
Then, according to the definition of multiplication:
- [(a,b)] * [(a’, b’)] = [(a * b’ + b * a’, a * a’ + b * b’)]
- [(c, d)] * [(c’, d’)] = [(c * d’ + d * c’, c * c’ + d * d’)]
We need to show that these two classes are identical, i.e. the representatives
are related. That means we need to show that
- (a * b’ + b * a’) + (c * c’ + d * d’) = (c * d’ + d * c’) + (a * a’ + b * b’)
It is easiest to start with what we would like to be true and work backwards. Therefore,
rearranging the above equation we have:
- a * b' - a * a' + b * a' - b * b' = c * d' - c * c' + d * c' - d * d'
Factoring, we obtain:
- a * (b' - a') - b * (b' - a') = c * (d' - c') - d * (d' - c')
and factoring again:
- (a - b) * (b' - a') = (c - d) * (d' - c')
But now we can use that fact that (a, b) ~ (c, d) and
(a', b') ~ (c', d') to see that this equation is indeed true.
As for the actual proof, we only have to read the last few lines backwards
to have a perfectly good proof. This will show that the two resulting classes
are the same, proving that multiplication is indeed well-defined.
As to why this definition yields equivalence classes with properties similar to
the integers, consider a few examples on your own. We do not actually have to
prove anything, because we simply define the integers to be the set of
equivalence classes with respect to the above equivalence relation and definition
of addition and multiplication.
Before we finish: it seems like a real coincidence that this nice factorization
worked in the proof of the well-definition of the multiplication. If you work
out some examples with actual numbers, however, it might become clear that this
is of course not a coincidence after all.
To Theory |
Glossary |
Map
(bgw)