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 .
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 do I need to set or ???
I checked the solution and the correct answer for this particular problem is setting x to zero:
[0]={ }
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...
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]={ }={-5,1,7,13}
Why did they set y=0 here but set x=0 in the problem above?
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. ) it doesn't matter whether you give a particular value to or to : the result will be the same, since they are interchangeable.
So, looking at the first relation: (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, can be written
In other words, and (which represent any two elements of an equivalence class) leave the same remainder when divided by .
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 .
Here's a start:
Grandad
Hi Grandad
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:
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]={ }
Now the only time when 6x is divisible by 7 is when x=7
{7} {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, can be written
Yes I had learned a little bit about the modular arithmetic notation. This relation is a congruence modulo 7, like you mentioned.
Hello RoamThis solution is not correct, in at least two different ways. First, does not make sense to write:
This is incorrect use of set notation. It should read:
In general, you can define a set A like this:
So it doesn't make sense to write
Secondly, the solution simply isn't correct: which is not divisible by .
Now, as to your next point:Not true, I'm afraid. also works, because , which is divisible by . So is correct.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]={ }
Now the only time when 6x is divisible by 7 is when x=7
Your statementis true, but that's not the same thing.{7} {1,7}
As to your main problem: Do I give a particular value to or to ? 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 , we can assign this value to , and say:
or we can assign the value to , and say:
Do you see? The statements and are equivalent, simply because they're both satisfied by the same set of values of and : namely those values which leave a remainder when divided by .
I hope that helps to clear things up.
Grandad