Show that $(P,S,1)$ is a Peano system if and only if it satisfies the Iteration Theorem

Question

You can skip the first section(hints and useful things) if you want, I will keep editing this along I got more findings related to the question.

Hints and useful things: I find out that the book from 1967 which the author mentions is Algebra(first edition) - Maclane and Birkhoff, but I dont have access to this book therefore I cant say what exactly is the hint in pages 67-70. If someone have access to this first edition please let me know what is the subject in these pages.

I have found a slide presentation talking about Induction, iteration, recursion, andwell ordering, In the page 42, It shows the Homomorphism Theorem (Dedekind 1888) in the same way the concept of isomorphism(3) here in my question, which in fact is obtained using the Iteration Theorem.

Later in pages 50-51, It talks about the Converse of Homomorphism Theorem where they states a very similar proposition to my interpretation of the question:

$$(N,S,1) \text{ is a Peano system} \Leftrightarrow (N,S,1) \text{ satisfies the Homomorphism Theorem}$$

The only difference is that in the question it uses Iteration Theorem instead of Homomorphism Theorem, then in the same slide the author says "This is a categorical characterization of $(\mathbb{N},0,S)$ (Lawvere 1965)". As the book which Im following give a definition of categorical(4) I added it to the concepts and definitions.

Question: Consider a Peano structure $(P,S,1)$, where $1 \in P$ and $S:P\rightarrow P$, Show that $(P,S,1)$ is a Peano system if and only if it satisfies the Iteration Theorem, that is for any set $W$, any object $c$ in $W$, and any singulary operation $g$ on $W$, there is a unique function $F:P\rightarrow W$ such that $F(1)=c$ and $F(S(x)) = g(F(x))$ for all $x$ in $P$. (see Maclane and Birkhoff [1967], pp. 67-70.

Concepts and definitions:

1. By a Peano System we mean a set $P$, a particular element $1$ in $P$, and a singulary operation $S$ on $P$ such that the following axioms are satisfied.

• (P1) $1$ is not the successor $S(x)$ of any object $x$ in $P$. In Symbols: $$(\forall x)(S(x) \neq 1)$$
• (P2) Different objects in $P$ have different successors. This can be formulated as follows: $$(\forall x)(\forall y)(x \neq y \Rightarrow S(x) \neq S(y))$$
• (P3) Principle of mathematical induction: Any subset of $P$ containing $1$ and closed under $S$ must be identical with $P$. This can be symbolically rendered as follows: $$(\forall B)([B \subseteq P \land 1 \in B \land (\forall x)(x \in B \Rightarrow S(x) \in B)] \Rightarrow P=B)$$

Such a Peano System will be denoted by the ordered triple (P,S,1): $P$ is called underlying set, $S$ the successor operation, and $1$ the distinguished element.

2. Iteration Theorem: Consider any Peano system $(P,S,1).$ Let $W$ be an arbitrary set, let $c$ be a fixed element of $W$, and let $g$ be a singulary opration on $W$. Then, there is a unique function $F:P \rightarrow W$ such that:

• $F(1) = c$
• $F(S(x)) = g(F(x))$ for all $x$ in $P$

3. Consider any two Peano systems $\mathscr{P}=(P,S,1)$ and $\mathscr{P}^* = (P^*,S^*,1^*)$, we say $\mathscr{P}$ and $\mathscr{P}^*$ are isomorphic if and only if there is a one-one correspondence $H$ between $P$ and $P^*$ $$H: P \xrightarrow[onto]{1-1} P^*$$ such that:

• $H(1) = 1^*$, and
• $H(S(x)) = S^*(H(x))$ for all $x$ in $P$.

Such a function $H$ is called an isomorphism between $\mathscr{P}$ and $\mathscr{P}^*$

4. A set of axioms is said to be categorical if and only if any two models for those axioms are isomorphic.

Proved Theorems: Here I will list previus proved Theorem in the text book which I believe its useful for this question.

1. Iteration Theorem (defined above)
2. Any two Peano systems are isomorphic (and the isomorphism is unique)

My atempt: My interpretation of the question is that it should be proved an equivalence between a system be a Peano system and satisfying the Iteration Theorem: $$(P',S',1') \text{ is a Peano system} \Leftrightarrow (P',S',1') \text{ satisfies the Iteration Theorem}$$

$[\Rightarrow]$

• We have by the definition of Iteration Theorem that it holds for any Peano system, as the Theorem is already proved we are done and just need to prove the converse.

$[\Leftarrow]$

• First assume some system $(P',S',1')$, where $P'$ is a set, $1' \in P'$ and $S'$ is a singulary operation on $P'$ and that this system satisfies the Iteration Theorem.
• From here I thinked about two approaches, where one is too prove that is possible to define an bijection between $P'$ and an already known set in another Peano system like $\mathbb{N}$ to establish an isomorphism, and the other approach is to prove that if any of Peano Axioms dont holds true for $(P',S',1')$ then the Iteration Theorem cannot be satisfied.
• Tryng the first approach, consider $(\mathbb{N}, S, 1)$ as the Standard Peano system, where $\mathbb{N}$ is the set of natural numbers and $S$ is defined as $S(x) = x+1$, now using the Iteration Theorem in $(P',S',1')$, let $W=\mathbb{N}$, $c=1$ and $g=S$, therefore we got a unique function $F:P' \rightarrow \mathbb{N}$ such that:

1. $F(1') = 1$, and
2. $F(S'(x)) = S(F(x))$ for all $x$ in $P'$

• We must show that $F$ is one-one and from $P'$ onto $\mathbb{N}$, first lets show that $F$ is onto by induction on $\mathbb{N}$.

Let $\mathscr{R}(F)$ be the range of $F$. We have that $1 \in \mathscr{R}(F)$, since $F(1') = 1$. Now assume $x \in \mathscr{R}(F)$ thus $(\exists u)(u \in P' \land x = F(u))$ and as $S$ is closed under $\mathbb{N} $ we have S(x) defined: $$S(x) = S(F(u))$$ and by definition of $F$ it follows $$S(x) = F(S'(u))$$

Thus we have $\mathscr{R}(F) \subseteq \mathbb{N} \land 1 \in \mathscr{R}(F)$ and we have shown that $x \in \mathscr{R}(F) \Rightarrow S(x) \in \mathscr{R}(F)$, therefore by Mathematical induction on $\mathbb{N}$ we have that $\mathscr{R}(F) = \mathbb{N}$, thus we got $F: P' \xrightarrow[onto]{} \mathbb{N}$

• Now we must show that $F$ is one-one, the first thing I notice is that if $F$ is from $P'$ onto $\mathbb{N}$ is must have at least one restriction $F'$ of $F$ where $F'$ is one-one, by the nature of the Iteration Theorem if we peek some element $x$ from $P'$ we have that $F(S'(x)) = S(F(x))$, but it we take $F(S'(S'(x)))$ we got first $S(F(S'(x))$ from which follows $S(S(F(x))$ not matter how many times we repeat this proccess we will have distinct objects because the nature of successor operation on $\mathbb{N}$, lets denote the $n$ applications of $S'$ to some $x$ by $S'^n(x)$ and $n$ applications of $S$ to $x$ by $S^n(x)$, therefore we can write $F(S'^n(x)) = S^n(F(x))$.

From this we can see that for any $a,b \in \mathbb{N}$ and some $x \in P'$ we have that $a \neq b \Rightarrow F(S'^a(x)) \neq F(S'^b(x))$ from which follows $a \neq b \Rightarrow S'^a(x) \neq S'^b(x)$.

Now for any $x \in P'$ let $P_x = \{y : y \in P' \land n \in \mathbb{N} \land (y = S'^n(x) \lor y=x) \}$, thus let $x=1$ in this definition and we will have $$P_{1'} = \{y : y \in P' \land n \in \mathbb{N} \land (y = S'^n(1') \lor y=1') \}$$

Now let $F$ be restricted to $F': P_{1'}\rightarrow \mathbb{N}$, we can prove that $F'$ is onto in the same way that was done before and as all elements in $P_{1'}$ is obtained from a successive applications of $S'$ to $1'$ it follows that $F'$ is one-one because $a,b \in \mathbb{N}$ we have that $a \neq b \Rightarrow F(S'^a(1')) \neq F(S'^b(1'))$, therefore we have $F':P_{1'} \xrightarrow[onto]{1-1} \mathbb{N}.$

• Now I suppose its possible to show that $F'=F$ or in other way that $P_{1'} = P'$ because it will prove that exists an isomorphism between $(P',S',1')$ and $(\mathbb{N}, S, 1)$ from which will follows that (P',S',1') is Peano system. I tried to show those both but I failed in all attempts and its not worth to put what tried at this part because I dont get any useful conclusions, thus I moved to the another approach where I dont make much progress but at least I got some useful things about singulary operation $S'$.
• From now I will just show two useful properties that $S'$ must have considering the function $F:P' \rightarrow \mathbb{N}$ established before using the Iteration Theorem.

1. $(\forall x)(S'(x) \neq 1')$

First assume $1'$ is in the range of $S$, thus $1' = S'(u)$ for some $u \in P'$, from which follows: $$F(1') = F(S'(u))$$ but as F(1') = 1 and F(S'(u)) = S(F(u)) we got $$1 = S(F(u))$$, which is a contradiction because by Axiom (P1) on $(\mathbb{N},S,1)$ $1$ is not a successor, therefore $1'$ is not in the range of $S'$, if we suppose $S'$ will act as a sucessor operation on $P'$ this show that Axiom (P1) holds true for $(P',S',1')$.

2. $(\forall x)(x \neq S'(x))$

Assume $S'(x) = x$, thus F(S'(x)) = F(x), from which follows S(F(x)) = F(x), which is a contradiction on $(\mathbb{N},S,1)$ because no one natural number is its own sucessor, therefore we have $x \neq S'(x)$ for all $x$ in $P'$.

Thats all I tried and managed to do, I think if its possible to prove that $S'$ is one-one it will be possible to prove that $F$ is one-one too and finish this proof without going along all Peano Axioms in the second apporach, but when if $S'$ is proved to be one-one, the only axiom which will be needed to prove is the Mathematical Induction.

Im not certain that those approach can really work in that case, so any feedback is welcome, and another approaches too, but I will like if some of those can be finished or corrected.