Let R by a relation defined on pairs $(m,n)$ of integers $m$ and natural numbers $n$ by $(i,j) R (k,l)$ if $il=jk$. Prove that this is an equivalence relation and give the equivalence cases. Show you found all the equivalence classes and that these are different. What do these equivalence classes represent?

This is a problem in my textbook, for which there is no solution in the solution manual and I'm having trouble figuring this out completely. This is what I've done up until now:

$i,l \in \mathbb{Z}$ and $j,l \in \mathbb{N}$, so we know that every $il, jk \in \mathbb{Z}$.

To prove it is an equivalence class, we need to prove that it is reflexive(1), reflexive(2) and transitive(3).

(1) For every $il,jk \in \mathbb{Z}$ we have $il=il$ and $jk=jk$.

(2) For every $il,jk \in \mathbb{Z}$ we have that if $il=jk$, then $jk=il$.

(3) For every $il,jk \in \mathbb{Z}$ we have that if $il=jk$ and $jk=C$, then $il=C$.

I know the above might not be completely rigorous, but I understand it intuitively. My problems start after this part. What are the equivalence classes of this relation? I know what an equivalence class is from reading some examples online, but all of the examples are different to this one. I have no clue what all of them are.

  • $\begingroup$ @Travis But why would you want to do that? I know that's what they're aiming for (rationals), but I have no idea why. Equivalence classes are horribly explained in my book. $\endgroup$
    – DaveAzp
    Oct 14 '14 at 4:34
  • $\begingroup$ The purpose of the exercise is just that this gives a rigorous definition of the rational numbers in terms of the integers, and all of the familiar properties of the rational numbers can be proved in terms of this definition. $\endgroup$ Oct 14 '14 at 4:48
  • $\begingroup$ @Travis Yes, that's what I found out from looking up this problem online, but my question is mainly about the "find all equivalence classes" problem. I have no idea how to do this, or why a ratio of the numbers is an equivalence class, and what else would constitute an equivalence class, etc. $\endgroup$
    – DaveAzp
    Oct 14 '14 at 4:50
  • $\begingroup$ The original question is not clearly formulated. I might interpret it as, "show that all rational numbers are represented by an equivalence class", but this is almost tautological. $\endgroup$ Oct 14 '14 at 4:53
  • $\begingroup$ Also, the proofs of the equivalence class criteria could be more precisely stated. For example, for symmetry, we must show that if $(i, j) \sim (k, l)$ then $(k, l) \sim(i, j)$. But the former means that $il = jk$, so $jk = il$, and thus $(k, l) \sim (i, j)$. $\endgroup$ Oct 14 '14 at 4:55

$(k,a)R(l,b)\Leftrightarrow kb=la$, where a,b,... >0 and $k,l,...\in\mathbb Z$.

Reflexive: $ka=ka\Rightarrow (k,a)R(k,a)$.

Symmetric: $(k,a)R(l,b)\Rightarrow kb=la\Rightarrow la=kb\Rightarrow (l,b)R(k,a)$.

Transitive: $(k,a)R(l,b)\wedge (l,b)R(m,c)\Rightarrow kb=la \wedge lc=mb\Rightarrow$ $kbc=lac \wedge lac=mba\Rightarrow$$ kbc=mba\Rightarrow $ $kc=ma\Rightarrow (k,a)R(m,c)$ because $b>0$.

The set of all equivalence classes $\overline{(k,a)}$ is in one-to-one correspondence with all rational numbers: $\phi(\overline{(k,a)})=\displaystyle\frac{k}{a}$, because: $\phi$ is well defined, $\overline{(k,a)}=\overline{(l,b)}\Rightarrow kb=la\Rightarrow \displaystyle\frac{k}{a}=\frac{l}{b}$.

$\phi$ is injective because $\phi(\overline{(k,a)})=\phi(\overline{(l,b)})\Rightarrow\overline{(k,a)})=(\overline{(l,b)})$ Prove!

$\phi$ is surjective because any $\displaystyle\frac{k}{a}$ is mapped to.

Define addition, subtraction, multiplication and division for the classes, inspired by the corresponding operations on the rational numbers. Then prove that


and the same for multiplication. Then, you have showed that the set of equivalence classes is isomorphic to $\mathbb Q$, the rational numbers.

Everyone studying abstract algebra has to establish morphisms as above a lot of times.


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.