Math Is Fun Forum

nha

Member

Registered: 2010-09-05

Posts: 43

equivalence relation questions

Hi everyone again, I am doing alot of math questions today have keep running into some problems here and there.

It would be great if anyone could help me with a couple of questions relating to equivalence relations.

Q1) Write down the ordered pairs corresponding to the equivalence relation, which yields the partition:
{a,c,e,g,j},{f},{b,d,h},{i}

Q2) Let {S_i}_i be a partition of a set S, i.e.

with

if

. Prove that this partition {S_i}_i gives rise to an equivalence relation on S.

My textbook doesn't give me much help with these, any help would be nice. Thanks

Bob

Administrator

Registered: 2010-06-20

Posts: 10,621

Re: equivalence relation questions

hi nha,

Not my best subject but, as no one else is posting I'll throw in my ideas.

(ii) first.  I think you've got to show symmetric, reflexive and transitive. 

So, for example, define R so that a R b. when a and b are both in Si. 

As  a in Si and b in Si => b in Si and a in Si => b R a so it is reflexive.

(i)  ??? What ordered pairs is this question after?  I really cannot get this.  Sorry.  Do you have a given example already to show what this means?

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

nha

Member

Registered: 2010-09-05

Posts: 43

Re: equivalence relation questions

hi nha,

Not my best subject but, as no one else is posting I'll throw in my ideas.

(ii) first.  I think you've got to show symmetric, reflexive and transitive. 

So, for example, define R so that a R b. when a and b are both in Si. 

As  a in Si and b in Si => b in Si and a in Si => b R a so it is reflexive.

(i)  ??? What ordered pairs is this question after?  I really cannot get this.  Sorry.  Do you have a given example already to show what this means?

Bob

Hi Bob, for Q2 I still don't understand, could you explain it a bit more. For Q1, that is all the question gives, that is why I don't understand it either.

Avon

Member

Registered: 2007-06-28

Posts: 80

Re: equivalence relation questions

Hi nha,

A binary relation R on a set X is usually considered to be a set of ordered pairs of elements of X, so that the pair (x,y) is in the set if and only if xRy is true.
An equivalence relation on X is a binary relation on X so corresponds to a set of ordered pairs.

If E is a equivalence relation on X then the equivalence classes of E form a partition of X.
Conversely, if we have a partition of X then we can define a relation E on X by xEy if x and y belong to the same part of the partition. Then E is an equivalence relation on X.

In fact, there is a one-to-one correspondence between the equivalence relations on X and the partitions of X.

The ordered pairs corresponding to the partition {a,c,e,g,j},{f},{b,d,h},{i} are
(a,a), (a,c), (a,e), (a,g), (a,j),
(c,a), (c,c), (c,e), (c,g), (c,j),
(e,a), (e,c), (e,e), (e,g), (e,j),
(g,a), (g,c), (g,e), (g,g), (g,j),
(j,a), (j,c), (j,e), (j,g), (j,j),
(f,f),
(b,b), (b,d), (b,h),
(d,b), (d,d), (d,h),
(h,b), (h,d), (h,h),
(i,i).

Bob

Administrator

Registered: 2010-06-20

Posts: 10,621

Re: equivalence relation questions

Thanks Avon,

That helps me too.

Back to Question 2.

The sets denoted Si and Sj don't have anything in their intersection so this partition divides main set S into non overlapping subsets.

Construct a relationship, R,  between elements that basically says a and b are related ( a R b) if and only if a and b are both in the same Si.

It's reflexive because a R a (a and a are both in the same set).

It's symmetric because if a R b this means they're both in the same Si which means b R a.

It's transitive because if a R b, and b R c this means that a, b and c are all in the same Si so a R c.

That makes it an equivalence relationship.

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob