Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
What is $\langle 0,0\rangle$, and what does it mean for it to be "a member of the factor"? Multiplication of what? You have both "number theory" (suggesting either natural numbers, integers, or perhaps rationals), and "real-analysis" (suggesting real numbers) in your question. A proof of the cancellation property depends on what you are taking for granted. – Arturo Magidin Aug 29 '11 at 1:21
Please see:… – user9413 Aug 29 '11 at 1:22
@Arturo: Please see my link. I think the sentence has been taken from there. – user9413 Aug 29 '11 at 1:23
@Chandrasekhar: Thanks. In short, we have the natural numbers, define the integers as the equivalence classes of pairs $(m,n)$ with $m,n\in\mathbb{N}$, under equivalence relation $(m,n)\sim(r,s)$ if and only if $m+s=n+r$; and are trying to prove the cancellation property of multiplication in the integers. The book uses $\langle m,n\rangle$ for the ordered pair $(m,n)$. – Arturo Magidin Aug 29 '11 at 1:25
@chandrasekhar I mean to say, that if $ a=b \ne 0$, then $b(a-b)=(a+b)(a-b)$ doesn't mean that $b=a+b$. And Yes! It's an exercise in the book SET THEORY AND LOGIC by RR STOLL. – gaurav Aug 29 '11 at 1:30
up vote 7 down vote accepted

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]$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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