Results 1 to 3 of 3

Math Help - Proof about Partitions of a set

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    42

    Proof about Partitions of a set

    Suppose that R1 and R2 are equivalence relations on a set A. Let P1 and P2 be the partitions that correspond to R1 and R2, respectively. Show that R1 is a subset of R2 if and only if P1 is a refinement of P2.

    ATTEMPT:

    We must show these two implications:

    If R1 is a subset of R2 then P1 is a refinement of P2 AND
    If P1 is a refinement of P2 then R1 is a subset of R2.

    1)I am not sure how to do this one...


    2) Assume P1 is a refinement of P2. Then every set in P1 is a subset of one of the sets in P2 (lets call it p). since P1 is a partition of R1 then the union of all sets in P1 = R1 and because all sets in P1 are in p then all elements of R1 are in P2 and since P2 is a subset of R2, R1 is a subset of R2.


    The second one sounds too informal, I would really appreciate some help (especially with the first implication) THANKS!!!!!!!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    First, I recommend keeping an example in mind. For instance, let C be a set of cars, R1 = {(c1, c2) | c1 and c2 have the same model (e.g., Accord)} and R2 = {(c1, c2) | c1 and c2 have the same make (e.g., Honda)}. It is assumed that different manufacturers produced different models, so if c1 and c2 have the same model ((c1, c2) in R1), they also have the same manufacturer ((c1, c2) in R2), i.e., R1 is a subset of R2.

    As you write, the fact that P_1 is a refinement of P_2 means that every set in P_1 is a subset of one of the sets in P_2 -- this is what we need to prove. Fix a set p_1\in P_1. This set is an equivalence class consisting, for example, of all Accords. Take some c\in p_1. Then c has an equivalence class p_2 with respect to R_2, consisting of all cars with the same make as c. We'd like to show that p_1\subseteq p_2. Well, take any c'\in p_1, i.e., (c, c')\in R_1, i.e., c' is another Accord. Since all Accords have the same manufacturer ( R_1\subseteq R_2), (c, c')\in R_2, i.e., c'\in p_2.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    I'll point out some formal errors in your proof of 2), even if there may be the right idea behind them.
    2) Assume P1 is a refinement of P2. Then every set in P1 is a subset of one of the sets in P2 (lets call it p).
    You can't name a set in P2 without also naming the set in P1 on which it depends. Right now it may seem that there is a single set p in P2 such that every set in P1 is a subset of p. The right way to say is: "Every set p1 in P1 is a subset of some set p2 in P2". This means: Let's fix any set p1 in P1. Then there exists a set p2 in P2 such that p1 is a subset of p2. I.e., we have two objects p1 and p2, and we described how we chose them. If you just name p in P2 and you want to use it later, it is not clear how you chose it in the first place.
    since P1 is a partition of R1 then the union of all sets in P1 = R1
    In our example, the union of all sets in P1 is the whole set of cars, while R1 is the set of pairs of cars.
    and because all sets in P1 are in p
    This is just plain wrong because for every set p1 in P1 there exists its own superset p2 in P2.
    then all elements of R1 are in P2
    Type error again: R1 consists of pairs of cars, P2 consists of cars.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Partitions
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: October 4th 2010, 02:40 AM
  2. more partitions
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: March 15th 2010, 04:28 PM
  3. partitions
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: March 15th 2010, 04:22 PM
  4. Combinatorics & Partitions proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 22nd 2009, 06:04 AM
  5. Replies: 0
    Last Post: December 7th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum