Results 1 to 6 of 6

Math Help - Outrageously hard equivalence relations

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    296

    Outrageously hard equivalence relations

    Verify it is equiv. rel.

    For the set X={m,n,p,q,r,s}, let R be the relation on P(X) (power set of X) given by A R B iff A and B have the same number of elements.
    Now, list all elements in {m}/R; in{m,n,p,q,r}/R. How many elements are in X/R? How many in P(X)/R?

    I know I need to show it is symmetric, transitive, and reflexive. I know how to this when we have like equations and things, but this one is confusing for me. Please help. Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Equivalence Classes and Quotient Sets

    Hello zhupolongjoe
    Quote Originally Posted by zhupolongjoe View Post
    Verify it is equiv. rel.

    For the set X={m,n,p,q,r,s}, let R be the relation on P(X) (power set of X) given by A R B iff A and B have the same number of elements.
    Now, list all elements in {m}/R; in{m,n,p,q,r}/R. How many elements are in X/R? How many in P(X)/R?

    I know I need to show it is symmetric, transitive, and reflexive. I know how to this when we have like equations and things, but this one is confusing for me. Please help. Thank you.
    As you have written the question, some of it doesn't make sense. I'll explain why, but it will take a little time, so stay with me.

    P(X), the power set of X, is the set of all the subsets of X. So:

    P(X) = \{\oslash, \{m\}, \{n\}, \dots, \{m,n\}, \{m, p\}, \dots, \{m,n,p,q,r,s\}\}

    Look carefully at the words above in italics: P(X) is a set of ... subsets ...; so the elements of P(X) are themselves sets - and I have listed a few of them above.

    Now R is a relation on P(X) (not a relation on X) - in other words R is a relation between two subsets of X, which is: subset A is related to subset B if and only if A and B have the same number of elements. So, for example:

    • \{m,n\}\,R\,\{n,p\} because they both have 2 elements
    • \{n,q,r\} \,R\, \{m,q,s\} because they both have 3 elements

    ... and so on.

    Next, you need to understand the / notation. If a relation R is defined on a set A, then A/R (called the quotient set of A by R) is the set of all the equivalence classes into which A is 'divided' (or partitioned) by R (hence the use of the word 'quotient').

    For example, if A = \mathbb{Z} and m\,R\,n \iff 2|(m - n) (in other words, (m - n) is divisible by 2), then R partitions \mathbb{Z} into two equivalence classes: {even integers} and {odd integers}, and these two sets are therefore the elements of A/R.

    So, in the question you're asking, whereas it makes sense to talk about P(X)/R, it makes no sense to talk about \{m\}/R or X/R, because R is not defined on individual elements like m, but on sets.

    OK. So let's look at the question that does make sense: How many elements are there in P(X)/R? This question means: when P(X) is partitioned into equivalence classes by R, how many of these equivalence classes are there? Well, for example, all the subsets of X that contain one element - that's \{m\}, \{n\}, \{p\}, \{q\}, \{r\}, \{s\} - are equivalent. So they form one equivalence class. (And that, I suspect, is what the question means when it says 'list all the elements in {m}/R', although that is incorrect use of the notation.)

    All the subsets of X containing 2 elements form another equivalence class; all the subsets containing 0 elements form another, and so on. Since you can form subsets containing 0, 1, 2, 3, 4, 5 or 6 elements, there are therefore 7 equivalence classes, and therefore 7 elements in P(X)/R.

    The proof that R is an equivalence relation is trivial. Any relation that contains the words ' A ... the same as B' usually is. If A has the same number of elements as B, then it's obvious that A\,R\,A (reflexive) and A\,R\,B \iff B\,R\,A (symmetric) and (A\,R\,B \wedge B\,R\,C) \Rightarrow A\,R\,C (transitive).

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    296
    Ok, thank you. I don't know why the book would ask a question that doesn't make sense...I just put the question just as it appeared in the text. Maybe they want you to realize that the question is nonsensical? But thank you the same!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jan 2009
    Posts
    296
    I just have on further question:

    "All the subsets of containing 2 elements form another equivalence class; all the subsets containing 0 elements form another, and so on. Since you can form subsets containing 0, 1, 2, 3, 4, 5 or 6 elements, there are therefore 7 equivalence classes, and therefore 7 elements in ."

    Why wouldn't it be the 1+6+.....+6+1..i.e. add all the elements..like there is one subset with 0 elements, 6 subsets with 1 element...6 subsets with 5 elements and so on...?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Equivalence Classes

    Hello zhupolongjoe[/quote]
    Quote Originally Posted by zhupolongjoe View Post
    "...there are therefore 7 equivalence classes, and therefore 7 elements in ."

    Why wouldn't it be the 1+6+.....+6+1..i.e. add all the elements..like there is one subset with 0 elements, 6 subsets with 1 element...6 subsets with 5 elements and so on...?
    Because this is the number of elements in P(X) - and in fact it's equal to 2^6 = 64. (Perhaps you can work out why?) On the other hand P(X)/R is the set of equivalence classes, and there are 7 of these, into which the 64 elements of P(X) are distributed by R.

    In the other illustration I gave you (the 2|(n-m) relation on \mathbb{Z}) there are just two equivalence classes: {odd integers} and {even integers}, whereas, of course, there are infinitely many integers in each one.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jan 2009
    Posts
    296
    Got it now, thanks so much!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 19th 2011, 02:09 PM
  2. Equivalence relations!
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: January 16th 2010, 04:22 PM
  3. Replies: 10
    Last Post: January 14th 2010, 01:28 PM
  4. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 14
    Last Post: October 1st 2009, 04:03 PM
  5. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 1st 2009, 12:14 PM

Search Tags


/mathhelpforum @mathhelpforum