In the answer to this question I asked previously, it was stated that I can identify the successor function $a \to a^+$ with $a+1$. I finished reading the section in Jacobson's Basic Algebra I and wanted to try this myself and verify my proof for why these two functions may be identified.
The information I am using consists of Peano's axioms as presented in the text:
- $0 \neq a^+$ for any $a$ (that is, $0$ is not in the image of $\mathbb{N}$ under $a \to a^+$).
- $a\to a^{+}$ is injective.
- (Axiom of induction). Any subset of $\mathbb{N}$ which contains $0$ and contains the successor of every element in the given subset coincides with $\mathbb{N}$.
And the recursion theorem, stated below:
Let $S$ be a set, $\varphi$ a map of $S$ to itself, $a$ an element of $S$. Then there exists one and only one map $f$ from $\mathbb{N}$ to $S$ such that
- $f(0)= a$
- $f(n^+) = \varphi(f(n)), n \in \mathbb{N}$
Proof.
We define addition of $1$ to $n$ via the recursion theorem by taking $a = 0^+$ and $\varphi$ to be the successor map $n \to n^+$, and we denote the function furnished by the recursion theorem for this choice of $a$ and $\varphi$ as $f_{+1}$. We claim that $f_{+1} = n\to n^+$.
We will show that $f_{+1}(n) = n^+$ for all $n \in \mathbb{N}$. Let $$T = \{ n \in \mathbb{N} : f_{+1}(n) = n^+ \}$$ we claim that $T = \mathbb{N}$ by the axiom of induction. Since $f_{+1}(0) = 0^+$, we have $0 \in T$. Next, suppose that $f_{+1}(n) = n^+$, that is, $n \in T$. Then, by the recursion theorem $$f_{+1}(n^+) = \varphi(f_{+1}(n)) = \varphi(n^+) = (n^+)^+$$ So, $n^+ \in T$. Thus, by the axiom of induction, $T = \mathbb{N}$. But then $f_{+1}(n) = n^+$ as desired. $\square$