Results 1 to 14 of 14

Math Help - set union/intersections/compliments

  1. #1
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1

    set union/intersections/compliments

    I have been thinking about this - do not know if there is any formal way to approcah this problem

    Few definitions

    S = Universal set
    A,B,C,D,.... = Subsets of S
    A' = compliment of A
    + = union on sets
    . = intersection of sets

    Let me take a case when there are just two subsets A and B

    Now, A.B, A'.B, A.B', A'.B' - partition S into mutually exclusive and exhaustive sets.

    Now any 'valid' operation on A and B (using +,.,') will represent a set in S, say X
    Then this X can be representes a union of some/all of A.B, A'.B, A.B', A'.B'

    For e.g A+B = A.B + A'.B + A.B'

    X can be as complicated as you want. (by repeatedly applying these operators in a consistent way)

    Now I have two questions
    1. How do you prove the above result - in a most generalized form?
    2. Will the proof / result change if
    a> S has infinite elements
    b> S has infinite subsets

    I do have an idea but am getting mixed up. Any help/pointers plz?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    I am not entirely sure what the question is here...are you basically asking, Let S=\bigcup_{\lambda \in \Lambda}A_{\lambda} where \Lambda is some indexing set. Then every subset of S can be thought of as a product consisting only of the operations A_i \cap A_j, A_i^{\prime}\cap A_j, A_i \cap A_j^{\prime} and A_{i}^{\prime}\cap A_j^{\prime}? I do not think this is true. Let \Lambda = \{a, b\} (basically |\Lambda| = 2) and let A_a = \{1, 2, 3\} and A_b = \{3\}. Thus S=A_a. Then, A_a^{\prime} = \emptyset, A_b^{\prime} = \{1, 2\} and your products will be, A_a \cap A_b = \{3\} A_a^{\prime} \cap A_b = \emptyset A_a \cap A_b^{\prime} = \{1, 2\} A_a^{\prime} \cap A_b^{\prime} = \emptyset. Thus there is no way of getting the elements 1 or 2 to be in a singleton set, which is a contradiction. However, I am unsure if this was actually your question... Also - use LaTeX! \cap is intersection, \cup is union, \{ is left curly bracket while \} is the right. See here. (Also, I believe that -A and \overline{A} are often used for S \setminus A = A \text{ complement} .)
    Last edited by Swlabr; July 16th 2010 at 02:11 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Sorry if my question was not clear. I'm not asking what you have understood.

    Let me repeat it

    Definitions -
    S = Universal set
    A,B,C,D,.... = Subsets of S
    A' = compliment of A
    + = union on sets
    . = intersection of sets
    (this notation makes it easier to write the problem below)

    Let there be 'n' subsets of S - A1, A2, A3, ...., An (any 'n' subsets will do)

    Consider 2^n subsets -
    A1.A2.A3...An-1.An
    A1.A2.A3....An-1.An'
    ....
    ..
    These 2^n subsets partition S into mutually exclusive and exhaustive sets. (This is easy to prove)

    Now consider operations -
    1. Union, +
    2. Intersection, .
    3. Compliment, '

    Using the above operations and {A1,A2,A3,....,An} sets we can construct a new set, for e.g.
    X = ((A1+A2)'.A3)+A7

    Prove that any such, X, can be represented as union of (some or all of the 2^n) partitions we constructed above.

    Will this proof change if
    a> S has infinite elements
    b> S has infinite subsets
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by aman_cc View Post
    Sorry if my question was not clear. I'm not asking what you have understood.

    Let me repeat it

    Definitions -
    S = Universal set
    A,B,C,D,.... = Subsets of S
    A' = compliment of A
    + = union on sets
    . = intersection of sets
    (this notation makes it easier to write the problem below)

    Let there be 'n' subsets of S - A1, A2, A3, ...., An (any 'n' subsets will do)

    Consider 2^n subsets -
    A1.A2.A3...An-1.An
    A1.A2.A3....An-1.An'
    ....
    ..
    These 2^n subsets partition S into mutually exclusive and exhaustive sets. (This is easy to prove)

    Now consider operations -
    1. Union, +
    2. Intersection, .
    3. Compliment, '

    Using the above operations and {A1,A2,A3,....,An} sets we can construct a new set, for e.g.
    X = ((A1+A2)'.A3)+A7

    Prove that any such, X, can be represented as union of (some or all of the 2^n) partitions we constructed above.

    Will this proof change if
    a> S has infinite elements
    b> S has infinite subsets
    It may be easier to write, but it certainly isn't easier to read!

    I'm still not really understanding you though. Are you saying that these n subsets are all the subsets of S? I mean, What if S=\{1, 2, \ldots, n\} and A_i:=\{i\}. Then the subsets which you construct are all empty...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    No they are not.

    In your example

     S=\{1, 2, \ldots, n\} and  A_i=\{i\}

    Consider
     S_1 = A_1'.A_2'.A_3'...A_{i-1}'.A_{i}.A_{i-1}'.....A_n' = \{i\} (Please note - Here a . represent intersection)

    So out of 2^n such subsets only 'n' are non-empty, rest all are empty. Nevertheless we have partionioned the universal set S into mutually exclusive and exhaustive susets, namely,
    <br />
\{1\}, \{2\}, ... , \{i\}, ..., \{n\}

    Is my question making sense now?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    So in general is,

    S_i:=A_1^{\prime} \cap A_2^{\prime} \cap \ldots \cap A_{i-1}^{\prime} \cap A_i \cap A_{i+1}^{\prime} \cap \ldots \cap A_n^{\prime}?

    Also, what do you mean by exhaustive?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Not really

    The partitions which are created by 'n' subsets of S, can be represented as an 'n' digit binary number
    say 0100....001
    Where ever you have 1 - Take A_i as such, else complement it before taking the intersection.

    For the above binary it would be
    S_i =A_1^{\prime} \cap A_2 \cap \ldots \cap A_i^{\prime} \ldots \cap A_n^

    What you wrote works only in the specific example you gave. (A better way to visualize these partitios is to consider any two subsets of S and see what each of the partition as I define them is in the Venn Diagram)

    By exhaustive, I mean, \forall x \in S there exits a partition, S_i, (infact a unqiue parition as all the partition are mutually exclusive) such that x \in S_i
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by aman_cc View Post
    Not really

    The partitions which are created by 'n' subsets of S, can be represented as an 'n' digit binary number
    say 0100....001
    Where ever you have 1 - Take A_i as such, else complement it before taking the intersection.

    For the above binary it would be
    S_i =A_1^{\prime} \cap A_2 \cap \ldots \cap A_i^{\prime} \ldots \cap A_n^

    What you wrote works only in the specific example you gave. (A better way to visualize these partitios is to consider any two subsets of S and see what each of the partition as I define them is in the Venn Diagram)
    Isn't that what I wrote?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Well I would say no becuase in the way you enumerated

    S_i:=A_1^{\prime} \cap A_2^{\prime} \cap \ldots \cap A_{i-1}^{\prime} \cap A_i \cap A_{i+1}^{\prime} \cap \ldots \cap A_n^{\prime}

    How would you define S_i for i \notin \{1,2,..,n\}

    Sorry if this is getting more and more confusing - seems I am not able to convey the crux of the problem.

    This is what it is
    1. Let there be any universal set S
    2. Let there be any subsets of this universal set, we call them A_1, A_2, .... A_n
    3. Based on A_1, A_2, .... A_n we define partitions (as in my post above). In general there will be 2^n such partitions, some of which may be \phi (null set)
    4. Now let X be any set whcih can be constructed from A_1, A_2, .... A_n using the operators below
    a> Intersection
    b> Union
    c> Complement
    5. Prove that X can be represented as union of partitions (as we defined them in step 3 above)

    Also I would write down how I think we can proceed with the proof.
    Show that if there are any two subsets of S, A and B where A,B can be expressed as union of the partitions then each of the following can also be expressed as union of paritions
    1. A' (or B')
    2. A \cup B
    3. A \cup B

    Now to start with each of the subsets A_i can be expressed as sum of partitions hence any X can also be.

    What I am struggling with is the case when we make 'n' infinite. Not sure if my logic breaks down somewhere?
    Last edited by aman_cc; July 19th 2010 at 05:17 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by aman_cc View Post
    Well I would say no becuase in the way you enumerated

    S_i:=A_1^{\prime} \cap A_2^{\prime} \cap \ldots \cap A_{i-1}^{\prime} \cap A_i \cap A_{i+1}^{\prime} \cap \ldots \cap A_n^{\prime}

    How would you define S_i for i \notin \{1,2,..,n\}

    Sorry if this is getting more and more confusing - seems I am not able to convey the crux of the problem.

    This is what it is
    1. Let there be any universal set S
    2. Let there be any subsets of this universal set, we call them A_1, A_2, .... A_n
    3. Based on A_1, A_2, .... A_n we define partitions (as in my post above). In general there will be 2^n such partitions, some of which may be \phi (null set)
    4. Now let X be any set whcih can be constructed from A_1, A_2, .... A_n using the operators below
    a> Intersection
    b> Union
    c> Complement
    5. Prove that X can be represented as union of partitions (as we defined them in step 3 above)

    Also I would write down how I think we can proceed with the proof.
    Show that if there are any two subsets of S, A and B where A,B can be expressed as union of the partitions then each of the following can also be expressed as union of paritions
    1. A' (or B')
    2. A \cup B
    3. A \cup B

    Now to start with each of the subsets A_i can be expressed as sum of partitions hence any X can also be.

    What I am struggling with is the case when we make 'n' infinite. Not sure if my logic breaks down somewhere?
    Induct on the number of operations you have. That is, you want to show that if you take a union of partitions, A, and union or intersect it with one of your sets, or take its complement, and see if you get a union of partitions. The complement and union are obvious, so concentrate on intersection.

    This method clearly does not depend on the number of partitions, but does depend on the number of operations you are performing (so you can't take an infinite intersection or something). If you are going to take an infinite intersection then I'm not actually sure if your result holds (think of open sets in a topological space...).
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Yes - it is the infinite case that is troubling me. Anyways thanks for your patience
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by aman_cc View Post
    Yes - it is the infinite case that is troubling me. Anyways thanks for your patience
    Which infinite case - the case of infinite products (e.g. taking an infinite intersection) or the case of an infinite number of partitions (which is what your fist post seems to imply). The two cases are different.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Infact both. But as of now I was thinking more on infinite number of partitions - I don't seem to able to think or even appreciate what challenges does this offer
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    My method, above, covers this (I mention that it covers it in the bottom paragraph, first line).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. conclude that the closure of a union is the union of the closures.
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: February 13th 2011, 07:50 PM
  2. Intersections Q
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 24th 2009, 07:12 AM
  3. Proofs involving sets and their compliments
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 15th 2009, 12:06 AM
  4. stats probability/compliments
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: June 3rd 2008, 06:52 PM
  5. intersections
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: January 8th 2008, 07:50 PM

Search Tags


/mathhelpforum @mathhelpforum