Math Is Fun Forum

ToneMU84

Member

Registered: 2009-05-02

Posts: 5

equivalence Relations-equivalence classes of related elements

I am currently in discrete structures and i understand transitive, reflexive and anti-symmetric propteries. I am currently stuck on a type problem that will be on my exam on Equivalence Relations
Here is the problem i am currently studying...

Suppsoe R is an equivalance relation {1,2,3,4,5}  What are the equivalence classes of each of the related elements.

1)1 is not related to 2
2)3R5
3)4R2
4)1 is not related to 3
5)3 is not related to 4

I know the answer b/c i have it in front of me, but dont understand y?!
Please if anyone could explain why the equivalence classes  are {1} {2,4}{3,5} which would project the data I provided above.

Knowing my properties, i think since!?!  1 is not related to 2, and 1 is not related to 3, 1 has to reflexive? related to itself?
Since nothing relates to 3 and 3 only relates to  5, our equivalence class has to be {3,5}?!?
{2,4} i wouldnt know where to being. 
I wish i could better visualize this as a digraph i think it would help me a lot more, but I cant plot this information correctly,

Thank You Sincerely,

Tony

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: equivalence Relations-equivalence classes of related elements

This way might be too informal, but here's how I see it:

First you have all the elements in their own equivalence classes: {1}; {2}; {3}; {4}; {5}.
Using the second and third facts, these can be joined together like so: {1}; {2,4}; {3,5}.
Now the remaining three facts show that no further joins are possible.
{1,2,4} is prevented since 1!R2, {1,3,5} is prevented since 1!R3 and {2,3,4,5} is prevented since 3!R4.

---

Why did the vector cross the road?
It wanted to be normal.

ToneMU84

Member

Registered: 2009-05-02

Posts: 5

Re: equivalence Relations-equivalence classes of related elements

Thank you... At first i didnt get it but it makes more sense now that i got a good nights rest and read what you posted.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: equivalence Relations-equivalence classes of related elements

This way might be too informal, but here's how I see it:

I couldn't imagine of a more clear or rigorous way to do it.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: equivalence Relations-equivalence classes of related elements

That's good to know!
I've never encountered that kind of question academically, so I just wanted to put a disclaimer in, in case there was some standard method that I wasn't following.

---

Why did the vector cross the road?
It wanted to be normal.

whatismath

Member

Registered: 2007-04-10

Posts: 19

Re: equivalence Relations-equivalence classes of related elements

I think Ricky and Mathsyperson basically explain the idea.
I would just like to point to an algorithmic perpective.
Equivalence classes are disjoint and elements
in an equivalence class are pair-wise related.
A list of relations (related pairs) and non-relations (unrelated
pairs) could be
1. consistent and uniquely determines all the equivalence classes, or
2. consistent but does not uniquely determine all the equivalence
    classes (it might determines some of them), or
3. inconsistent, which unfortunately might only be found out at
    a late stage.

For me, I might want to consider all the relations first and apply
transitivity to get a collection of largest possible subsets of pair-wise
related elements. Then I would apply the non-relations:
a. on each subset above to check for consistencies
b. on each pair of subsets above for possibility that they are
    part of the same equivalence class.

Sorry for making a simple exercise too complicated.
Thanks for reading.