Let’s do something fun!

The Peano axioms for arithmetic are something like the Zermelo-Fraenkel axioms for sets. They describe what we intuitively want to be true about the natural numbers. Using ZFC, we were able to prove the existence of an inductive set , and it’s actually pretty easy to prove that the axioms below hold for that set. But the idea of the Peano axioms is that *any structure satisfying them* is “just as good” a model for the natural numbers. That is, it’s a necessary fact about that every number has a successor, but it’s not a necessary fact that the successor of is the set . It’s not even necessary that be a set at all.

And in fact, there *are* other models. We could take a category-theory approach and look at as the initial object in a category of things satisfying the axioms. We could treat numbers as just numbers and not suppose any internal structure. It doesn’t really matter, and perhaps this is the reason why we axiomatize stuff, so that we know what matters and what doesn’t.

The following is meant to be a bit of an exploration, mirroring Peano’s own exposition, into the properties of the natural numbers. Many of them you probably saw in school, but now you can actually prove them from a very small set of definitions and axioms. If nothing else, it’s a nice exercise in thinking logically.

We assume a set , and an equivalence relation that is defined on . (For honor’s sake, we could write this as a set of axioms as well: is reflexive, transitive, symmetric, and is closed under it.) The axioms are then as follows:

**Zero:**has an element . Peano originally used instead, but this is more useful, because it gives us an additive identity. This might be the reason for the distinction they teach you in school between the natural numbers and the “whole” numbers, the first not including , the second including it. Which is, by the way, the silliest thing.**Successor:**There is a function . We’ll write for the successor of . What’s going to end up happening is that we can use these two symbols to express any number, so and so on. We can’t do this yet because we don’t know that repeatedly applying the successor function to generates every number.**Least element**: There is no number such that . This is what makes “special,” and suggests that we can use it as a starting point for proofs.**Injectivity**: If , then . Now we can show, for example, that is infinite, because it contains , and they’re all different.**Induction**: If is a set such that and such that if , then , then . We call such a set**inductive**. Since is inductive, it must be the entire set . Again, all these elements are different, so there’s no problem with relabelling everything to get .

The “key idea” here is induction, just like the “key idea” of topology was closeness. The other four axioms just make sure you have a place to start () and don’t hit a fixed point (by injectivity). Then a lot of facts about the natural numbers just fall out. The first examples are the definitions, which pretty much all work due to induction. For example, we can define a binary operation inductively by . Since every element is for some number of ‘s, this is everywhere defined. Now try to prove the following things:

- .
- If , then .
- By induction on , . (Zero is an additive identity — and of course this means that it is
*the*additive identity.) - By induction on , . It follows that .
- By induction on , . (Addition is commutative.)
- By induction on , . (Addition is associative.)

This shows that addition is a *commutative monoid* (a monoid, remember, is a group without inverses). But though it doesn’t have inverses, it does have something close:

- By induction on , if , then . (Addition is right-cancellative.)
- By commutativity, addition is also left-cancellative.

This means that the monoid extends to a group, something we’ll explore in detail later. We define a relation by if for some number . Then are defined in the obvious way. If , then is defined to be the number such that (and if not, is undefined). By cancellativity, this is unique if it exists. Then:

- Since , is reflexive, and .
- If and , then (using the fact that implies ): is anti-symmetric.
- If and , then : is transitive, hence a partial order.
- By induction on , or (or both) for any : is a total order.
- If has no least element (an element such that for all ), then the set of elements in is inductive, so is empty. Thus, is a well-order.
- If , then , so addition is order-preserving.
- Finally, when , and similarly when .

Now we can define multiplication, again inductively. Let . Then:

- , and by induction on , (using ). So is the multiplicative identity.
- By induction on and then , : multiplication distributes over addition on the right.
- By induction on and then , and using distributivity, : multiplication is associative.
- By induction on , .
- By induction on , . So multiplication distributes over addition on both sides, and in particular, .
- Using the above two steps, and by induction on , : multiplication is commutative.
- Oh, and by the way, by induction on , if , then UNLESS (start with for the induction), so multiplication is cancellative.

So is also a commutative monoid under multiplication! But it also has two more special properties: for any , and multiplication distributes over addition. A set that is a commutative monoid under two operations with one distributing over the other and the identity of the first “annihilating” everything under the second is called a commutative **semiring**. This will become a ring, and then a field, once we start adding inverses, which the cancellation properties suggest we can do.

The final step in Peano’s exploration is somewhat more opaque, but it mirrors the definition of . Recall that if for some . Likewise, we can define if for some . The D can be read as “divides” and the symbol is used nowadays, but I really loathe that symbol, so yeah. If , then is defined to be the such that (by cancellativity, this is necessarily unique). Finally, we define a **prime number** as a number such that no number has other than and itself. Likewise, two numbers are **relatively prime** if no other than has .

And now you should be pretty familiar with how to prove the basic theorems of arithmetic coming out of these definitions. If you’re curious, try to prove that is a partial order, that a prime number is relatively prime to every number it doesn’t divide, and that if , then for any . You might also try defining exponentiation, if you’re curious, or other arithmetic operations. I’m probably going to move past this, though some brief forays into number theory might be fun later on, and start extending to the other sets of numbers we know and love.

**4 Comments so far**

Leave a comment

[…] yesterday, and I realized I hadn’t been as clear as I should have been in my treatment of Peano arithmetic. So I started typing some errata, and I ended up typing a super-long exposition about All the […]

Pingback by A Couple Nuances « Gracious LivingDecember 6, 2010 @ 03:01[…] yourself of the bounds of Peano arithmetic, you come upon a number of different routes to take. You want the addition and multiplication […]

Pingback by Ordinal Arithmetic « Gracious LivingDecember 7, 2010 @ 21:03[…] tricky! Unlike ordinal arithmetic, the arithmetic of cardinals isn’t really an extension of Peano arithmetic. Rather, it’s a consequence of the set model of ordinals, with the sum of two ordinals […]

Pingback by Cardinal Arithmetic « Gracious LivingDecember 8, 2010 @ 03:23[…] structure on the groups. In particular, I’m going to construct and similarly to how the Peano axioms constructed […]

Pingback by Rings, Integral Domains, and Fields « Gracious LivingFebruary 2, 2011 @ 19:36