Building Arithmetic

The first math skill you learned as a child was probably counting. The natural numbers: 1, 2, 3, and so on. The second was arithmetic. 2+2, 8 times 5, and so on. These both probably come naturally to you now, but it’s unlikely that your kindergarten teacher ever explained set theory and the successor function while teaching you how to count. That’s what I hope to do here: show you the rigorous foundations of the mathematics you use every day without even thinking.

In ye olden times, the proof of 2+2=4 probably went something like this:

“I have two apples in this pile and two apples in this other pile. Now I will put them into one pile. This new pile has four apples because look at it. QED”

This proof is good enough for most people. It’s blindingly obvious that 2+2 is 4. What else could it possibly be? However, mathematics has moved far past those sorts of arguments. We no longer form cults and drown people who claim there is such a thing as an irrational number. Now, for something to be true, you have to set up some assumptions everyone agrees are reasonable (your axioms) and use the rules of logic to prove things from there. Everything you prove in this manner will be true as long as your logic is sound.

Now what are some reasonable assumptions for arithmetic? Well, the assumptions that most mathematicians use are called the Peano axioms, and they are (with explanations as needed):

1. 0 is a natural number
   It will become more apparent why we need this axiom later in the list, but this basically establishes that there is at least one natural number, the first one.
2. Every natural number is equal to itself (the reflexive property)
   It may seem obvious that 2=2, 5=5, and 1,000,802,391=1,000,802,391, but we’re setting things up mathematically so we have to be explicit with every assumption we’re making.
3. If x is equal to y, then y is equal to x where x and y are natural numbers (the symmetric property)
   This is another obvious one that we have to state so that everyone knows what we’re assuming before we start using our assumptions.
4. If x is equal to y and y is equal to z, then x is equal to z where x, y, and z are natural numbers (the transitive property)
   You get the gist.
5. If x is a natural number and x is equal to y, then y is also a natural number
6. If x is a natural number, then the successor of x is also a natural number
   Here’s another one that requires a little explaining. This axiom basically states that if you have a natural number, say 2, there will always be a “next” natural number, 3 in this case. The “next” number is called the successor and is usually written as S(n), a function which takes in a natural number n and spits out its successor.
7. If m and n are equal, their successors are equal
8. There is no natural number whose successor is 0
   This axiom places a very important restriction on our successor function from earlier. Without this, we would have no guarantee that our numbers don’t just loop back around to zero after some (possibly very long) time. Having numbers loop back to zero isn’t useless — it comes up a lot in finite group theory — but it’s not what we want our counting numbers to do.
9. If we have a set that satisfies the following properties: 0 is in the set and if a natural number is in the set its successor must also be in the set; that set contains every natural number (induction axiom)
   This axiom is pretty dense compared to the others so a quick demonstration might help. Any set that satisfies this axiom must contain 0, which is a natural number. The set must also contain the successor of every natural number in it, so 1 must also be in the set. Well, now 2 has to be in the set. And 3, 4, 5, and so on. This very intuitive property is the last piece we need to create arithmetic and also just so happens to be very useful in almost every area of math at some point or another.

And that long list is all you need to define addition and multiplication of natural numbers. It may be hard to see how, but we’re about to prove that. We’ll define all of these operations in turn, but it’s best to start off with addition to get an idea of how it works.

The two things we use to define addition are our successor function and a concept called recursion. Those who have taken a CS class may remember recursion. The basic idea of recursion is to take an input to your function, break it into one or more smaller parts, and plug those parts back into the same function until you reach some base case (it’s a bit more complicated than that but this definition is good enough for now). We use recursion to define addition of natural numbers by saying that for any natural number, a, a+0=a, and for any two natural numbers, a and b, a+S(b)=S(a+b). This definition satisfies all the properties of addition we’d like — namely associativity and commutativity (verifying this for yourself would be a great exercise). To demonstrate our new definition in action, let’s compute 2+2. Going through the computations very quickly, 2+2=2+S(1)=S(2+1)=S(2+S(0))=S(S(2))=S(3)=4. And it works! It may seem weird and ungainly, but it’s rigorous and it works! Multiplication is defined similarly to addition so I won’t bother going over it here.

That was a lot of work just to get some basic arithmetic. We didn’t even manage to get negative numbers or fractions (we need a few axioms about sets for those). However, this rigorous work to establish basic operations like arithmetic ensures all of the mathematics higher up works correctly. An incorrect assumption at the foundation can send an entire mathematical tower tumbling down into a pile of contradictions so it’s very important when you’re doing math to make sure every statement you make logically follows from some other statement or axiom you’ve made in the past.