# Peano axioms with only sets and mapping

I've got Serge Lang's Undergraduate Algebra (2nd edition). In the Appendix is a treatment of the Peano Axioms, but, as he says: "

The rules of the game from now on allow us to use only sets and mappings."

Good. Here they are:

1. There is an element $0 \in \mathbb{N}$
2. We have $\sigma(0) \ne 0$ and if we let $\mathbb{N}^+$ denote the subset of $\mathbb{N}$ consisting of all $n \in \mathbb{N}$, $n \ne 0$, then the map $x \mapsto \sigma(x)$ is a bijection between $\mathbb{N}$ and $\mathbb{N}^+$
3. If $S$ is a subset of $\mathbb{N}$, if $0 \in S$, and if $\sigma(n)$ lies in $S$ whenever $n$ lies in $S$, then $S = \mathbb{N}$.

He then says

We often denote $\sigma(n)$ by $n'$ and think of and think of $n'$ as the successor of $n$. The reader will recognize 3. as induction. We denote $\sigma(0)$ by $1$.

This supposedly implies $\sigma$ is a successor function, i.e., $\sigma(n) \implies n + 1$. To me it seems 2. and 3. must be working together to produce the successor function, although I can't see it. What necessarily forces $\sigma$ to behave as a successor function $\sigma(n) \implies n + 1$?

• What do you mean by "behave as"? I find this to be pretty unclear in your question. Apr 2, 2016 at 15:35
• The binary $+$ must be defined in order to show that, and this definition is usually recursive and makes an inductive proof of the successor property you mention possible. Apr 2, 2016 at 15:42
• These axioms are oddly expressed. More usual is mathworld.wolfram.com/PeanosAxioms.html Apr 2, 2016 at 20:54
• I don't find them so odd. #2 implies $\Bbb N$ is infinite, which is permissible by the axiom of infinity, but we can derive the surjectivity of $\sigma$ from just assuming $\sigma(n) \in \Bbb N$ and applying #3 to $\{0\} \cup \sigma(\Bbb N)$. There are lots of apparently different ways of saying things in math that turn out to be equivalent. Apr 3, 2016 at 2:04

To elaborate on coffeemath's comment, let's consider this function, $f_x: \Bbb N \to \Bbb N$:

$f_x(0) = x\\f_x(\sigma(k)) = \sigma(f_x(k)).$

Note that, in turn, we have another function: $x \mapsto f_x$ (which goes from $\Bbb N \to \Bbb N^{\Bbb N}$: $\Bbb N^{\Bbb N}$ is just another way of naming the set of functions $\Bbb N \to \Bbb N$). Let's call this second function $g$.

We will be especially interested in $g(1)$. let's unpack what function $g(1)$ is:

$f_1(0) = 1\\f_1(\sigma(k)) = \sigma(f_1(k)).$

Hence, $f_1(1) = f_1(\sigma(0)) = \sigma(f_1(0)) = \sigma(1)$.

In order to save time, let's look at the set: $T = \{n \in \Bbb N: \sigma(n) = f_1(n)\}$. We have already seen this set contains $0$ and $1 = \sigma(0)$.

Now suppose that $k \in T$, so that $f_1(k) = \sigma(k)$. By the definition of $f_1$:

$f_1(\sigma(k)) = \sigma(f_1(k)) = \sigma(\sigma(k))$, that is $\sigma(k) \in T$. So by rule 3, $T = \Bbb N$.

We thus conclude that $f_1 = \sigma$, since they agree on every domain element.

You probably know the function $f_x$ better as: "add $x$ to $k$", that is, the function that sends $k \mapsto k+x$, so hopefully you see now that $\sigma$ is thus the function that sends $k \mapsto k+1$. The reason $\sigma$ is not DEFINED as: $\sigma(0) = 1$, and $\sigma(k) = k+1$, is that we need a reasonable definition of "+" to define $\sigma$, then, and we want to USE $\sigma$ to define +.

The format:

$h(0) = a\\h(\sigma(k)) = f(h(k))$

(where $f$ is some function from the set $a$ lives in to that same set) is called a recursive definition of $h$, and allows us to specify $h$ for any natural number by just specifying the "rule" $f$, and the "seed value" $a$.

For example, if $a = 1 \in \Bbb R$, and $f: \Bbb R \to \Bbb R$ is the "doubling function" ($f(x) = 2x$), we get:

$h(0) = 1\\h(k+1) = 2\cdot h(k)$

which is a recursive definition of the function $h:\Bbb N \to \Bbb R$ given by $h(k) = 2^k$.

The idea is: rules 2 & 3 allow us to make such recursive definitions, because at each step, we can compute $h(n)$ in terms of $h$ evaluated at "smaller" values for $n$ we have previously computed.

• Please explain your $f_1(1) = f_1(\sigma(0)) = \sigma(f_1(0)) = \sigma(1)$ step. It's obvious that $\sigma(f_1(0)) = \sigma(1)$ (substitution), but I don't follow $f_1(1) = f_1(\sigma(0))$. What allows you to say that? Apr 3, 2016 at 1:44
• $1 = \sigma(0)$ (it's another substitution). If you want to show that without explicitly mentioning $1$, you would write: $f_{\sigma(0)}(0) = \sigma(0)$ and then $f_{\sigma(0)}(\sigma(0)) = \sigma(f_{\sigma(0)}(0))$ (by definition of $f_{\sigma(0)}$), which then equals $\sigma(\sigma(0))$. Apr 3, 2016 at 1:53
• I can follow your substitutions, but still I'm not seeing $1 = \sigma(0)$ from them. I see the recursive-ness of $\sigma(\sigma(0))$, but I still don't see how $1 = \sigma(0)$ is established. Don't we need to explicitly say $\sigma$ has magical powers of succession? But then at my age I can barely see the lines I used to think I could read between. . . . Apr 3, 2016 at 2:04
• My apologies, $1 = \sigma(0)$ is just the DEFINITION of $1$ (another name for it so we don't have to keep writing $\sigma(0)$ over and over again). We could keep going, writing $2 = \sigma(\sigma(0))$, and so forth. I just wanted to show that we have at least TWO values of $k$ (namely, $k = 0$ and $k = \sigma(0)$) for which $\sigma(k) = f_1(k)$, to apply rule 3, however, we only need that $f_1(0) = \sigma(0)$. Apr 3, 2016 at 2:08
• Good, thanks. I guess my OP had me confused about how a bijection of $\mathbb{N}$ to $\mathbb{N}^+$ could be inferred to be a succession function just because it couldn't map back to $0$. I'll continue reading your answer, hopefully still tonight. Apr 3, 2016 at 2:19

The above axioms are oddly stated. They axioms are usually expressed as something like:

1. $0\in N$
2. $\sigma: N\to N$
3. $\sigma$ is injective
4. $\forall x\in N: \sigma(x)\neq 0$
5. $\forall S\subset N: [0\in S \land \forall x\in S: \sigma(x)\in S \implies S=N$

The add function can be constructed as a set $A$ of ordered triples as follows:

$\forall x,y,z\colon[(x,y,z)\in A \iff (x,y,z) \in N^3$

$\land \forall S\subset N^3\colon[\forall t\in N\colon[(t,0,t)\in S] \land \forall (t,u,v)\in S\colon[ (t,\sigma(u),\sigma(v))\in S] \implies (x,y,z)\in S]]$

We can then prove, using the prefix notation that:

1. $\forall x\in N: [A(x,0)=x$]

2. $\forall x,y\in N:[A(x,\sigma(y)) = \sigma(A(x,y))]$

• Yes, oddly stated. But I doubt that Professor Lang is in error. I'm just not grasping it. Apr 3, 2016 at 1:46
• @147pm Dan's #5 is just your #3 stated another way, and Dan's #2 through #4 cover essentially the same ground as your #3 (well your #2 says a little more-it says $\sigma$ is onto $\Bbb N\setminus\{0\}$, but this follows from Dan's #2 and #5, using $S = \text{im }\sigma \cup \{0\}$. Apr 3, 2016 at 1:58
• @147pm I'm not saying it's erroneous, just oddly stated.It may even be equivalent. For the intuition of it all, you might have a look at my blog posting at dcproof.com/WhatIsANumberAgain.html Apr 3, 2016 at 2:32
• @ Dan C Having trouble getting to the dcproof.com site. . . . Apr 3, 2016 at 2:58
• @147pm Strange. I'm not having any trouble accessing it using Chrome on Windows. I don't know what to suggest. I think you will find the diagrams helpful. Apr 3, 2016 at 3:18