## 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 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 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 is less than or equal to the natural number (and write ) if either and are the same number, or if is the successor of some number and . This seems circular, but it’s really not. As we step down from to (maybe many times), eventually either will be equal to and we stop, or becomes 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 to .

The relation is reflexive right away. It’s also transitive, since if we have three numbers , , and with and then we have a chain of successors from to and one from to , and we can put them together to get one from to . Finally, the relation is antisymmetric, since if we have two different numbers and with both and , then we can build a chain of successors from back to itself. That would make the successor function fail to be injective which can’t happen. This makes 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 is either or for some number . We define the sum of and using this fact: is , and is .

That behaves as an additive identity is clear. We need to show that the sum is associative: given three numbers , , and , we have . If , then . If , then and . So if we have associativity when the third number is we’ll get it for , and we have it for . 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 — — and addition preserves order — if then .

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 if 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 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.

Two questions:

1. Can the

Comment by Jangler | March 17, 2007 |

hm. Well, my questions got cut off. Let’s try this again…

1. Can the less-than relation and plus operation be formulated entirely within category theory…something like “plus is the unique functor from NxN to N such that blah?”

2. Is there a good reference you can recommend for a category-theoretic treatment of the naturals? I think this way is more aesthetic, because obviously it’s irrelevant if 3 is an element of 5, or whatever, but I’m afraid that in such a general setting it may be impossible to prove, or even formulate, “interesting” theorems.

Comment by Jangler | March 17, 2007 |

Well, what I’m doing isn’t purely category theoretical. I’m just saying that

only those relations defined by the Peano axioms (and those definable in terms of them) are sensible predicates for the natural numbers. “Membership” is not part of PA, and cannot be expressed in terms of “Is-zero” or “Is-successor-of”, thus it’s out of bounds.That said, there

isa category-theoretic formulation, but it’s important enough that I’m going to wait until later to talk about it in a real post. That said, consider the category of finite sets…Comment by John Armstrong | March 17, 2007 |

[...] we’ve covered that the natural numbers are a commutative ordered monoid. We can add numbers, but we’re used to subtracting numbers too. The problem is that we [...]

Pingback by Integers « The Unapologetic Mathematician | March 18, 2007 |