# The equivalence relation $(z_1, n_1)\sim(z_2, n_2) :\Leftrightarrow z_1 \cdot n_2 = z_2 \cdot n_1$

Given the relation $(z_1, n_1)\sim(z_2, n_2) :\Leftrightarrow z_1 \cdot n_2 = z_2 \cdot n_1$ on the set $\mathbb Z \times \mathbb N$.

a) Prove that $\sim$ is an equivalence relation.

Here is how I've proven it, could someone check if it's right?

• Reflexive: $a\sim a$: $z_1 \cdot n_1=z_1 \cdot n_1$ (is it always this trivial for equations?)

• Symmetric: $a\sim b \Rightarrow b\sim a$: $z_1 \cdot n_2=z_2 \cdot n_1\Rightarrow z_2 \cdot n_1=z_1 \cdot n_2$

• Transitive: $a\sim b \land b\sim c \Rightarrow a\sim c$. $$z_1 \cdot n_2=z_2 \cdot n_1 \land z_2\cdot n_1=z_3 \cdot n_3 \Rightarrow z_1 \cdot n_2 = z_3 \cdot n_3 .$$

I think got this last one wrong because of the $z_3 \cdot n_3$, this is not respecting the relation that is: $(z_1, n_1)\sim(z_2, n_2) :\Leftrightarrow z_1 \cdot n_2 = z_2 \cdot n_1$. But how can I make a new pair $c$ that is not the same as $a$? Am I allowed to rewrite it to $\frac{z_1}{n_1}=\frac{z_2}{n_2}$? Then I could write $$\frac{z_1}{n_1}= \frac{z_2}{n_2} \land \frac{z_2}{n_2} = \frac{z_3}{n_3} \Rightarrow \frac{z_1}{n_1}= \frac{z_3}{n_3} .$$

b) Give one bijective function of the set $M$ of equivalence classes, where $M = \{ (\widetilde{z, n}) \mid (z, n) \in \mathbb Z \times \mathbb N\}$ on the set $\mathbb Q$. A little lost here. Any directions?

(a) You were doing fine until you got to transitivity. There your assumption is that $(z_1,n_1)\sim(z_2,n_2)$ and $(z_2,n_2)\sim(z_3,n_3)$, and you want to prove that $(z_1,n_1)\sim(z_3,n_3)$. Begin by translating these into the language of the specific relation $\sim$. You know that $$z_1 \cdot n_2 = z_2 \cdot n_1\tag{1}$$ and that $$z_2 \cdot n_3=z_3 \cdot n_2,\tag{2}$$ and you want to show that $$z_1 \cdot n_3=z_3 \cdot n_1.\tag{3}$$

Notice that in your version you got both $(2)$ and $(3)$ wrong: you didn’t correctly translate $(z_2,n_2)\sim(z_3,n_3)$ and $(z_1,n_1)\sim(z_3,n_3)$.

Now, how can you use $(1)$ and $(2)$ to get $(3)$? In you could get something involving $z_1 \cdot n_3$ on the lefthand side by multiplying $(1)$ and $(2)$ together: $$z_1 \cdot n_2 \cdot z_2 \cdot n_3=z_2 \cdot n_1 \cdot z_3 \cdot n_2.\tag{4}$$ Let’s isolate the parts of interest on each side of $(4)$: $$(z_1 \cdot n_3) \cdot (n_2\cdot z_2)=(z_3 \cdot n_1) \cdot (n_2 \cdot z_2)\;.\tag{5}$$ Look at the unwanted parts: they’re the same on both sides. It would be nice to cancel them, but be careful: they could be $0$, in which case cancellation wouldn’t be possible. You’ll have to deal with that possibility as a separate, special case. If $n_2 \cdot z_2=0$, why is $(3)$ still true?

(b) You’ve almost hit on the right idea in your own post. If $(z_1,n_1)\sim(z_2,n_2)$, what can you say about the rational numbers $\dfrac{z_1}{n_1}$ and $\dfrac{z_2}{n_2}$? (I’m assuming that for you $\mathbb{N}$ does not include $0$; be aware that for many of us it does, so you should always specify which version you mean.)

Added: You want a bijection from $f:M\to\mathbb{Q}$, where $$M=\left\{\widetilde{(z,n)}:(z,n)\in\mathbb{Z}\times\mathbb{N}\right\}.$$ Each $\widetilde{(z,n)}\in M$ has many names; for example, $$\widetilde{(3,2)}=\widetilde{(6,4)}=\widetilde{(18,12)}\;.$$ Similarly, each rational number has many names; for example, $$\frac32=\frac64=\frac{18}{12}.$$ What’s the rule for deciding whether $\widetilde{(z_1,n_1)}$ and $\widetilde{(z_2,n_2)}$ are two names for the same member of $M$? That’s the case if and only if $(z_1,n_1)\sim(z_2,n_2)$, so $$\widetilde{(z_1,n_1)}=\widetilde{(z_2,n_2)}\iff z_1n_2=z_2n_1\;.\tag{6}$$

Now what’s the rule for deciding whether $\frac{z_1}{n_1}$ and $\frac{z_2}{n_2}$ are different names for the same rational number? $$\frac{z_1}{n_1}=\frac{z_2}{n_2}\iff z_1n_2=z_2n_1\;.\tag{7}$$

Now $(6)$ and $(7)$ look an awful lot alike, so why not try the map $$f:M\to\mathbb{Q}:\widetilde{(z,n)}\mapsto\frac{z}n\;?$$ There’s still a fair bit of work to be done: you have to show that $f$ is well-defined, meaning that if $\widetilde{(z_1,n_1)}=\widetilde{(z_2,n_2)}$, then $f\big(\widetilde{(z_1,n_1)}\big)=f\big(\widetilde{(z_2,n_2)}\big)$, and you have to check that it really is a bijection.

• Hi Brian, thanks for the reply. The professor suppose it doesn't include 0. – Clash Nov 6 '11 at 11:45
• I guess my function is right there: $\dfrac{z_1}{n_1}=\dfrac{z_2}{n_2}$. They are rational numbers and it's certainly bijective, because $n \in \mathbb N$, right? Wait, 5/5, 2/2, they are going to have the same image 1. This isn't bijective then... hmmm what about $z\neq n$. Hm still not going to work... 6/2, 3/1, both build to 3... how can I write that $z$ and $n$ can't be divisible by each other? – Clash Nov 6 '11 at 11:47
• $6/2=3/1$; is it true that $(6,2)\sim(3,1)$? $(-3,2)\sim(-9,6)$; is it true that $-3/2=-9/6$? – Brian M. Scott Nov 6 '11 at 11:51
• Everything you wrote is true, but I don't follow. These values are all having the same image, which means it isn't injective, right? – Clash Nov 6 '11 at 11:58
• @Clash: The map doesn’t take pairs $(z,n)$ to rationals: it takes equivalence classes of pairs to rationals. $(6,2)\sim(3,1)$, so $\widetilde{(6,2)}=\widetilde{(3,1)}$. It’s one equivalence class, so it can go to only one rational; which rational looks like a good candidate? – Brian M. Scott Nov 6 '11 at 12:07

I will start by transitivity, (reflexivity and symmetry were done right): We have $z_1 \cdot n_2 = z_2 \cdot n_1$ and $z_2 \cdot n_3= z_3 \cdot n_2$ then multiply the first equation by $n_3$ and the second equation by $n_1$ it follows: $(z_1 \cdot n_2) \cdot n_3= (z_2 \cdot n_1) \cdot n_3= z_2 \cdot (n_1 \cdot n_3)$ (the last step follows by associativity of $\cdot$) and $(z_2 \cdot n_3) \cdot n_1= (z_3 \cdot n_2) \cdot n_1$ hence using associativity and commutativity of $\cdot$:$z_1 \cdot (n_2 \cdot n_3)=z_3 \cdot (n_2 \cdot n_1)$ and the result follows (I leave the rest as an exercise).

b) For this question observe that you can send $(z,n)$ for $z,n$ to $z/n$ and if for some $(z',n')$ $(z,n) \sim (z',n')$ then $z/n=z'/n'$ so the function is well defined.

• Thanks for the reply. Can I alternatively write $z_2*n_1=z_2*n_3$? This means $n_1=n_3$. I then do the same for $z_1 * n_3=z_3 * n_1$ and get $z_1=z_3$. – Clash Nov 6 '11 at 11:33
• I don't think you have the right to do that. – user17090 Nov 6 '11 at 11:34
• Why not? Isn't the definition $a\sim b \wedge b\sim c \Rightarrow a\sim c$? Doesn't this mean $b=z_2*n_1=z_2*n_3$? – Clash Nov 6 '11 at 11:41
• @Clash: no. To take a concrete example, $(1,2)\sim(2,4)\sim(3,6)$ but $z_2n_1=4\neq 12=z_2n_3$. – Shane O Rourke Nov 6 '11 at 12:02
• Thanks a lot for the example, you are completely right! – Clash Nov 6 '11 at 12:04

Let's have a look at the transitivity requirement: assuming $(z_1,n_1)\sim(z_2,n_2)$ and $(z_2,n_2)\sim(z_3,n_3)$ we need $(z_1,n_1)\sim(z_3,n_3)$. From the definition of $\sim$ this means that we have to show: $$\mbox{If }z_1n_2=z_2n_1\mbox{ and }z_2n_3=z_3n_2\mbox{ then }z_1n_3=z_3n_1.$$ (This is not the same as what you've stated.) So one pointer is to consider $z_1n_2n_3$. Can you express this in terms of $z_3$? Does this help?

As for (b), observe that two rational numbers can be written in the form $z_1/n_1$ and $z_2/n_2$, and that $z_1/n_1=z_2/n_2$ if $z_1n_2=z_2n_1$. Does this suggest a suitable function $f:M\to\mathbb{Q}$?

The proof for transitivity should read $$(z_1\cdot n_2=z_2\cdot n_1) \wedge (z_2\cdot n_3=z_3\cdot n_2) \Rightarrow (z_1\cdot n_3=z_3\cdot n_1).$$ Can you see how to show this? Hint: Try multiplying the two equations on the left.

A hint for (b): For two rational numbers $\dfrac{a}{b}$ and $\dfrac{c}{d}$ we have $$\frac{a}{b}=\frac{c}{d}\Longrightarrow a\cdot d=b\cdot c.$$ This should give you an idea of how to build a bijection $M\to\mathbb Q$.

• Hi Rasmus, thank you for your reply. In the proof transitivity, as $b$ should appear on both sides, can I then assume $n_1=n_3$, which means $z_1=z_3$? – Clash Nov 6 '11 at 11:19
• No, you can't. But see my additional hint in the answer. – Rasmus Nov 6 '11 at 11:45