1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Can the size of any E-class be either 9 or 99?

  1. Jan 13, 2013 #1
    1. The problem statement, all variables and given/known data

    Let A be the set of all subsets of {1,2,...,99} and E an equivalence
    relation on A. Can the size of any E-class be either 9 or 99?


    2. Relevant equations



    3. The attempt at a solution

    I think yes but can't see how...
     
  2. jcsd
  3. Jan 13, 2013 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    How many subsets of A are there?

    If you want to define an equivalence relation where each class has 9 members, how many equivalence classes do you get? Does that make sense?
     
  4. Jan 13, 2013 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Much depends on the meaning of "any" in the question "Can the size of any E-class be either 9 or 99?" You seem to be assuming that "any" = "every", but maybe the question wants to know if any one (but not all) of the equivalence classes can have size 9 (or 99).
     
  5. Jan 13, 2013 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I thought about that, but that would make the question weird and (imho) pointless.
     
  6. Jan 13, 2013 #5

    I like Serena

    User Avatar
    Homework Helper

    The only relevancy that I see, is as an exercise to understand the definitions of equivalence relations and of equivalence classes.

    bedi, can you give an example of an equivalence relation on A?
    And more to the point, can you give an example of an equivalence relation that has an equivalence class of size 9?
     
  7. Jan 13, 2013 #6
    As an example of an equivalence relation on A:
    Provided X,Y are elements of A, X≈Y iff either X is a subset of Y or Y is a subset of X. In view of this relation ≈ every element of A is related, right?
    But I cannot find an equivalence relation that has an equivalence class of size 9... And cannot see why it is impossible.
     
  8. Jan 13, 2013 #7

    I like Serena

    User Avatar
    Homework Helper

    Good. That is indeed an equivalence relation.
    One that has only 1 equivalence class, which is A.

    What about the relation given by the set of pairs:
    {(a,a) : a in A} + {({2},{2}), ({2},{3}), ({3},{2}), ({3},{3})}.

    Is it an equivalence relation on A?
    If so which equivalence classes does it contain?
     
    Last edited: Jan 13, 2013
  9. Jan 13, 2013 #8
    Yes I think this is an equivalence relation on A. And the equivalence classes are:
    [1]={{1}}, [2]={{2},{3}}, [3]={{3}}. Actually I'm not sure if an equivalence relation on any given set must say something about all the elements of the set. For instance in this eq. relation we do not have [4], is this a problem?
     
  10. Jan 13, 2013 #9

    I like Serena

    User Avatar
    Homework Helper

    Actually, you'd have [3]={{2},{3}}.
    And so {{2},{3}} is the corresponding equivalence class of size 2.

    From wiki:

    A given binary relation ~ on a set A is said to be an equivalence relation if and only if it is reflexive, symmetric and transitive.
    Equivalently, for all a, b and c in A:
    1. a ~ a. (Reflexivity)
    2. if a ~ b then b ~ a. (Symmetry)
    3. if a ~ b and b ~ c then a ~ c. (Transitivity)


    So yes, each element a in A must at least have an equivalence relation with itself.


    Now, can you think of an equivalence relation on A that contains an equivalence class of size 9?
     
    Last edited: Jan 13, 2013
  11. Jan 13, 2013 #10
    On the other hand, mfb asked that "if you want to define an equivalence relation where each class has 9 members, how many equivalence classes do you get?" and since equivalence classes are also a partition on A, we have to have 2^99/9 classes in this case, which is not possible. Correct?
     
  12. Jan 13, 2013 #11

    I like Serena

    User Avatar
    Homework Helper

    Correct. ;)
     
  13. Jan 13, 2013 #12
    Thank you, you are so helpful!
     
  14. Jan 13, 2013 #13

    I like Serena

    User Avatar
    Homework Helper

    Btw, I concur with Ray that this is not what the problem asks.

    The problem asks for "any", and not for "every" or "each".
    I interpret it that it suffices if there is just a single equivalence class of size 9.
     
  15. Jan 13, 2013 #14
    Alright, that can happen right? Why not?
     
  16. Jan 13, 2013 #15

    I like Serena

    User Avatar
    Homework Helper

    To properly answer the question, you have to give a specific example, and prove that it is indeed an equivalence relation.

    But yeah, it can happen. ;)
     
  17. Jan 13, 2013 #16

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Well, it is trivial.
    Take any 9 elements of A, let them be in the same equivalence class, ignore the other elements (apart from the required M~M for every element of A).
    It is not an interesting equivalence relation, but that was not requested.

    I don't see how this is an equivalence relation.

    {1,2}~{1}~{1,3}, but not {1,2}~{1,3}
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Can the size of any E-class be either 9 or 99?
  1. Can Any Genius Answer (Replies: 3)

Loading...