Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof Involving Binary Operators

  1. Feb 3, 2004 #1
    I am trying to prove that A union (B intersection C) = (A union B) intersection (A union C). In other words, proving one of DeMorgan's Laws. I have gotten this far, and not sure if I'm right thus far:

    Let x belong to A union (B intersection C). Then x is in either A or in (B intersection C).

    Case 1: x belongs to A.
    In this case, x belongs to (A union B) and x belongs to (A union C).

    Case 2: x belongs to (B intersection C).
    In this case, x belongs to either (A union B) or (A union C).

    So x belongs to ((A union B) intersection (A union C)) union ((A union B) union (A union C)).

    ((A union B) union (A union C)) can be rewritten as (using associative property):

    (A union B union A union C), or simply (A union B union C).

    What do I do now? Thank you.
     
  2. jcsd
  3. Feb 3, 2004 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    No, if x belongs to (B intersection C),then x belongs to both (A union B) and (A union C).
    (since x belongs to (B intersection C) it is in both B and C and so in both (A union B) and (A union C) so it is in
    (A union B)intersection (A union C).)
     
  4. Feb 3, 2004 #3
    OK this is what I got now:

    First, we must prove that A union (B intersection C) is a subset of (A union B) intersection (A union C).

    So we let x belong to A union (B intersection C). Then x is in A or (B intersection C).

    Case 1: x belongs to A.
    In this case, x belongs to (A union B) and x belongs to (A union C).

    Case 2: x belongs to (B intersection C).
    In this case, x belongs to (A union B) and x belongs to (A union C).

    So x belongs to ((A union B) intersection (A union C)).

    Now we have to prove that (A union B) intersection (A union C) is a subset of A union (B intersection C).

    So now let x belong to (A union B) intersection (A union C). Then x is in A. x is in either B or C.

    Case 1: x is in B.
    In this case, x belongs to (A union B).

    Case 2: x is in C.
    In this case, x belongs to (A union C).

    Am I right so far? I don't know how to go any farther with this.

    Thanks for the help so far.
     
  5. Feb 3, 2004 #4

    Tom Mattson

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Why not do it with Venn diagrams?
     
  6. Feb 3, 2004 #5
    I have to solve it without using Venn Diagrams.
     
  7. Feb 4, 2004 #6
    How can I conclude that (A union B) intersection (A union C) is a subset of A union (B intersection C)?
     
  8. Feb 4, 2004 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    almost any question about the containment or equality of sets boils down to showing x in A implies x in D

    so take something in one and show it's in the other by considering all cases if necessary. here x is in AUB and AUC, if it is in A it is certainly in AU(B int C)

    if it is not in A then it must be in both B and C, ie it is in (B int C), and is then also clearly in AU(BintC)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proof Involving Binary Operators
  1. Binary Operations (Replies: 12)

Loading...