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.

  • $\begingroup$ Thanks for the quick feedback! I'll throw those in. I appreciate it! $\endgroup$ – Austin Aug 24 '18 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.