You are Here: Home >< Maths

# Sets Watch

1. Hi, I've been stuck on a question for a while so decided to come on here for some help. The question is:
How many equivalence relations on two equivalence classes are there on an n-set.
I'm not sure what to do or even how to start this question and would appreciate some help. Thanks.
2. Your best bet is to count the number of relations, and then cut that number down based on reflexivity, symmetry and transitivity.

How many relations are there? How many of those are reflexive? How many of those are symmetric? How many of those are transitive?
3. Just started revising this so can't help much lol....
4. (Original post by JBKProductions)
Hi, I've been stuck on a question for a while so decided to come on here for some help. The question is:
How many equivalence relations on two equivalence classes are there on an n-set.
I'm not sure what to do or even how to start this question and would appreciate some help. Thanks.
If the question means how many equivalence relations are there on an n-set that partition the set into 2 equivalence classes, just note that there is a bijection between partitions and equivalence classes.

EDIT: Just to make that a bit clearer, for each partition of the n-set, there is exactly one corresponding equivalence relation.
5. (Original post by nuodai)
Your best bet is to count the number of relations, and then cut that number down based on reflexivity, symmetry and transitivity.

How many relations are there? How many of those are reflexive? How many of those are symmetric? How many of those are transitive?
Sorry I'm not sure what you mean, we've just been told that we have a set X and that's it so not sure what you mean by counting the number of relations.
6. (Original post by Mark13)
If the question means how many equivalence relations are there on an n-set that partition the set into 2 equivalence classes, just note that there is a bijection between partitions and equivalence classes.
So is it the number of subsets in the partition?
7. (Original post by JBKProductions)
So is it the number of subsets in the partition?
I'm not quite sure what the question means. If it's saying "how many equivalence relations are there on a n-set that partition the set into 2 equivalence classes", then you can use the fact that the number of ways of partitioning the n-set into 2 subsets is equal to the number of equivalences relations that partition the n-set into 2 equivalence classes.
8. (Original post by Mark13)
I'm not quite sure what the question means. If it's saying "how many equivalence relations are there on a n-set that partition the set into 2 equivalence classes", then you can use the fact that the number of ways of partitioning the n-set into 2 subsets is equal to the number of equivalences relations that partition the n-set into 2 equivalence classes.
This is the answer to the question "An equivalence relation is determined by its equivalence classes. Therefore the number
in question is the number of partitions of an n-set X into two non-empty subsets which is the number of all subsets A of X with ; 0=/= A =/= X divided by two since A and A* lead to the same partition"
The answer is just so confusing, I don't understand it.
I hope this answer clears up what the question means.
9. (Original post by JBKProductions)
This is the answer to the question "An equivalence relation is determined by its equivalence classes. Therefore the number
in question is the number of partitions of an n-set X into two non-empty subsets which is the number of all subsets A of X with ; 0=/= A =/= X divided by two since A and A lead to the same partition"
The answer is just so confusing, I don't understand it.
I hope this answer clears up what the question means.
Ok, the question means what I thought it did - i.e. count the number of equivalence relations on the n-set that partition it into 2 (non-empty) equivalence classes

To understand what the answer means, note that if we've got a partition on the n-set which splits it into subsets A and B, this corresponds to a unique equivalence relation whose equivalence classes are A and B - namely aRa' iff a,a' both belong to A or both belong to B.

So, the number of equivalence relations we're looking for is equal to the number of ways of splitting the n-set into 2 non-empty subsets. Can you see how to find this number?
10. (Original post by Mark13)
Ok, the question means what I thought it did - i.e. count the number of equivalence relations on the n-set that partition it into 2 (non-empty) equivalence classes

To understand what the answer means, note that if we've got a partition on the n-set which splits it into subsets A and B, this corresponds to a unique equivalence relation whose equivalence classes are A and B - namely aRa' iff a,a' both belong to A or both belong to B.

So, the number of equivalence relations we're looking for is equal to the number of ways of splitting the n-set into 2 non-empty subsets. Can you see how to find this number?
Has it got something to do with the power set?
11. (Original post by JBKProductions)
Has it got something to do with the power set?
Yeh sort of. If, for each partition, we say the n-set is partitioned into a subset A and a subset B, what possible choices do we have for A? Every possible subset (with the exception of the empty set and the full set, since we are not allowed for A or B to be empty) i.e. the number of choices for A is equal to the size of the power set of the n-set take away two.

This isn't quite the final answer, since if we choose A={1}, then this implies that B={2,...,n}, but if we choose A={2,...,n}, this implies B={1}. So these two different choices of A have led to the same partition of the n-set. Can you see what needs to be done to the number obtained in the first paragraph to get to the final answer?
12. (Original post by Mark13)
Yeh sort of. If, for each partition, we say the n-set is partitioned into a subset A and a subset B, what possible choices do we have for A? Every possible subset (with the exception of the empty set and the full set, since we are not allowed for A or B to be empty) i.e. the number of choices for A is equal to the size of the power set of the n-set take away two.

This isn't quite the final answer, since if we choose A={1}, then this implies that B={2,...,n}, but if we choose A={2,...,n}, this implies B={1}. So these two different choices of A have led to the same partition of the n-set. Can you see what needs to be done to the number obtained in the first paragraph to get to the final answer?
Oh I see! so it's ((2^n)-2)/2?
13. (Original post by JBKProductions)
Oh I see! so it's ((2^n)-2)/2?
Yep.
14. (Original post by Mark13)
Yep.
Thank you!

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: December 24, 2010
Today on TSR

### Cambridge interview invitations

Has yours come through yet?

### Official Oxford interview invite list

Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams

## Groups associated with this forum:

View associated groups
Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.