Is this proof of the cancellation law for natural numbers alright?

105 Views Asked by At

For starters:

  • $\mathbb{N_{0}}$ means $0\in \mathbb{N}$
  • We define the addition between natural numbers (the suggested reading for my class does) as follows: Let $m$ and $n$ be natural numbers.

\begin{align*}n+0=0+n=n\tag{$a$}\\ n+(m+1)=(n+m)+1\tag{$b$} \end{align*}

Our goal is to show: $\forall m,n,p\in \mathbb{N_{0}}: m+p=n+p\implies m=n$.

Proof. Let $m\in \mathbb{N_{0}}$ and $n\in \mathbb{N_{0}}$.

Base case: If $p=0$ and $m+p=n+p$, \begin{align*} m+p&=n+p\\ m&=n\end{align*}

Induction step: Assume that for a fixed $q\in \mathbb{N_{0}}$\begin{align*}m+q=n+q\implies m=n\tag{$i$}\end{align*}Furthermore, let's suppose\begin{align*}m+(q+1)=n+(q+1)\tag{$ii$}\end{align*} Observe that according to $(i)$: \begin{align*}m\ne m\implies m+q\ne n+q.\tag{$iii$}\end{align*}

From $(b)$ we establised that $(ii)$ is equivalent to $(m+q)+1=(n+q)+1$.

Now, by way of contradiction we hypothesize the antecedent of $(iii)$. But such foregoing assumption would imply that, in particular, for the $q=1$ case it's true that $m+q\ne n+q$ no matter what $m$ and $n$ are because $q$ is fixed/constant after all but arbitrary.

So, by this contradiction against $(ii)$ we've shown ${m+(q+1)=n+(q+1)\implies m=n}$.

1

There are 1 best solutions below

0
On

Long comment

IMO it does not work: if we use in the proof $m≠n → (m+q≠n+q)$, this is exactly what we have to prove.

The "trick" is that in (a) and (b) above you are using $+$ in the def of $+$ and this is incorrect. In the definition of the binary operation $+$ we have to use the unary function $s$ (successor).

We assume (ii) and we get (iii) $s(m+q)=s(n+q)$ using the defintion of $+$.

By Axiom for successor: $\forall x \forall y\ (s(x)=s(y) \to x=y)$, we get $m+q=n+q$ and now we can use the induction hypotheses concluding with $m=n$.