3
$\begingroup$

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!

  • 0
    This is very close to this question: http://math.stackexchange.com/questions/77227/proving-this-relation-is-transitive. Perhaps this more general result might interest you, too: http://www.proofwiki.org/wiki/Equivalence_Relation_on_Semigroup_Product_with_Cancellable_Elements2011-11-06
  • 0
    Rather than leave you floundering, I’ve expanded my answer. (But it’s now 0800, and I’m going to bed.)2011-11-06

4 Answers 4

1

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

  • 0
    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$?2011-11-06
  • 0
    No, you can't. But see my additional hint in the answer.2011-11-06
4

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.

  • 0
    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$.2011-11-06
  • 0
    I don't think you have the right to do that.2011-11-06
  • 0
    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$?2011-11-06
  • 1
    @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$.2011-11-06
  • 0
    Thanks a lot for the example, you are completely right!2011-11-06
3

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

  • 0
    Hi Brian, thanks for the reply. The professor suppose it doesn't include 0.2011-11-06
  • 0
    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?2011-11-06
  • 0
    $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$?2011-11-06
  • 0
    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?2011-11-06
  • 0
    @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?2011-11-06
  • 0
    Right, so if I understood this right, it's only one equivalence class, which means it only has one image, which means it's injective. In your class the equivalence class is $(3*x, x)$, which builds an image to 6. I didn't get the point of your last question? Why do I have to a pick one rational? I thought it was about a function? I'm going to read on equivalence classes, I guess I'm a little confused. thank you for your kind help2011-11-06
  • 0
    @Clash: $\widetilde{(6,2)}$ and $\widetilde{(3,1)}$ are two different-looking names for the same equivalence class. $6/2$ and $3/1$ are two different names for the same rational number. Wouldn’t that rational be the natural one to assign to $\widetilde{(6,2)}$? Similarly, $\widetilde{(6,4)}$ and $\widetilde{(9,6)}$ are different names for the same equivalence class, and $6/4$ and $9/6$ are different names for the same rational number, $3/2$. Why not try $f\big(\widetilde{(9,6)}\big)=3/2$?2011-11-06
  • 0
    sorry Brian, I still don't get it, $f\big(\widetilde{(9,6)}\big)$ is an injective function? Isn't it's image always $3/2$? How is it a function if it doesn't have any parameters?2011-11-06
  • 0
    @Brian +1 I had changed the notation in the question; so I took the liberty to do so in your post as well. Hope it's ok.2011-11-06
  • 0
    many thanks brian!2011-11-06
2

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}$?