If $x \in P$ and $x \neq 1$, then $x = S(y)$ for some $y \in P$

Question

$P$ is a Peano system and $S$ is the successor function.

We want to show that all $x \in P$ (except $1$) are successors of some $y \in P$, so I guess we can use induction.

The case where $x = 1$ is trivial by one of the properties of a Peano system, so now we need to work on all the other $x$.

The induction hypothesis would be that some $x = S(y)$ for some $y \in P$, and so we need to show that $S(x) = S(y)$ for some $y \in P$. I know that the successor function is injective, so $S(x) = S(y)$ implies that $x = y$, but the converse is not true (since we don't care if $x = y$ or not; we want to show that $S(x) = S(y)$ is true) so I don't know how to prove that $S(x) = S(y)$.

Answer 1

Just to make sure I understand you correctly, let me restate the problem setting. Let me know if any of this isn't what you intended.

• $P$ is some set such that $1\in P.$
• $S:P\to P.$
• If $x\in P,$ then $S(x)\ne 1.$
• If $x,y\in P$ such that $S(x)=S(y),$ then $x=y.$
• If $A$ is a set such that $1\in A$ and such that $\forall x\in A\cap P\:\bigl(S(x)\in A\bigr),$ then $P\subseteq A.$

What you're trying to show, then, is that if $x\in P$ and $x\ne 1,$ then there is some $y\in P$ such that $S(y)=x.$

The trick is, indeed, to use induction, but this isn't necessarily done as we're used to. Instead, we let $$A=\{1\}\cup \{S(x):x\in P\}.$$ Now, $1\in A$ by definition. Moreover, if $x\in A\cap P,$ then in particular $x\in P,$ so we have $S(x)\in A$ by definition. Hence, we have $P\subseteq A.$ (Why?) On the other hand, suppose $y\in A.$ If $y=1,$ then $y\in P.$ (Why?) Otherwise, we must have $y=S(x)$ for some $x\in P$ by definition, so we have $y=S(x)\in P.$ (Why?) Hence, $A\subseteq P,$ and so $A=P.$

Finally, we see that $\{1\}\cap\{S(x):x\in P\}=\emptyset.$ (Why?) Hence, we're done. (Can you see why?)

For "bonus points," can you see which axiom(s) did not get used in this proof outline?