3
$\begingroup$

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$?

$\endgroup$
4
  • $\begingroup$ What do you mean by "behave as"? I find this to be pretty unclear in your question. $\endgroup$
    – Wojowu
    Apr 2, 2016 at 15:35
  • 1
    $\begingroup$ 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. $\endgroup$
    – coffeemath
    Apr 2, 2016 at 15:42
  • $\begingroup$ These axioms are oddly expressed. More usual is mathworld.wolfram.com/PeanosAxioms.html $\endgroup$ Apr 2, 2016 at 20:54
  • $\begingroup$ 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. $\endgroup$ Apr 3, 2016 at 2:04

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – 147pm
    Apr 3, 2016 at 1:44
  • $\begingroup$ $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))$. $\endgroup$ Apr 3, 2016 at 1:53
  • $\begingroup$ 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. . . . $\endgroup$
    – 147pm
    Apr 3, 2016 at 2:04
  • $\begingroup$ 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)$. $\endgroup$ Apr 3, 2016 at 2:08
  • $\begingroup$ 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. $\endgroup$
    – 147pm
    Apr 3, 2016 at 2:19
0
$\begingroup$

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))]$

$\endgroup$
5
  • $\begingroup$ Yes, oddly stated. But I doubt that Professor Lang is in error. I'm just not grasping it. $\endgroup$
    – 147pm
    Apr 3, 2016 at 1:46
  • $\begingroup$ @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\}$. $\endgroup$ Apr 3, 2016 at 1:58
  • $\begingroup$ @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 $\endgroup$ Apr 3, 2016 at 2:32
  • $\begingroup$ @ Dan C Having trouble getting to the dcproof.com site. . . . $\endgroup$
    – 147pm
    Apr 3, 2016 at 2:58
  • $\begingroup$ @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. $\endgroup$ Apr 3, 2016 at 3:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .