Question

Can anyone explain number of equivalence relations in the set {a,b,c}?

Answer 1

So, that's the number of possible ordered pairs, but not the number of possible equivalence relations

Answer 2

Since it is such a small set, I would go about it by brute force by going through every single pair and finding out which equivalence relation it generates (although this does not necessarily mean it'll find all equivalence relations!)

Answer 3

For example. If I pick (b,b), then it satisfies transitivity, reflexitivity and symmetry so that is an equivalence relation

Answer 4

Another example: I pick (c,a). Then by symmetry, (a,c) must be in the equivalence relation. Then by transitivity, (c,c) and (a,a) must be in the equivalence relation. Now, symmetry is also fulfilled, since (c,c) and (a,a). So now we have another equivalence relation. Then i would do it for the rest of them. But this does not give you all the equivalence relations! But the remaining equivalence relations should be quite trivial to think of...

Answer 5

I actually didn't feel that you r right..@pawanyadav
U just took into account that equivalence sets those can be {a,a} ,{b,b},{c,c} and likewise the symmetric n transitive relation...
What about the relations??
N big thing is that i m confused in this one particular aspect only is relation on set A {(b,c),a}.

Answer 6

@bobo-i-bo ur method wud lead to a lot much consumption of time ..
We don't have to wait for so long..
Do u know a bttr way out??

Answer 7

Let A := the set of all possible ordered pairs. Then an equivalence relation is any subset of A which satisfies transitivity, symmetry and reflexivity.

Answer 8

My method is quite quick actually if you consider the symmetries. So basically my method is the idea of generating the minimal equivalence relation which contains a particular element. So from the examples I showed, since (a,a) is a equivalence relation, it is quite obvious that (b,b) and (c,c) is a equivalence relation

Answer 9

And then from my example, it is obvious that (c,a) would generate the same generating set as (a,c). So we can ignore that one. Then by symmetry, we know that (a,b) and (b,a) would generate the same equivalence relation, and (b,c) and (c,b) would generate the same equivalence relation. So that adds three more unique equivalence relations

Answer 10

Then there is only one more equivalence relation which we haven't mentioned yet...

Answer 11

Does that make sense or is that going over your head? '~'

Answer 12

I m analysing them..pls wait

Answer 13

Do u mean to say that (a,b),(b,a) is an equivalence set..??
Well..if i m not wrong then it is just a symmetric relation and there is no reflexivity in it..

Answer 14

No, I'm saying they generate the same equivalence relation

Answer 15

They both generate the equivalence relation: {(a, a),(b, b), (a,b),(b, a) }

Answer 16

If any equivalence was to contain (a, b) then it must contain the set above as well. Any equivalence relation which contains (b, a) must contain the set above too

Answer 17

Ok..this is one equivalence relation similarly we can say the same for {(a,a),(c,c),(a,c),(c,a)}

Answer 18

Three relations we will get like the above case u explained similar to this:
{(a,a),(a,b),(b,a),(b,b)}

Answer 19

Yes.

Answer 20

This is for pair of two ..
What about all the three??

Answer 21

And this too {(a),(b),(c)} ..
This is also an equivalence relation isn't it??

Answer 22

No. I defined what an rwuivalence relationship is above

Answer 23

It is a subset of all possible ordered pairs. Triples and singlescetc are not allowed

Answer 24

The idea is that a relation is a relationship between any two objects (kinda inherent in the name :p)

Answer 25

So if there IS a relation between two objects, then you put it in the set. An equivalence relation is just a special kind of relation. Makes sense?

Answer 26

Ok ..
So like we have a set A containing three elements a, b,c then
Subsets (possible) are (a*a),(a*b),(a*c),(b*b),(b*c),(b*a),(c*c),(c*a),(c*b)
And there is no triplet in it or even singlet so relation can never be that..

Answer 27

Yes an equivalence relationship is any subset of the set of ordered pairs you have just listed above which satisfies transivity, symmetry and reflexitivity.

Answer 28

So we got only three relations till now.
(Equivalence one)

Answer 29

Yes, now try and find out what all the other ordered pairs generate. And then see if there are any more equivalence relationships which you haven't yet mentioned

Answer 30

I just got these
(a,a),(b,b),(b,a),(a,b)
(a,a),(a,c),(c,a),(c,c)
(b,b),(c,c),(b,c),(c,b)
That is 3..

Answer 31

So what equivalence relation does (a, a) generate?

Answer 32

Sorry ! I didn't get what u want to say by this?

Answer 33

I have enlisted all the relations i got ..

Answer 34

I'll start from the beginning to be clear ^_^

Answer 35

So let A:={(a,a),(b,b) (c,c) (a,b) (b,a) (a,c) (c,a) (b,c) (c,b)}

Answer 36

Then an equivalence relation is any subset satisfying the three things

Answer 37

So let us consider the pair (a,b). Any equivalence relation containing this pair must contain the set {(a,a),(b,b),(b,a),(a,b)}. This set itself is an equivalence relation

Answer 38

Any set containing (b,a) must contain that set too

Answer 39

Then we can apply the same argument with (b,c) and (c,b), and (a,c) and (c,a)

Answer 40

Which gives us three equivalence relations

Answer 41

So each of those equivalence relations are generated by (b,c) or (a,c) etc. But we haven't considered what (a,a) or (b,b) or (c,c) could generate... so what equivalence relation do they generate?

Answer 42

Sorry if i'm not explaining very well, maybe someone else should take over >_<

Answer 43

@bobo-i-bo i got total four equivalence relations till now..

Answer 44

Bcoz the complete set is also equivalence relation ..

Answer 45

Okay! So the fifth relation is {(a,a),(b,b),(c,c)}

Answer 46

Ohh am sorry ,, I have its solution even after that I don't have a look on it ...damn it

Answer 47

{(a,a),(b,b),(c,c)} is not an equivalence relation since it does not satisfy transitivity (although it does satisfy reflextivity and symmetry!)

Answer 48

So, there are 7 equivalence relations:
{(a,a)}
{(b,b)}
{(c,c)}
{(a,a),(b,b),(b,a),(a,b)}
{(a,a),(a,c),(c,a),(c,c)}
{(b,b),(c,c),(b,c),(c,b)}
{(a,a),(b,b) (c,c) (a,b) (b,a) (a,c) (c,a) (b,c) (c,b)}

Answer 49

Wait a sec..
U r wrong bcoz that's an equivalence relation bcoz it satisfy all the requirements of an equivalence relation
If u closely analyse it then u wud find that it doesn't have an element like (a,b),(b,c) types so we won't have a,c type in it..
And further i think that u were right in calling them as equivalence relations
{(a,a)}
{(b,b)}
{(c,c)}

Answer 50

Hmmm, what are you referring to when you say "it"?

Answer 51

Lmao

Answer 52

It is the whole relation (the complete one which u rejected to be the equivalence relation)

Answer 53

Oh yes, my mistake, it is a equivalence relation :p

Answer 54

Ok so we got 8 relations..

Answer 55

@bobo-i-bo

Answer 56

Hm, does the empty set count as as a equivalent relation?

Answer 57

Yes it does :p

Answer 58

9 then

Answer 59

is it?

Answer 60

Oh sorry, apparently empty set us not usually an equivalence relation: http://math.stackexchange.com/questions/690482/is-the-relation-r-emptyset-is-it-reflexive-symmetric-and-transitive-why

Answer 61

{(a, a), (b, b) } is an ewuivalence relation. And then u can extrapolate 2 more. Apart from that, I'm pretty sure we've exhausted the list

Answer 62

how many euivalence relations do u aim to get for this question?

Answer 63

Well it seems we've listed them all, so 11 :p