Addition and Multiplication

So far, we have sets, and we can build the natural numbers from them.  What we need now is ways to use them.  Let’s start with addition.

Many people see the statement 2+2 = 4 as something that just is.  It isn’t something that can be proven, or needs to be proven.  But there’s a problem with this approach: we end up defining addition by an infinite number of unproven statements, and that’s not a definition that we can use.

Our ability to count provides the answer.  Counting might seem like another infinite set of unproven statements: the number after one is two, the number after two is three, and so on.  That’s why we defined numbers in the way we did, by turning the problem around and defining numbers in terms of counting: the fact that three is the number after two is not just a property of three, but its definition.

Addition is just repeated incrementing.  And anyone who has spent much time with a language like LISP will know that recursion is the way to repeat a process.  So let’s find a recursive definition of addition.

Let x and y be two natural numbers.  What is x+y?  If y is 0, that’s easy.  We just say x+0 = x, for all natural numbers x.  If y is not zero, then it must be the successor of some other natural number (that was one of the Peano axioms).  Let’s call that number z, and define x+z’ = (x+z)’.  In other words, the sum of x and the successor of z is the successor of the sum of x and z.

Those two rules cover all possibilities: either y is 0, or it is the successor of some other number.  So now we can add any two natural numbers, by repeatedly applying the second rule until we reach a situation where the first is appropriate.  So 2+2 = 2+1′ = (2+1)’ = (2+o’)’ = (2+0)” = 2” = 4.

Multiplication is just as easy: it’s repeated addition.  So x \times z' = (x\times z)+x.

We can define subtraction too: x-y is the number z that makes the statement y+z = x true.  What is 7-4?  It’s 3, because 4+3 = 7.  But now we run into a problem.  What is 4-7?  What number, when added to 7, gives 4?  There isn’t one – not if we stick with the natural numbers, anyway.

To solve this problem, we need new numbers.  But before we build them, we’ll have to take a quick diversion.

Relations

The concept of a relation should be a familiar one.  It’s simply a property that a pair of objects may or may not have.  Familiar examples are “equals” (which is usually written =), “less than” (<), “greater than or equals” (\equiv_4).  The order of the objects matters: 2 is less than 4, but 4 is not less than 2.

We can define a relation as a set of ordered pairs, and say that two objects a and b satisfy the relation R if (a,b) \in R.

There are three important properties that relations can have.

  1. Reflexivity.  A relation R is reflexive if x R x for all x.  Of the examples above, the relations =, \equiv_4 are all reflexive, but < is not.
  2. Symmetry.  A relation R is symmetric if x R y and y R x are equivalent.  Here, = and x R y \Leftrightarrow y R x, meaning x R y implies y R x and y R x implies x R y.
  3. Transitivity.  A relation R is transitive if, when x R y and y R z, we also have x R z.  All four of the examples are transitive.  1 < 5, and 5 < 10, so it follows that 1 < 10.  An example of a relation that is not transitive is “is the successor of”.  3 is the successor of 2, and 2 is the successor of 1, but 3 is not the successor of 1.

A relation that has all three of these properties is said to be an equivalence relation.  Equivalence relations have the useful property of partioning sets.  That is, we can divide a set into subsets called partitions.  Every pair of elements taken from the same partition satisfy the relation, and no pair of elements taken from different partitions satisfy it.  Every element of the original set can be found in one, and only one, partition.

That needs an example.  The relation 2 \not\equiv_4 12, because they leave different remainders (2 and 0, repectively).

Partitions are also called equivalence classes, because each one is made of objects that can be regarded as equivalent, as far as the relation is concerned.

The Integers

Why that diversion?  Because we need it to make integers.  And why do we need integers?  Because we want to be able to solve subtraction problems.

So let’s try defining integers as the result of subtraction: an integer is an ordered pair of natural numbers (a,b), and we will regard it as being the answer to a-b.  Is that a satisfactory definition?  Not really – we end up with infinitely many representations of what we’d like to be the same number.  We know from the natural numbers that 1 = 2-1 = 3-2 = 4-3 = …, and that means our integers have infinitely many ways of representing 1.

So what we have is a set of things that we want to consider equivalent.  Does that sound like an equivalence class?  Can we find a relation that partitions ordered pairs of natural numbers in the right way?

After a bit of trial and error, you might come up with this: we call the relation (2,1) \sim (4,3), as we wanted.  (An aside: “if and only if” is used so frequently in mathematics that it is usually written “iff”.  That isn’t a typo).

Is (a,b) \sim (e,f), which means it’s transitive.

So \sim partitions the set of ordered pairs of natural numbers into equivalence classes, and we can define the integers to be those equivalence classes.  So the integer 1 is not the same as the natural number 1, but is instead the set {(1,0), (2,1), (3,2), …} of all pairs of natural numbers (x’,x).

Addition of integers is simple, but a bit convoluted because integers are not simple objects.  To add the integers x and y, we first choose any of the pairs from the sets defining each.  Say the pair we got from x is (a,b), and the pair from y is (c,d).  Then the sum x+y is the equivalence class that contains the pair (a+c,b+d).  For example, to add 3 and 4 I might choose (8,5) as my representitive for 3 and (18,14) for 4.  The result is the equivalence class containing (8+18,5+14) = (26,19), which is the integer we call 7.

I’ve gone on more than long enough for today, so multiplication shall be, as they say, an excercise for the reader.  If I have any readers left.