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