Results 1 to 11 of 11

Math Help - Partition induced by a relation

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    11

    Partition induced by a relation

    Let A be a nonempty set and fix the set B where B is a subset of A. Define the relation R on the power set of A as follows: for all subsets X, Y of A, X R Y if and only if B intersect X = B intersect Y.

    Suppose we make some sets...

    A={1,2,3} and B={1,2}

    How do i find the partition of the power set of A? Do I need to know what X and Y are first?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by chubbs145 View Post
    Let A be a nonempty set and fix the set B where B is a subset of A. Define the relation R on the power set of A as follows: for all subsets X, Y of A, X R Y if and only if B intersect X = B intersect Y.

    Suppose we make some sets...

    A={1,2,3} and B={1,2}

    How do i find the partition of the power set of A? Do I need to know what X and Y are first?
    X and Y are just elements of the powerset of A. You need to find which elements of the powerset are "equal" using this relation.

    So, for example, {1}R{1, 3}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by chubbs145 View Post
    Let A be a nonempty set and fix the set B where B is a subset of A. Define the relation R on the power set of A as follows: for all subsets X, Y of A, X R Y if and only if B intersect X = B intersect Y.

    Suppose we make some sets...

    A={1,2,3} and B={1,2}

    How do i find the partition of the power set of A? Do I need to know what X and Y are first?
    A relation partitions a set if and only if it is an equivalence relation. The partitions are known as equivalence classes. If you've worked with congruence classes (mod n), then you will have a good idea of this concept from experience.

    Wikipedia states it thus: "For any equivalence relation on a set X, the set of its equivalence classes is a partition of X. Conversely, from any partition P of X, we can define an equivalence relation on X by setting x ~ y precisely when x and y are in the same part in P. Thus the notions of equivalence relation and partition are essentially equivalent." (source)

    So we know beforehand from the problem statement that we are dealing with an equivalence relation, but we could verify it if we wanted.

    But anyway, I'd like to consider a larger example to better illustrate how this applies.

    A = {1,2,3,4,5,6}
    B = {1,2,3}

    Now notice the powerset of B has 2^3 elements, and each of these sets defines an equivalence class. So for example, {1,2} is in the powerset of B. Consider

    C = {1,2,5}
    D = {1,2,5,6}
    E = {1,2,4}
    F = {1,2}

    These are all equivalent under the relation R.

    Does that make sense?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by chubbs145 View Post
    Let A be a nonempty set and fix the set B where B is a subset of A. Define the relation R on the power set of A as follows: for all subsets X, Y of A, X R Y if and only if B intersect X = B intersect Y.

    Suppose we make some sets...

    A={1,2,3} and B={1,2}

    How do i find the partition of the power set of A? Do I need to know what X and Y are first?
    "To know X,Y first"? you need to check which subsets of A are related according to the given relation...for example, \{2\}R\{2,3\} , since

    \{2\}\cap \{1,2\}=\{2,3\}\cap\{1,2\}=\{2\} . From here, both \{2\}\,,\,\{2,3\} will be in the same partition set (i.e., equivalence class) of the power set of A, since they're r-related.

    Well, now you find all the partitions sets (=equiv. classes) one by one. After all, there're only 8 subsets here...

    Tonio
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2010
    Posts
    11
    Yeah a little, I guess im not really seeing the difference between equivalence class and partition. Are you able to have equivalence classes in a partition of something like the powerset of A by the definition of R?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by undefined View Post
    A relation partitions a set if and only if it is an equivalence relation. The partitions are known as equivalence classes. If you've worked with congruence classes (mod n), then you will have a good idea of this concept from experience.

    Wikipedia states it thus: "For any equivalence relation on a set X, the set of its equivalence classes is a partition of X. Conversely, from any partition P of X, we can define an equivalence relation on X by setting x ~ y precisely when x and y are in the same part in P. Thus the notions of equivalence relation and partition are essentially equivalent." (source)

    So we know beforehand from the problem statement that we are dealing with an equivalence relation, but we could verify it if we wanted.

    But anyway, I'd like to consider a larger example to better illustrate how this applies.

    A = {1,2,3,4,5,6}
    B = {1,2,3}

    Now notice the powerset of B has 2^3 elements, and each of these sets defines an equivalence class. So for example, {1,2} is in the powerset of B. Consider

    C = {1,2,5}
    D = {1,2,5,6}
    E = {1,2,4}
    F = {1,2}

    These are all equivalent under the relation R.

    Does that make sense?

    Perhaps it makes sense but it is, I'm afraid, wrong (or I am: not that many choices here ): for example, where does the set \{3\} belong to? Nowhere, according to you!

    We have \{3\}\cap B=\{3\} , whereas none of the sets C,D,E,F intersects B in 3 only...

    Tonio
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by tonio View Post
    Perhaps it makes sense but it is, I'm afraid, wrong (or I am: not that many choices here ): for example, where does the set \{3\} belong to? Nowhere, according to you!

    We have \{3\}\cap B=\{3\} , whereas none of the sets C,D,E,F intersects B in 3 only...

    Tonio
    I'm not sure what you mean

    {3} is in the powerset of B.

    So it is in the partition described completely by

    {3} 000
    {3,6} 001
    {3,5} 010
    {3,5,6} 011
    {3,4} 100
    {3,4,6} 101
    {3,4,5} 110
    {3,4,5,6} 111

    where I wrote binary numbers alongside to show how I was choosing elements from A that are not in B. So the above 8 sets all have the same intersection with B, so are equivalent under R, and there are no other sets in this partition.

    Am I wrong?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Apr 2010
    Posts
    15
    see below
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Apr 2010
    Posts
    15
    Let A be a nonempty set and fix the set B where B⊆A. Define the relation R on ℘(A), the power set of A, as follows: for all subsets X,Y of A, X R Y iff B∩X = B∩Y.

    Suppose we make some sets...

    A={1,2,3}
    B={1,2}

    How do i find the partition of the power set of A? Do I need to know what X and Y are first?

    well we can find that:

    ℘(A) = {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

    therefore the partition of the power set of A would be:

    [{},{3}],
    [{1},{1,3}],
    [{2},{2,3}],
    [{1,2},{1,2,3}]

    reasoning:
    [{},{3}]

    if X={}, Y={} and B={1,2}
    B∩X = B∩Y = {} = {} which is true

    if X={}, Y={3} and B={1,2}
    B∩X = B∩Y = {} = {} which is true

    if X={3}, Y={3} and B={1,2}
    B∩X = B∩Y = {} = {} which is true

    if X={3}, Y={} and B={1,2}
    B∩X = B∩Y = {} = {} which is true

    ~~~~~~~~~~~~~~~~~~~~~~~~~~
    [{1},{1,3}]

    if X={1}, Y={1} and B={1,2}
    B∩X = B∩Y = {1} = {1} which is true

    if X={1}, Y={1,3} and B={1,2}
    B∩X = B∩Y = {1} = {1} which is true

    if X={1,3}, Y={1} and B={1,2}
    B∩X = B∩Y = {1} = {1} which is true

    if X={1,3}, Y={1,3} and B={1,2}
    B∩X = B∩Y = {1} = {1} which is true

    ~~~~~~~~~~~~~~~~~~~~~~~~~~

    similarly for [{2},{2,3}] and [{1,2},{1,2,3}]
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,916
    Thanks
    1762
    Awards
    1
    Quote Originally Posted by chubbs145 View Post
    Let A be a nonempty set and fix the set B where B is a subset of A. Define the relation R on the power set of A as follows: for all subsets X, Y of A, X R Y if and only if B intersect X = B intersect Y.
    This is a well-known problem. Letís say that B\not= \emptyset
    Then as was pointed out the equivalence classes are determined by the elements in the power set \mathcal{P}(B).
     \forall X \in\mathcal{P}(B) however one denotes the equivalence class [X]= \left\{ {X \cup Y:Y \in \mathcal{P}(A\backslash B)} \right\}
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by undefined View Post
    I'm not sure what you mean

    {3} is in the powerset of B.

    So it is in the partition described completely by

    {3} 000
    {3,6} 001
    {3,5} 010
    {3,5,6} 011
    {3,4} 100
    {3,4,6} 101
    {3,4,5} 110
    {3,4,5,6} 111

    where I wrote binary numbers alongside to show how I was choosing elements from A that are not in B. So the above 8 sets all have the same intersection with B, so are equivalent under R, and there are no other sets in this partition.

    Am I wrong?

    No, re-reading your post you only gave 4 sets which are within one single equivalence class in P(A) , whereas I misunderstood and thought those were the eq. clases . As I warned, it was either you or me were wrong...and it was me.
    Thanx for the explanation.

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. induced partition?
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: September 22nd 2010, 05:55 PM
  2. induced subgraphs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 3rd 2009, 02:58 AM
  3. induced norm
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: November 23rd 2009, 06:58 PM
  4. equivalence relation on a partition..help.
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: July 29th 2009, 10:12 PM
  5. partition for each equivalence relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 23rd 2009, 08:18 PM

Search Tags


/mathhelpforum @mathhelpforum