# Prove that if $n, m \in \mathbb{N}$, then $m+n \neq n$ (by induction/contradiction)

My biggest question is whether I can use contradiction paired with induction the way I do below. I'm not 100% that it makes logical sense. For the purposes of this course I'm in, we define the first element of $\mathbb{N}$ to be $1$. Thanks in advance!

Prove that if $n, m \in \mathbb{N}$, then $m+n \neq n$.

The proposition $P_n$ is that $m+n \neq n$ when $m, n \in \mathbb{N}$.

We begin with the base case. If $n=1$, then $m+1 \neq 1$ because $m+1$ is the successor of $m$. By Peano's Axioms, $1$ is the successor of no element in $\mathbb{N}$. Thus the hypothesis is true in the base case.

For the induction step, we need to show that $P_{n+1}$ is true whenever $P_n$ is true. We assume that $m+n \neq n$ for some $n \in \mathbb{N}$.

Suppose that $m+n+1=n+1$. Then the successors of $(m+n)$ and $n$ are the same, and by Peano's Axioms, $m+n=n$.

But this is a contradiction to our inductive hypothesis that $m+n \neq n$.

Thus, for all $n, m \in \mathbb{N}, m+n \neq n$.

Your proof lacks quantifiers. The case $n=1$ should be:$$(\forall m\in\mathbb{N}):m+1\neq1.$$And the induction hypothesis should be: for some $n\in\mathbb N$, we have$$(\forall m\in\mathbb{N}):m+n\neq n.$$But the global idea of your proof is correct.