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.

About these ads

March 12, 2007 - Posted by John Armstrong | Fundamentals, Numbers

4 Comments »

Two questions:

1. Can the

Comment by Jangler | March 17, 2007 | Reply
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 | Reply
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 is a 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 | Reply
[...] 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 | Reply

About this weblog

This is mainly an expository blath, with occasional high-level excursions, humorous observations, rants, and musings. The main-line exposition should be accessible to the “Generally Interested Lay Audience”, as long as you trace the links back towards the basics. Check the sidebar for specific topics (under “Categories”).

I’m in the process of tweaking some aspects of the site to make it easier to refer back to older topics, so try to make the best of it for now.

RSS Feeds

RSS - Posts
RSS - Comments
Feedback

Got something to say? Anonymous questions, comments, and suggestions at Formspring.me!
Subjects
Archives

March 2007

M T W T F S S

« Feb Apr »

1 2 3 4

5 6 7 8 9 10 11

12 13 14 15 16 17 18

19 20 21 22 23 24 25

26 27 28 29 30 31
Search for:

The Unapologetic Mathematician

Mathematics for the interested outsider