2

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:

  1. Peano's axioms
  2. 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$.
  3. 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$.
  4. $m+n=n+m$
  5. $(m+n)+p=m+(n+p)$
  6. $m+n=p+n \implies m=p$
  7. $m+n=0 \implies m=n=0$
  8. $m.n=n.m$
  9. $0.n=0$ and $1.n=n$
  10. $(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).

enter image description here enter image description here enter image description here enter image description here

Akira
  • 17,367
  • No answer from me ... but I remember trying to prove that one without trichotomy as well ... and failed. I don't know how to do this without using some sort of trichotomy at some point. – Bram28 Mar 17 '18 at 02:52
  • Those properties aren't sufficient because there are rings with the same properties where the cancellation law doesn't hold. – Matt Samuel Mar 17 '18 at 03:02
  • @MattSamuel: Of course, we can use Peano's axioms and the definitions of addition and multiplication as well. – Akira Mar 17 '18 at 03:08
  • @MattSamuel I have edited my post to include Peano's axioms and the definitions of addition and multiplication. – Akira Mar 17 '18 at 04:34
  • Just to clarify my earlier comment. of course you can prove the cancellation lemma using the Peano axioms ... but I don't see how you can do this without first using induction to prove some kind of theorem to the effect of $\forall x \forall y (x=y \lor \exists z (x = s(y+z)) \lor \exists z (y =s(x+z)))$ ... which is really just the trichotomy law in disguise. – Bram28 Mar 17 '18 at 12:33
  • @Bram28 I added images from my textbook so that you can have a full look of what the author intended to do. Please have a look at these images. – Akira Mar 17 '18 at 13:51
  • 1
    @DungLe Wow, ok, yeah, there is every suggestion by the author that a straightforward induction would suffice, but as you and I found out the hard way, that is not the case. I'd call this an oversight by the author. – Bram28 Mar 17 '18 at 14:49
  • 1
    There is a good proof using only the axiom in this answer: https://math.stackexchange.com/a/3067506/543323 – Madjosz Jun 18 '20 at 10:58
  • 3
    Does this answer your question? Multiplication cancellation property by Peano axioms – ggg Oct 29 '20 at 13:40

0 Answers0