# Equivalence Relation Proof

• August 4th 2009, 03:51 AM
Roam
Equivalence Relation Proof
Define a relation ~ on N whereby a~b if and only if there exists $k \in Z$ such that $\frac{a}{b} = 2^k$.

(a) Prove that ~ is an equivalence relation.
(b) Write out the equivalence classes for ~ on the set {1,2,3,....10}

Here's my attempt at part (a):

To show that ~ is an equivalence relation, I must show that it's reflexive,symmetric and transitive:

* ~ is reflexive $\Longleftrightarrow$ a~a $\forall a \in Z$
$\Longleftrightarrow \frac{a}{a} = 2^k$

But we know: $\frac{a}{a} = 1$, well I'm sort of stuck here and I don't know how to conclude that ~ is reflexive...

* ~ is symmetric $\Longleftrightarrow$ a~b $\Rightarrow$ b~a

$\Longleftrightarrow \frac{a}{b} = 2^k \Rightarrow \frac{b}{a} = 2^k$

We can suppose $\frac{a}{b} = 2^k$ and then try to show that $\frac{b}{a} = 2^k$ but I don't know how to do it...

* ~ is transitive if and only if a~b $\wedge$ b~c $\Rightarrow$ a~c

$\Longleftrightarrow$ $\frac{a}{b}=2^k \wedge \frac{b}{c} = 2^k \Rightarrow \frac{a}{c} = 2^k$

Suppose $\frac{a}{b}=2^k \wedge \frac{b}{c} = 2^k$ then:

$\frac{a}{c} = \frac{a}{b} + \frac{b}{c}$ $= 2^k + 2^k = 2^{2k} = 4.2^k$

I'm not sure how to continue this part either... any help with this problem is greatly appreciated.
• August 4th 2009, 04:15 AM
Swlabr
Your problems in parts 1 and 2 - reflexivity and symmetricity (is that a word?) - are easily resolved if you remember that $k \in \mathbb{Z}$. In the first one, take $k=0$, and in the second remember that $1/2^k = 2^{-k}$.

For the 3rd part note that the value of $k$ does not matter, as long as some $k$ exists. Thus, you have shown that the $k$ in this instance is actually just $k'=4k$.

For instance, if we take the equivalence class of all numbers of the form $2^n$, clearly $4/2=2$ so $4 \sim 2$. Also, $2/4=1/2=2^{-1}$ so $2 \sim 4$. Further, $16/4=4$ so $16 \sim 4$, and also $4/16=4^{-1}$ so $4 \sim 16$. Then, $16/2=8$ so $16 \sim 2$.

So we have an example of symmetricity and transitivity.
• August 4th 2009, 04:26 AM
Plato
Note: We are assuming that $\mathbb{N}=\{1,2,3,..\}$.

For the reflexive property: $a^0~\&~0\in \mathbb{Z}$.

For the symmetric property note that $a^{-1}=\frac{1}{a}~\&~-1\in \mathbb{Z}$.

For the transitive property note that $\frac{a}{b}=2^m~\&~\frac{b}{c}=2^n \Rightarrow\frac{a}{c}=2^{m+n}$.
• August 4th 2009, 04:36 PM
Roam
OK thanks very much Plato and Swlabr! I got it.

Now I need some help with part (b), I don't really understand what to do:

Quote:

(b) Write out the equivalence classes for ~ on the set {1,2,3,....10}
• August 4th 2009, 05:01 PM
Plato
Quote:

Now I need some help with part (b), I don't really understand what to do:
(b) Write out the equivalence classes for ~ on the set {1,2,3,....10}
Can you show that $[1]=\{1,2,4,8\}$?
Can you show that $[3]=\{3,6\}$?
Can you show that $[5]=\{5,10\}$?
What about $[7]~\&~[9]?$
• August 4th 2009, 08:24 PM
Roam
Quote:

Originally Posted by Plato
Can you show that $[1]=\{1,2,4,8\}$?
Can you show that $[3]=\{3,6\}$?
Can you show that $[5]=\{5,10\}$?
What about $[7]~\&~[9]?$

Frankly I can't follow what you've done there... I know that if ~ is a relation then for $a \in A$ we define the set of relatives of "a" as:
$T_{a}$ = { $x \in A$ : a~x}
And in the case when ~ is an equivalence relation on a set A then each $T_{a}$ is called an equivalent class.

I appreciate it if you can explain what you've done in your last post so that I can follow, and why did you choose the odd numbers? What about {2,4,6,8}?
• August 4th 2009, 09:02 PM
Gamma
The equivalence relation basically amounts to two things are equivalent if and only if the ratio of the two integers have a ratio that is a power of two (note this includes $2^0=1$ this is the reflexive part of the equivalence relation). We know that equivalence relations partition, so what he has done is just figured out which things are in equivalence classes together.

start with 1, what things have ratios that are powers of two with 1.
2 does because $\frac{2}{1}=2=2^1$. 4 does because $\frac{4}{1}=4=2^2$. 8 does because $\frac{8}{1}=8=2^3$. That is all of them. You have already verified that the relation is transitive, so there is no need to check them against one another, it will work out pretty obviously.

So what have we missed? 3 is the next one, anything that is a ratio of a power of two? yeah 6 is because $\frac{6}{3}=2=2^1$. That's it.

Next is 5. Well $\frac{10}{5}=2=2^1$ so 10 is in there, and that is it.

next is 7, the only thing left that hasn't already been assigned is 9, clearly they are not a ratio of a power of 2, so they can't be in the same equivalence class. This means each of these must be in their own class.

That is why Plato's post is complete.
• August 4th 2009, 11:19 PM
Swlabr
In general,

$[a]=[b]$ $\Leftrightarrow$ $a=k2^m$ and $b=k2^n$, with a $k$ fixed natural number and $m$ and $n$ natural numbers. This is because in the rations the k's will cancel.
• August 5th 2009, 01:19 PM
HallsofIvy
Quote:

Originally Posted by Roam
Frankly I can't follow what you've done there... I know that if ~ is a relation then for $a \in A$ we define the set of relatives of "a" as:
$T_{a}$ = { $x \in A$ : a~x}
And in the case when ~ is an equivalence relation on a set A then each $T_{a}$ is called an equivalent class.

I appreciate it if you can explain what you've done in your last post so that I can follow, and why did you choose the odd numbers? What about {2,4,6,8}?

The first thing you should have done on this problem, in order to make sure you understood what you were given, was to actually write down some "equivalent" pairs. For example, what numbers are equivalent to 1? Since a~b if and only if $a/b= 2^k$ for some k, taking b= 1, we are looking for numbers, a, such that $a/1=a= 2^k$. It should be clear that those are just the powers of 2: 2, 4, 8, 16, etc. Since you are asked onlyfor numbers from 1 to 10, those are {1, 2, 4, 8}.

What numbers are equivalent to 2? That's easy, since 2 was in that previous set, it is just {1, 2, 4, 8} again.

What numbers are equivalent to 3? Now, taking b= 3, we have $a/3= 2^k$ so that $a= 3(2^k)$- 3 times powers of 2: $3(2^0)= 2$, $3(2^1)= 6$, $3(2^2)= 12$, etc. The "equivalence class" is {3, 6} (12 is not between 1 and 10).

4 was already in the first equivalence class so its class is {1, 2, 4, 8} again.

If b= 5, $a/5= 2^k$ yields $a= 5(2^k)$: 5 times different powers of 2: $5(2^0)= 5$, $5(2^1)= 10$ $5(2^2)= 20$. The only ones of those between 1 and 10 are 5 and 10: {5, 10}

6 was in the class {3, 6} so its class is also {3, 6}.

If b= 7, $a/7= 2^k$ so $a= 7(2^k)$, {7, 14, 28, ...} the only one of which is between 1 and 10 is 7: {7}.

8 is already in {1, 2, 4, 8} and 10 is in {5, 10}.