# Equivalence Classes

1. Apr 1, 2013

### mliuzzolino

1. The problem statement, all variables and given/known data

Consider the relation on $\mathbb{N}$ given by aRb if there exists k $\in$ $\mathbb{Z}$ such that a/b = 2k.

Give an example of two different equivalence classes (that is, find x, y $\in \mathbb{N}$ such that Ex $\neq$ Ey, where Ex and Ey are the equivalence classes of x and y; respectively).

2. Relevant equations

Ex = {n $\in \mathbb{N}$: x ~ n}.

Ey = {n $\in \mathbb{N}$: y ~ n}.

a ~ b by a/b = 2k

3. The attempt at a solution

I'm having an incredibly difficult wrapping my head around the concept of equivalence classes in the context of this problem. I'm not sure where to even begin, so forgive me if I'm off to a very incorrect start...

Let k = 1, so 2 = a/b --> a = 2b where 2 = n $\in \mathbb{N}$
Then let k = -1, so 1/2 = a/b --> b = 2a where 1/2 = n $\in \mathbb{N}$

Then a = 2(2a), where a $\neq$ 4a.

Therefore, I have no idea what any of this means...

2. Apr 1, 2013

### Staff: Mentor

Don't let k be something. k can be any integer, and there are too many to consider them individually.

It is easier to start with some arbitrary a. Let's use 6.
We know that b ~ 6 if there is an integer k such that 6/b = 2k.
Can we find some b? b=3 is an example, as 6/b=2 = 21. Therefore, 6~3.
b=12 is another example, as 6/12=1/2 = -1. Therefore, 6~12.
Can you find more examples?

As we have an equivalence relation, this implies 12~3. As you can see, this is "equivalent to", not "equal to", therefore we don't get a contradiction "12=3".
If you go back to your approach, you showed (in general) that a ~ 4a.

3. Apr 1, 2013

### LCKurtz

Start by writing down what subsets of $\mathbb{N}$ are $E_1,\ E_2,\ E_3$ and see if that gives you any ideas.

4. Apr 1, 2013

### mliuzzolino

Alright. More equivalencies of the a = 6 would be: 6~3, 6~6, 6~12, 6~24, etc.

I did a similar process for a = 1 and obtained the equivalencies of: 1~1, 1~2, 1~4, 1~8.

Then I chose a b that wasn't in this relationship, so b = 3.

I let my two different equivalence classes be:

Ea = {2n, n $\in \mathbb{N}$},

Eb = {3*2k, k $\in \mathbb{Z}$}.

I am not sure that I quite wrap my head around what is happening here, but it seems that I can say Ea and Eb are the equivalence classes of a = 1 and b = 3, respectively. Since 1 is not related to 3 by a/b=2k, can I say that their respective equivalence classes are different?

5. Apr 2, 2013

### Staff: Mentor

Right.

For the definition of Eb (I would call it E3 I think), you should restrict k to the natural numbers (including 0), as 3/2, 3/4, ... are not natural numbers.