Proof by Induction, is it correct? For $n \in N$, we define a set of successors of $n$ through
$A_n := \{s(n), s(s(n)), ...\} := \{ \varphi_m(n), \text{ where } m \in N \setminus\{0\} \}$
$\varphi_m : N \to N$ is the addition function, as in m + n
I'm trying to prove through induction that $n \notin A_n$ for every $n \in N$
I started by proving that $0 \notin A_n$ based on Peano Axioms and the definition of addition function: $\varphi_m(0) = m$.
Assuming that $n \notin A_n$ for every $n \in N$, I have to prove that $s(n) \notin A_{s(n)}$
Perhaps it would work by defining $A_{s(n)}$ in terms of $A_{n}$ and using the induction assumption, but I am not sure how to do that. Am I on the right track?
 A: Recall (from Peano's axioms) that the successor function is injective. Let $s^k$ denote $s\circ s \circ \cdots \circ s$ ($k$ times).
If $s(n) \in A_{s(n)}$, then there exists $k \ge 2$ such that $s(n) = s^k(n) = s(s^{k-1}(n))$ hence by injectivity $n = s^{k-1}(n)$, so $n \in A_n$. A contradiction.
A: Proof by contradiction. Assume $s(n) \in A_{s(n)}$. Then there exists some $m \in \mathbb{N} \setminus \{ 0 \}$ such that $\varphi_m(s(n)) = s(n)$, i.e. $m + s(n) = s(n)$. Given that $m \in \mathbb{N} \setminus \{ 0 \}$, it must be the case that $m = s(k)$ for some $k$, and thus $s(k) + s(n) = s(n)$.
Now, by the Peano Axiom that says:
$\forall x \forall y \ x + s(y) = s(x + y)$
we thus have that 
$s(s(k) + n) = s(n)$
And by the Peano Axiom that says:
$\forall x \forall y \ (s(x) = s(y) \rightarrow x = y)$
We thus have that:
$s(k) + n = n$
But that means that there is some $m \in \mathbb{N} \setminus \{ 0 \}$ (namely, $s(k)$) such that $m + n = n$, and thus $n \in A_n$.  But that contradicts the inductive hypothesis that $n \not \in A_n$.  Hence our assumption that $s(n) \in A_{s(n)}$ must be rejected, and thus $s(n) \not \in A_{s(n)}$
