Assume $(N, 0_N, ++^N) and (N˜, 0_{N˜} , ++^{N˜} )$ are two systems satisfying the Peano axioms.
Define the function
$T : N → N˜$ by
$T(0_N) = 0_{N˜}$
and
$T(n++^N) = T(n)++^{N˜}$
Prove that T(n) = T(m) ⇒ n = m
I can't figure out how to close my proof by induction. First I proved the proposition that $ n \neq 0$ implies there exists a m such that m++ = n. Which I then used to prove that for n = $0$ , T(n) = T(m) implies n = m = $0_N$ (using the axiom that $0$ is not a successor and proving the contrapositive) . Now for the inductive step I'm trying to prove that (T(n) = T(m) => n=m) => (T(n++) = t(m) => n++=m) and I can't figure it out for the life of me how to get there. Can somebody please point me in the right direction? Thanks for reading this.
I'm assuming that $++$ is a unary function symbol which is interpreted as the successor function in the standard model. For the sake of clarity, I will replace it with a prefix unary function $S$ (so that my $Sx$ is the same as your $x++$).
(incorrect answer removed)
After I came back home and reflected on the question, I think that it's important to emphasize that the problem statement is only true assuming that we are using second-order Peano axioms, in which every subset of the universe which contains $0^N$ and is closed under $S^N$ is equal to the whole universe. If we only take the first-order Peano axioms then this will not be true. To see this, let $N$ be a model of cardinality $\alpha\ge\aleph_0$ (e.g. the standard model $(\mathbb{N},0,x\mapsto x+1)$) and apply upward Löwenheim-Skolem-Tarski Theorem to get a model $N^\prime$ of cardinality $\beta>\alpha$. Then the problem statement would say that there exists an injection $N^\prime\to N$, which implies that $\beta\le\alpha$, which is absurd. Then it should be fairly simple, even trivial, to show that the statement holds in second-order arithmetic. (See comment for details)