In textbook A Course in Mathematical Analysis by prof D. J. H. Garling, the author proves the cancellation law in multiplication before he moves on to prove the trichotomy of order. I have tried to prove by induction many times but to no avail. Please shed some light!
Below are properties of addition and multiplication that I can use:
- Peano's axioms
- Definition of Addition: Considering the (successor) mapping $s:\mathbb{N} \to \mathbb{N}$, setting $m_0=m$, and using recursion, there exists a sequence $(m_n)_{n \in \mathbb{N}}$ such that $m_0=m$ and $m_{s(n)}=s(m_n)$. Define $m+n:=m_n$. Thus $m=m+0$ and $s(m)=m+1$. Hence the equation $m_{s(n)}=s(m_n)$ becomes $m+(n+1)=(m+n)+1$.
- Definition of Multiplication: Suppose that $n \in \mathbb{N}$. Using recursion, there exists a sequence $(p_m)_{m \in \mathbb{N}}$ such that $p_0=0$ and $p_{m+1}=p_m+n$. Define $m.n:=p_m$.
- $m+n=n+m$
- $(m+n)+p=m+(n+p)$
- $m+n=p+n \implies m=p$
- $m+n=0 \implies m=n=0$
- $m.n=n.m$
- $0.n=0$ and $1.n=n$
- $(m.n).p=m.(n.p)$
Now I want to prove the cancellation law on multiplication:
$m.n=p.n \wedge n \neq 0 \implies m=p$
Here is my take:
Let $U=\{n \in \mathbb{N}^{*} \mid m.n=p.n \implies m=p, \text{ for all } m,p \in \mathbb{N}\}$ and $V=U \cup \{0\}$.
It's clear that $0 \in V$.
Assume $n \in V$. Then $m.n=p.n \implies m=p$.
Now we prove $n+1 \in V$ i.e. $m.(n+1)=p.(n+1) \implies m=p$. To prove this, it is equivalent to prove $m.(n+1)=p.(n+1) \implies m.n=p.n$.
I don't know how to precede to prove $m.(n+1)=p.(n+1) \implies m.n=p.n$
PS: I updated the excerpt from textbook. As you can see, the author proves the cancellation law in multiplication (Theorem 2.1.2) before he proves the trichotomy of order (Theorem 2.1.5).
