The Unapologetic Mathematician

More structure of the Natural Numbers

Now we know what the natural numbers are, but there seems to be a lot less to them than we’re used to. We don’t just take successors of natural numbers — we add them and we put them in order. Today I’ll show that if you have a model of the natural numbers it immediately has the structure of a commutative ordered monoid.

The major tool for working with the natural numbers is “induction”. This uses the property that every natural number is either ${}0$ or the successor of some other natural number, as can be verified from the universal property. Think of it like a ladder: proving a statement to be true for ${}0$ lets you get on the bottom of the ladder. Proving that the truth of a statement is preserved when we take a successor lets you climb up a rung. If you can get on the ladder and you can always climb up a rung, you can climb as far as you want.

First let’s define the order. We say the natural number $a$ is less than or equal to the natural number $b$ (and write $a\leq b$) if either $a$ and $b$ are the same number, or if $b$ is the successor of some number $c$ and $a\leq c$. This seems circular, but it’s really not. As we step down from $b$ to $c$ (maybe many times), eventually either $c$ will be equal to $a$ and we stop, or $c$ becomes ${}0$ and we can’t step down any more. A more colloquial way of putting this relation is that we can build a chain of successors from $a$ to $b$.

The relation $\leq$ is reflexive right away. It’s also transitive, since if we have three numbers $a$, $b$, and $c$ with $a\leq b$ and $b\leq c$ then we have a chain of successors from $a$ to $b$ and one from $b$ to $c$, and we can put them together to get one from $a$ to $c$. Finally, the relation is antisymmetric, since if we have two different numbers $a$ and $b$ with both $a\leq b$ and $b\leq a$, then we can build a chain of successors from $a$ back to itself. That would make the successor function fail to be injective which can’t happen. This makes $\leq$ into a partial order. I’ll leave it to you to show that it’s total.

The monoid structure of the natual numbers is a bit easier. Remember that a number $b$ is either ${}0$ or $S(c)$ for some number $c$. We define the sum of $a$ and $b$ using this fact: $a+0$ is $a$, and $a+S(c)$ is $S(a+c)$.

That ${}0$ behaves as an additive identity is clear. We need to show that the sum is associative: given three numbers $a$, $b$, and $c$, we have $(a+b)+c=a+(b+c)$. If $c=0$, then $a+(b+0)=a+b=(a+b)+0$. If $c=S(d)$, then $a+(b+S(d))=a+S(b+d)=S(a+(b+d))$ and $(a+b)+S(d)=S((a+b)+d)$. So if we have associativity when the third number is $d$ we’ll get it for $S(d)$, and we have it for ${}0$. By induction it’s true no matter what the third number is.

There are two more properties here that you should be able to verify using these same techniques. Addition is commutative — $a+b=b+a$ — and addition preserves order — if $a\leq b$ then $a+c\leq b+c$.

Notice in particular that I’m not using any properties of how we model the natural numbers. The von Neumann numerals preferred by Bourbaki have the nice property that $a\leq b$ if $a\subseteq b$ as sets. But the Church numerals don’t. The specifics of the order structure really come from the Peano axioms. They shouldn’t depend at all on such accidents as what sort of model you pick, any more than they should depend on whether or not $3$ is Julius Cæsar. No matter what model you start with that satisfies the Peano axioms you get the commutative ordered monoid structure for free.

March 12, 2007 Posted by | Fundamentals, Numbers | 4 Comments