Hey there! Sign in to join this conversationNew here? Join for free
    • Thread Starter
    Offline

    0
    ReputationRep:
    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.
    • PS Helper
    Offline

    14
    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?
    Offline

    3
    ReputationRep:
    Just started revising this so can't help much lol....
    Offline

    0
    ReputationRep:
    (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.
    • Thread Starter
    Offline

    0
    ReputationRep:
    (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.
    • Thread Starter
    Offline

    0
    ReputationRep:
    (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?
    Offline

    0
    ReputationRep:
    (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.
    • Thread Starter
    Offline

    0
    ReputationRep:
    (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.
    Offline

    0
    ReputationRep:
    (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?
    • Thread Starter
    Offline

    0
    ReputationRep:
    (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?
    Offline

    0
    ReputationRep:
    (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?
    • Thread Starter
    Offline

    0
    ReputationRep:
    (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?
    Offline

    0
    ReputationRep:
    (Original post by JBKProductions)
    Oh I see! so it's ((2^n)-2)/2?
    Yep.
    • Thread Starter
    Offline

    0
    ReputationRep:
    (Original post by Mark13)
    Yep.
    Thank you!
 
 
 
  • 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
    What newspaper do you read/prefer?
    Useful resources

    Make your revision easier

    Maths

    Maths Forum posting guidelines

    Not sure where to post? Read the updated guidelines here

    Equations

    How to use LaTex

    Writing equations the easy way

    Student revising

    Study habits of A* students

    Top tips from students who have already aced their exams

    Study Planner

    Create your own Study Planner

    Never miss a deadline again

    Polling station sign

    Thinking about a maths degree?

    Chat with other maths applicants

    Can you help? Study help unanswered threads

    Groups associated with this forum:

    View associated groups
  • 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

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