Mendelson (in Number Systems & the Foundations of Analysis) defines a Peano System as a triple $(P, S, 1)$ consisting of a set $P$, a distinguished element $1 \in P$, and a singulary operation $S 😛 \mapsto P$, where $S(n)$ is called "the successor of $n$", such that
- $1$ is not the successor of any other element
- $S(x) = S(y) \implies x = y$
- The Principle of Mathematical Induction holds — namely, for any subset $B \subseteq P$ that contains the distinguished element $1$ and is closed under $S$, then $B = P$.
My question is: is it possible to show that a triple satisfies these properties? In particular, how might one rigorously show that property 3 holds?
For example, let $P$ be the set of positive even integers, $S = x \mapsto x + 2$, and the distinguished element is $0$. Showing that properties 1 and 2 are met seems simple enough, but it's unclear to me how one might show that 3 holds for an arbitrary set.
I know that in this example, we need what Mendelson calls the "Iteration Theorem" and what other authors seem to call the "Recursion Theorem" to define addition over the natural numbers to be rigorous about our definition of $S$. But that seems a bit circular, since we haven't yet shown that our triple is even a Peano System yet.
I would appreciate any efforts to illuminate my muddled thinking here 🙂
Best Answer
The short answer is that it depends on how you define your candidate Peano structure.
What property (3) guarantees is that your set $P$ is inductively defined, that is every element $x\in P$ can be written as $S(S(\ldots(S(1))\ldots))$, that is, $P$ contains no other "exotic" elements.
When you define a Peano system you are defining a class of mathematical structures satisfying certain properties. These structures are precisely the sets which have the structure of the natural numbers.
So when we define the natural numbers in set theory we first build a set $\mathbb N$ which is closed under an operation called the successor, given by $S(x) := \{x,\{x\}\}$, and $0 := \emptyset$. Set theory guarantees the existence of such a set, called $N$. In fact there are many such sets, which may have too many elements. To fix this, we define
$$\mathbb N := \bigcap\{x\in \mathscr P(N)\ |\ 0\in x\ \wedge\ \forall z. z\in x\to S(z)\in x\}.$$
We then show that $(\mathbb N,0,S)$ satisfies the property of being a Peano structure. In particular, for property (3) we have that given $U\subset \mathbb N\subset N$ containing $0$ and closed under $S$, we know from the definition of $\mathbb N$ (since it is an intersection), that $\mathbb N\subset U$ and thus $U =\mathbb N$.
This is how one would proceed. For the even naturals $\mathbb E\subset\mathbb N$, you would either define them similarly (replacing $S$ with $S\circ S$) to $\mathbb N$ and use the same argument, or you would have to use the fact that $\mathbb N$ satisfies property (3).
Now that you know that $\mathbb N$ is a Peano system, you can use your iteration theorem (I assume this gives you a way to define recursive functions, or some version of the Knaster-Tarski theorem) to define the addition and multiplication operations.