Let $E$ be an equivalence relation on the set of all ordered pairs of non-negative integers ($N\times N$). It is defined as $$(a,b)E(x,y) \Longleftrightarrow a+y = b+x$$

Multiplication ($*$) is defined as $$(a,b)*(x,y) = (ax+by, ay+bx)$$

Without using substraction or division, how can I show that $E$ is consistent with $*$ ?

By consistent I mean that if $(a,b)E(a', b')$ and $(x,y)E(x',y')$ then $(a,b)*(x,y)E(a',b')*(x',y')$

Right now I have laid down all the information about the problem:

Let $(a,b)$, $(a',b')$, $(x,y)$ and $(x',y')$ $\in N \times N$. Suppose $(a,b)E(a',b')$ and $(x,y)E(x',y')$.

We have: $$(a,b)E(a',b') \Longleftrightarrow a+b'= b+a'$$ $$(x,y)E(x',y') \Longleftrightarrow x+y'= y+x'$$ and I want to show that the following is true $$(a,b)*(x,y)E(a',b')*(x',y')$$ The expansion of the preceding statement gives this: $$ax+by+b'x'+a'y'=^{?} bx+ay+a'x'+b'y'$$

I spent some time thinking about it but I can't find a way to do that. Thanks for the help!

  • $\begingroup$ As a reference, this problem is from Elias Zakon's Basic Concepts of Mathematics, chapter 1.7 problem 5. trillia.com/zakon1.html $\endgroup$ – Olivier Jan 13 '14 at 0:58

What you have in front of you is actually a construction of the integers $\mathbb{Z}$ from the non-negative integers $N$. Define a surjection $\pi : N \times N \to \mathbb{Z}$ by $\pi(x,y) = x-y$. You should find that $(x,y) E (a,b)$ if and only if $\pi(x,y) = \pi(a,b)$. So, you can identity $E$-equivalence classes with integers!

Now, regarding consistency of $*$, observe that $$\pi( (x,y)*(a,b)) = \pi(x,y) \pi(a,b)$$ where juxtaposition is ordinary multiplication of integers. Does this help you?


I did not see your request there be no reference to subtraction at first. So here is a more direct approach.

Claim 1: If $(a,b),(a',b'),(x,y) \in N \times N$ and $(a,b) E (a',b')$, then $[(a,b)*(x,y)] E [(a',b') * (x,y)]$.

Proof: Since $(a,b)E(a',b')$, we have $$ a+b' = b+a'.$$ Thus, we get $$(a+b') x + (b+a')y = (b+a')x + (a+b')y$$ which expands out to $$(ax+by) + (a'y+b'x) = (ay+bx)+(a'x+b'y)$$ which says exactly that $$[(a,b)*(x,y)] E [(a',b') * (x,y)].$$

Similarly, you can prove

Claim 2: If $(a,b),(x,y),(x',y') \in N \times N$ and $(x,y) E (x',y')$, then $[(a,b)*(x,y)] E [(a,b) * (x',y')]$.

Now, consistency of $*$ follows from transitivity of $E$, which I presume you have already checked? Transitivity of $*$ needs the cancellation law $x+a =y+a \Rightarrow x=y$ to have been established for $(N,+)$.

  • $\begingroup$ The question said "without using subtraction or division", so it seems that the function you call $\pi$ isn't available. $\endgroup$ – Andreas Blass Jan 13 '14 at 0:36
  • $\begingroup$ It's an interesting answer but it does indeed go around the idea of not using subtraction. $\endgroup$ – Olivier Jan 13 '14 at 0:51
  • $\begingroup$ @Andreas: Ah sorry about that, fixing it now. $\endgroup$ – Mike F Jan 13 '14 at 0:54
  • $\begingroup$ Great! Thank you, I get it now. I didn't thought of dividing the proof in two steps, and then combining them using the transitivity of E (which I indeed already checked). Thanks a lot! $\endgroup$ – Olivier Jan 13 '14 at 1:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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