# Equivalence Relations

1. Mar 26, 2014

### knowLittle

1. The problem statement, all variables and given/known data
Let $H = \{ 2^{m} : m \in Z\}$
A relation R defined in $Q^{+}$ by $aRb$, if $\frac{a}{b} \in H$

a.) Show that R is an equivalence Relation

b.) Describe the elements in the equivalence class [3].

3. The attempt at a solution
For part a, I think I am able to solve it, tell me what you think of my solution:
Assume:
$2^{m} R 2^{m} , m \in Z$
Since, $2^{0} \equiv 1 \equiv \frac{2^{m} }{2^{m} } \in H$
So, R is reflexive, for any m in Z.

Assume:
$2^{m} R 2^{n}$, then $\frac{ 2^{m}} { 2^{m} }, m , n \in Z$
If $m<0 \frac{1}{2^{m} 2^{n}}$ , then it still satisfies $2^{0} , 2^{m+n} \in H$, since m+n is in Z as well.
Without loss of generality for n<0 or both m and n <0.
Thus, $2^{n} R 2^{m}$ and R is symmetric.

Assume:
$2^{m} R 2^{n}$ and $2^{n} R 2^{d}$, since n, m, and d are in Z , they are transitive.

I have problems in part b.
What would an equivalence class [3] mean in this powers of 2 relation?

2. Mar 26, 2014

### PeroK

You've gone about this the wrong way. You must prove R is an equivalence relation on Q+, not on H.

So, you need to show the properties hold for elements of Q+.

3. Mar 26, 2014

### pasmith

3 is a positive rational number. [3] is the equivalence class of 3, ie. the set of all positive rational $a$ such that $aR3$.

4. Mar 26, 2014

### knowLittle

I know that a/b or 3/1 is in $Q^{+}$.
Would be multiples of 3 or numbers that can be divided and reduced into 3/1?

5. Mar 26, 2014

### knowLittle

So, the purpose of mentioning H is to say that whatever a/b is in the form $2^{m}, m \in Z$?
It will always be in Q+.
Could you give one or two examples of elements in this relation class?

6. Mar 26, 2014

### PeroK

You've still got things the wrong way round. You would start, for symmetry say:

Let a, b be in Q+ and aRb, then a/b is in H, so $∃ m \in Z \ s.t. \ a/b = 2^{m}$...

7. Mar 26, 2014

### knowLittle

This is what I don't understand, what if a/b =7. This cannot be explained by $2^{m}$

8. Mar 26, 2014

### PeroK

If a/b = 7 then $a \ notR b$

9. Mar 26, 2014

### vela

Staff Emeritus
In addition to what PeroK said, if a=7 and b=14, neither of which is of the form $2^n$, you'd have aRb because a/b = 1/2 = 2-1.

10. Mar 26, 2014

### pasmith

In the definition of $aRb$, both $a$ and $b$ are strictly positive rationals, and $aRb$ if and only if there exists $m \in \mathbb{Z}$ such that $ab^{-1} \in H = \{2^m : m \in \mathbb{Z}\}$.

Thus, for example, 4/7 and 5/41 are not equivalent, because
$$\frac 47 \div \frac 5{41} = \frac{164}{35} \notin H.$$
On the other hand, 5/8 and 5/16 are equivalent, because
$$\frac 58 \div \frac {5}{16} = 2 \in H.$$

11. Mar 26, 2014

### knowLittle

So, to correct my 'proof' as Perok mentioned:

Last edited: Mar 26, 2014
12. Mar 26, 2014

### LCKurtz

Well, that's a new one. You have made it impossible to quote your revised post. How the hell did you do that?

In any case, it is still messed up, even on reflexive. You have to start with $a\in Q^+$. You aren't given that $a$ is some power of $2$.

If $a\in Q^+$ please state what you have to prove to show $aRa$. Do it in response to this post, not by editing something previous.

13. Mar 27, 2014

### knowLittle

Reflexive:
Assume $a \in Q^+$.
If $a \in Q^+$ and $\frac{a}{a} \in \{2^{m}: m\in Z\}$, then $aRa$.

Since, $\frac{a}{a} \equiv 1 \equiv {2^0}, 0 \in Z$, then $aRa$.

Is this right?

14. Mar 27, 2014

### PeroK

Yes, you're getting there! But, let me tidy things up for you, as you're still thinking a little back to front. And, there's no need for equivalent signs rather than equal signs:

$$Let \ a \in Q^+$$
$$\frac{a}{a} = 1 = 2^0 \in H \ as\ 0 \in \mathbb{Z}$$
$$∴ \ aRa$$
$$∴ \ R \ is \ reflexive$$

15. Mar 27, 2014

### knowLittle

Thanks, Perok and LCKurtz.
Now, I want to prove symmetry.
Let $a,b \in Q^+$

$\frac{a}{b} = 2^m \in H; \frac{b}{a} = 2^n \in H$ for some m,n $\in \mathbb{Z}$

Then, $aRb, bRa$

and R is symmetric.

Is this correct?

16. Mar 27, 2014

### PeroK

I'm afraid not, I'm sorry to say. To prove symmetry you need to show that:

For a, b in Q+, aRb => bRa

In other words, if aRb, then bRa.

This stuff's hard until you get your head round what the hell is going on!

17. Mar 27, 2014

### knowLittle

Ok.
$a,b \in Q^+$

If $aRb , \frac{a}{b} \in H$ for some $2^m , m \in Z$

or $\frac{a}{b} = 2^m$

Solve for b/a:

$\frac{1}{2^m} = \frac{2^0}{2^m} = 2^{-m} = \frac{b}{a}$

Then, $\frac{b}{a} = 2^{-m} \in H$

So, $aRb$ implies $bRa$

Correct

18. Mar 27, 2014

### PeroK

Yes, you've got it!