1
$\begingroup$

How to prove that Multiplication has a cancellation property if $\langle 0, 0 \rangle$ is not a member of the factor to be canceled.

  • 0
    Also, what's so fundamental about this lemma?2011-08-29

1 Answers 1

8

You start with the natural numbers $\mathbb{N}$, which include $0$. The book linked to by Chandrasekhar assumes the usual properties of addition, multiplication, and order of natural numbers as part of the axiomatic set-up; these properties include cancellation for nonzero natural numbers.

Then we define an equivalence relation on $\mathbb{N}\times\mathbb{N}$ by $(a,b)\sim (c,d) \Longleftrightarrow a+d = b+c.$ It is not hard to establish that this is indeed an equivalence relation. We define the set $\mathbb{Z}$ to be the set $\mathbb{N}/\sim$ of equivalence classes modulo $\sim$. Let $[a,b]$ denote the equivalence class of $(a,b)$ under $\sim$.

We define addition of integers by $[a,b]+[c,d] = [a+c,b+d].$ This is well-defined, and has the usual properties of addition.

Then we define multiplication of integers by: $[a,b]\times [c,d] = [ac+bd, ad+bc].$

Since your question is about multiplication, I'll start actually proving things here.

Theorem. Multiplication is well defined. That is, if $(a,b)\sim (x,y)$ and $(c,d)\sim (v,w)$, then $(ac+bd,ad+bc) \sim (xv+yw, xw+yv)$.

Proof. First, I prove that $(ac+bd, ad+bc) \sim (xc+yd, xd+cy)$; indeed, we know that $a+y = b+x$. Multiplying by $c$, we have $ac+yc = bc+xc$. Multiplying by $d$, we get $ad+yd=bd+xd$. So $(ac+yc)+(bd+xd) = (bc+xc)+(ad+yd)$, which proves that $(ac+bd,ad+bc)\sim (xc+yd,xd+cy)$.

Next, I prove that $(xc+yd, xd+cy)\sim (xv+yw, xw+yv)$. We know $c+w=d+v$; multiplying by $x$ and by $y$, we get $xc + xw = xd+xv$ and $yc+yw = yd+yv$. Therefore, $(xc+xw)+(yd+yv) = (xd+xv) + (yc+yw)$, which is what we want. By transitivity, we get the result. $\Box$

Therefore, multiplication of integers is well defined.

Theorem. Multiplication is commutative, associative, and distributes over sums.

Proof. Simply a matter of computing. $\Box$

Theorem. If $[a,b][x,y] = [a,b][r,s]$ and $a\neq b$, then $[x,y]=[r,s]$.

Proof. $[a,b][x,y] = [ax+by, ay+bx]$; $[a,b][r,s] = [ar+bs,as+br]$. Equality means that $ax+by+as+br = ay+bx+ar+bs.$ We want to show that $x+s = y+r$. These are all natural numbers, so the usual properties hold.

Note that $ax+by+as+br = a(x+s) + b(y+r)$ and $ay+bx+ar+bs = a(y+r) + b(x+s)$.

If $a\lt b$, then we can write $b=a+h$ with $h\gt 0$. Then we have $\begin{align*} a(x+s) + b(y+r) &= a(y+r) + b(x+s)\\ a(x+s) + a(y+r) + h(y+r) &= a(y+r) + a(x+s) + h(x+s)\\ h(y+r) &= h(x+s). \end{align*}$ Since $h\neq 0$, then $y+r=x+s$, as desired. If $a\gt b$, then we can write $a=b+h$ with $h\gt 0$, and a similar computation again shows that $x+s=y+r$, as desired. $\Box$

Now, note that $(0,0)\in[a,b]$ if and only if $(0,0)\sim (a,b)$, if and only if $a=b$. Therefore, in the integers (i.e., in $(\mathbb{N}\times\mathbb{N})/\sim$) we have that $[a,b][x,y] = [a,b][r,s]$ if and only if the ordered pair $(0,0)$ is not one of the elements of the equivalence class $[a,b]$.