First this is how the book define as a Peano System.
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.
Now the question:
Determine wheter or not the following structure (P,S,1) are Peano Systems.
a. $P$ is the set of all integers greater than $9$, "$1$" stands for the integer $10$. $S(u)=u+1$ for any $u$ in $P$.
My atempt:
$\checkmark$ (P1): Its clear that for any $x$ in $P$ we have that $x>9$ thus $(\forall x)(x+1 \neq 10)$ holds true
$\checkmark$ (P2): For any $x$ and $y$ in $P$ we have that $x \neq y \Rightarrow x+1 \neq y+1$
? (P3):
begin edit 1
First I assume some subset $B$ of $P$, such $10 \in B$ and $B$ is closed under $S$, from this we have that $(\forall x)(x \in B \Rightarrow S(x) \in B)$
But as $10 \in B$ we have that $S(10) \in B$ also, and then $S(S(10)) \in B$ too then $S(S(S(10))) \in B$…, from this I think its possible to "see" that every integer greater than 9 are in $B$ also. But I think its possible to state this in a better way.
For every integer $x$ greater than $9$ which is different from $10$, we have that $(\exists !y)(x = S(y))$, thus if $y \neq 10$, we will have that $(\exists !z)(y = S(z))$ and the same proccess can be repeated until we reach the application of $S$ to $10$, let $z=10$, thus we will have $x = S(S(10))$ which in fact is the integer 12, thus we needed to apply $S$, $x-10$ times to obtain the integer $x$, then if some $x \in P$, we know that applying $S$ in $10$, $x-10$ times will be the same integer, and therefore $x \in B$ because $B$ is closed under $S$, thus $P \subseteq B$.
From this we have that $P=B$ thus (P3) holds true from $(P,S,1)$
end edit 1
I dont know what is needed to prove or conclude that the (P3) holds true $(P,S,1)$, in some other exercises its clear that the system dont hold true for (P1) or (P2) and therefore is not a Peano System, but when (P1) and (P2) holds true I dont know how to continue. Thus I need help to understand how (P3) can be proved, I have looked at other questions concerning Peano System and Mathematical Induction axiom, some people says this cannot proved, If it is correct I should just assume (P3) holds true?
Best Answer
Your intuition is right, but that's not quite a rigorous proof: phrases like
are not really precise.
The way to rigorously prove this is ... by induction in the context of $\mathbb{N}$, which we presumably already know is a Peano system. Specifically, suppose $B\subseteq P$ contains $10$ and is closed under successor. Let $\hat{B}=B\cup\{1,2,3,4,5,6,7,8,9\}$.
For the first step, can you show that (in the context of $\mathbb{N}$) the set $\hat{B}$ is closed under successor?
Now what does that tell us about $\hat{B}$?
Finally, can you translate this back to $P=\{i\in\mathbb{N}: i\ge 10\}$?