# Gracious Living

Peano Arithmetic
December 4, 2010, 14:45
Filed under: Logic, Math | Tags: , , ,

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 $\mathbb{N}$, 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 $\mathbb{N}$ that every number has a successor, but it’s not a necessary fact that the successor of $x$ is the set $x\cup\{x\}$.  It’s not even necessary that $x$ be a set at all.

And in fact, there are other models.  We could take a category-theory approach and look at $\mathbb{N}$ 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 $\mathbb{N}$, and an equivalence relation $=$ that is defined on $\mathbb{N}$.  (For honor’s sake, we could write this as a set of axioms as well: $=$ is reflexive, transitive, symmetric, and $\mathbb{N}$ is closed under it.)  The axioms are then as follows:

• Zero:$\mathbb{N}$ has an element $0$.  Peano originally used $1$ 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 $0$, the second including it.  Which is, by the way, the silliest thing.
• Successor:There is a function $S:\mathbb{N}\rightarrow\mathbb{N}$.  We’ll write $Sx$ for the successor of $x$.  What’s going to end up happening is that we can use these two symbols to express any number, so $1=S0,2=SS0,$ and so on.  We can’t do this yet because we don’t know that repeatedly applying the successor function to $0$ generates every number.
• Least element: There is no number $x$ such that $Sx=0$.  This is what makes $0$ “special,” and suggests that we can use it as a starting point for proofs.
• Injectivity: If $x\ne y$, then $Sx\ne Sy$.  Now we can show, for example, that $\mathbb{N}$ is infinite, because it contains $0,S0,SS0,\dotsc$, and they’re all different.
• Induction: If $M$ is a set such that $0\in M$ and such that if $x\in M$, then $Sx\in M$, then $M=\mathbb{N}$.  We call such a set inductive.  Since $\{0,S0,SS0,\dotsc\}$ is inductive, it must be the entire set $\mathbb{N}$.  Again, all these elements are different, so there’s no problem with relabelling everything to get $\{0,1,2,\dotsc\}=\mathbb{N}$.

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 ($0$) 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 $x+0=x,x+Sy=S(x+y)$.  Since every element is $S\dotso S0$ for some number of $S$‘s, this is everywhere defined.  Now try to prove the following things:

• $x+1=S(x+0)=Sx$.
• If $x+y=0$, then $x=y=0$.
• By induction on $x$, $0+x=x$.  (Zero is an additive identity — and of course this means that it is the additive identity.)
• By induction on $y$, $S(x+y)=Sx+y$.  It follows that $x+Sy=Sx+y$.
• By induction on $y$, $x+y=y+x$.  (Addition is commutative.)
• By induction on $z$, $x+(y+z)=(x+y)+z$.  (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 $y$, if $x+y=z+y$, then $x=z$.  (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 $\le$ by $y\le x$ if $x=y+z$ for some number $z$.  Then $<,>,\ge$ are defined in the obvious way.  If $y\le x$, then $x-y$ is defined to be the number $z$ such that $x=y+z$ (and if not, $x-y$ is undefined).  By cancellativity, this $z$ is unique if it exists.  Then:

• Since $x=x+0=0+x$, $\le$ is reflexive, and $x-x=0,x-0=x$.
• If $x\le y$ and $y\le x$, then $x=y$ (using the fact that $x+y=0$ implies $x=y=0$): $\le$ is anti-symmetric.
• If $x\le y$ and $y\le z$, then $x\le z$: $\le$ is transitive, hence a partial order.
• By induction on $y$, $x\le y$ or $y\le x$ (or both) for any $x$: $\le$ is a total order.
• If $M\subset\mathbb{N}$ has no least element (an element $x$ such that $x\le y$ for all $y\in M$), then the set of elements in $M$ is inductive, so $M$ is empty.  Thus, $\le$ is a well-order.
• If $x\le y,z\le w$, then $x+z\le y+w$, so addition is order-preserving.
• Finally, $x+(y-x)=y$ when $y\ge x$, and similarly $z+(y-x)=y+(z-x)$ when $y,z\ge x$.

Now we can define multiplication, again inductively.  Let $x\cdot 0=0,x\cdot Sy=(x\cdot y)+x$.  Then:

• $x\cdot 1=x$, and by induction on $y$, $1\cdot y=y$ (using $z+1=Sz$).  So $1$ is the multiplicative identity.
• By induction on $z$ and then $y$, $x(y+z)=xy+xz$: multiplication distributes over addition on the right.
• By induction on $z$ and then $y$, and using distributivity, $x(yz)=(xy)z$: multiplication is associative.
• By induction on $x$, $0\cdot x=0$.
• By induction on $z$, $(x+y)z=xz+yz$.  So multiplication distributes over addition on both sides, and in particular, $(Sx)y=(x+1)y=xy+y$.
• Using the above two steps, and by induction on $y$, $xy=yx$: multiplication is commutative.
• Oh, and by the way, by induction on $x$, if $xy=xz$, then $y=z$ UNLESS $x=0$ (start with $x=1$ for the induction), so multiplication is cancellative.

So $\mathbb{N}$ is also a commutative monoid under multiplication!  But it also has two more special properties: $x\cdot 0=0$ for any $x$, 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 $\le$.  Recall that $x\le y$ if $y=x+z$ for some $z$.  Likewise, we can define $xDy$ if $y=xz$ for some $z$.  The D can be read as “divides” and the symbol $|$ is used nowadays, but I really loathe that symbol, so yeah.  If $xDy$, then $y/x$ is defined to be the $z$ such that $xz=y$ (by cancellativity, this is necessarily unique).  Finally, we define a prime number as a number $p$ such that no number $x$ has $xDp$ other than $1$ and $p$ itself.  Likewise, two numbers $x,y$ are relatively prime if no $z$ other than $1$ has $zDx,zDy$.

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 $D$ is a partial order, that a prime number is relatively prime to every number it doesn’t divide, and that if $xDy,xDz$, then $xD(ay+bz)$ for any $a,b\in\mathbb{N}$.  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 $\mathbb{N}$ to the other sets of numbers we know and love.

[…] 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 Living

[…] 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 Living

[…] 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 Living

[…] structure on the groups.  In particular, I’m going to construct and similarly to how the Peano axioms constructed […]