1. ## Equivalence Classes

Let S={-8,-4,-2,0,1,2,5,7} be a subset of Z(integers), and let ~ be a relation defined on S by x~y if $7 | (6x+7)$.

Find all distinct equivalence classes.

Attempt:
Here's my problem: when I want to find one of the equivalence classes, for instance [0], I'm not sure how do it.
In $7 | (6x+7)$ do I need to set $x=0$ or $y=0$???

I checked the solution and the correct answer for this particular problem is setting x to zero:

[0]={ $x \in S : 7|6.0+y = y$}

I'm confused because in many other problems which are very similar we set y=0. I don't see how we can determine this...

2. Originally Posted by Roam
Let S={-8,-4,-2,0,1,2,5,7} be a subset of Z(integers), and let ~ be a relation defined on S by x~y if $7 | (6x+7)$.
Are you sure that it isn't meant to read:

$x$ ~ $y$ iff $7$ | $(6x+$ $y$ $)$ ?

3. Originally Posted by pomp
Are you sure that it isn't meant to read:

$x$ ~ $y$ iff $7$ | $(6x+$ $y$ $)$ ?
Well, there's another problem given to us which is very similar to the one I posted above:

Let S={-5,-3,-2,0,1,6,7,9,13} be a subset of Z, and let ~ be a relation defined on S by x~y if 6|(x+5y).

Find the equivalence class [1] = T_1 containing 1.

And this is how it has been solved:

[1]={ $x \in S : 6|x+5.1 = x+5$}={-5,1,7,13}

Why did they set y=0 here but set x=0 in the problem above?

4. Hello Roam

The first thing you need to verify is that these are equivalence relations. If they are, then since an equivalence relation is symmetric (i.e. $x \sim y \iff y \sim x$) it doesn't matter whether you give a particular value to $x$ or to $y$: the result will be the same, since they are interchangeable.

So, looking at the first relation: $x\sim y \iff 7|(6x+y)$ (for that is surely what the question means), ask three questions: is it reflexive? is it symmetric? is it transitive?

Do you understand modular arithmetic notation?

Well, if you do, $7|(6x+y)$ can be written $6x + y \equiv 0 \mod 7$

$\Rightarrow 7x+y \equiv x \mod 7$

$\Rightarrow y \equiv x \mod 7$

In other words, $x$ and $y$ (which represent any two elements of an equivalence class) leave the same remainder when divided by $7$.

So, yes, it is an equivalence relation. And all you need to do to find the equivalence classes is to look for elements of the original set that leave the same remainder when divided by $7$.

Here's a start: $[-8]=\{-8\}, [-4]=\{-4\}, [-2]=\{-2, 5\}, ...$

Could you PLEASE show me in more detail what's happening here because I'm still SO confused on how to find equivalence classes.

Hello Roam

The first thing you need to verify is that these are equivalence relations. If they are, then since an equivalence relation is symmetric (i.e. $x \sim y \iff y \sim x$) it doesn't matter whether you give a particular value to $x$ or to $y$: the result will be the same, since they are interchangeable.
This is the solution they gave us for this problem:

They've done it by setting x=0. Yes I checked and proved that it's an equivalence relation (reflexive, symmetric and transitive). But it's impossible to obtain the same results by setting y=0:

[0]={ $x \in S: 7| 6x+0 = 6x$}

Now the only time when 6x is divisible by 7 is when x=7

$\Rightarrow$ {7} $\neq$ {1,7}

Since 7 \notdivides 6.1

See, it does matters if I assign a particular value to x or to y!

Do you understand modular arithmetic notation?

Well, if you do, $7|(6x+y)$ can be written $6x + y \equiv 0 \mod 7$

$\Rightarrow 7x+y \equiv x \mod 7$

$\Rightarrow y \equiv x \mod 7$

Yes I had learned a little bit about the modular arithmetic notation. This relation is a congruence modulo 7, like you mentioned.

6. Hello Roam
Originally Posted by Roam

Could you PLEASE show me in more detail what's happening here because I'm still SO confused on how to find equivalence classes.

This is the solution they gave us for this problem:

This solution is not correct, in at least two different ways. First, does not make sense to write:

$[0]=\{x\in S:7|6\cdot0+y=y\}=\{0,7\}$

This is incorrect use of set notation. It should read:

$[0]=\{y\in S:7|6\cdot0+y=y\}=\{0,7\}$

In general, you can define a set A like this:

$A =\{x:x\text{ satisfies a certain condition}\}$

So it doesn't make sense to write $A =\{x:y\text{ satisfies a certain condition}\}$

Secondly, the solution $[1]=\{-8, 1\}$ simply isn't correct: $6\times (-8) + 1 = -47$ which is not divisible by $7$.

Now, as to your next point:
They've done it by setting x=0. Yes I checked and proved that it's an equivalence relation (reflexive, symmetric and transitive). But it's impossible to obtain the same results by setting y=0:

[0]={ $x \in S: 7| 6x+0 = 6x$}

Now the only time when 6x is divisible by 7 is when x=7
Not true, I'm afraid. $x=0$ also works, because $6\times0=0$, which is divisible by $7$. So $[7] = \{0, 7\}$ is correct.

$\Rightarrow$ {7} $\neq$ {1,7}
is true, but that's not the same thing.

As to your main problem: Do I give a particular value to $x$ or to $y$? I repeat my previous answer: because it's an equivalence relation it doesn't matter! For instance, if we want to find the equivalence class containing the element $5$, we can assign this value to $x$, and say:

$[5]=\{y\in S:7|30+y\}=\{-2,5\}$

or we can assign the value $5$ to $y$, and say:

$[5]=\{x\in S:7|6x+5\}=\{-2,5\}$

Do you see? The statements $7|30+y$ and $7|6x+5$ are equivalent, simply because they're both satisfied by the same set of values of $x$ and $y$: namely those values which leave a remainder $5$ when divided by $7$.

I hope that helps to clear things up.