# Showing the consistency of an equivalence relation over *

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!

• As a reference, this problem is from Elias Zakon's Basic Concepts of Mathematics, chapter 1.7 problem 5. trillia.com/zakon1.html – 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,+)$.

• The question said "without using subtraction or division", so it seems that the function you call $\pi$ isn't available. – Andreas Blass Jan 13 '14 at 0:36
• It's an interesting answer but it does indeed go around the idea of not using subtraction. – Olivier Jan 13 '14 at 0:51
• @Andreas: Ah sorry about that, fixing it now. – Mike F Jan 13 '14 at 0:54
• 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! – Olivier Jan 13 '14 at 1:39