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?

Thanks in advance!


(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.

  • $\begingroup$ Hi Brian, thanks for the reply. The professor suppose it doesn't include 0. $\endgroup$ – Clash Nov 6 '11 at 11:45
  • $\begingroup$ 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? $\endgroup$ – Clash Nov 6 '11 at 11:47
  • $\begingroup$ $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$? $\endgroup$ – Brian M. Scott Nov 6 '11 at 11:51
  • $\begingroup$ 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? $\endgroup$ – Clash Nov 6 '11 at 11:58
  • $\begingroup$ @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? $\endgroup$ – 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.

  • $\begingroup$ 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$. $\endgroup$ – Clash Nov 6 '11 at 11:33
  • $\begingroup$ I don't think you have the right to do that. $\endgroup$ – user17090 Nov 6 '11 at 11:34
  • $\begingroup$ 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$? $\endgroup$ – Clash Nov 6 '11 at 11:41
  • 1
    $\begingroup$ @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$. $\endgroup$ – Shane O Rourke Nov 6 '11 at 12:02
  • $\begingroup$ Thanks a lot for the example, you are completely right! $\endgroup$ – 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$.

  • $\begingroup$ 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$? $\endgroup$ – Clash Nov 6 '11 at 11:19
  • $\begingroup$ No, you can't. But see my additional hint in the answer. $\endgroup$ – Rasmus Nov 6 '11 at 11:45

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.