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

Homework Help: Proving a set theory equality

  1. May 16, 2010 #1
    Hi Everyone!

    I would really appreciate some help with this set proof.

    1. The problem statement, all variables and given/known data

    Show that, for any sets A, B, ((A ∪ B) ∩ A) = (A ∩ A') ∪ (A ∩ B).
    (Hint: Remember that a complement of a complement is just the original set.)

    2. Relevant equations

    I can use any sentential calculus rules to prove this equality.

    3. The attempt at a solution

    I think that the key to this problem is to use the SC distribution rule. But using distribution on the left yields (A ∩ A) ∪ (A ∩ B), and I can't think of anyway to get the left side to (A ∩ A'). There is a hint with the question about complements of complements, but I don't see how to use that. I have tried variations of double negation and still cant get it started. If I can get the left side to ((A` ∪ B) ∩ A) before distribution that would work, but I'm not sure how to get there!

    Thanks in advance for the help, I just need help getting this question started!
     
  2. jcsd
  3. May 16, 2010 #2

    lanedance

    User Avatar
    Homework Helper

    i'm not totally convinced after a quick look:

    ((A ∪ B) ∩ A) = (A ∩ A) ∪ (B ∩ A) = (A) ∪ (A ∩ B) =...

    (A ∩ A') ∪ (A ∩ B) = (empty) ∪ (A ∩ B) =...

    assume you can pick an element a in A, that is not in B. Its in the 1st, but not in the 2nd?
     
    Last edited: May 17, 2010
  4. May 17, 2010 #3

    HallsofIvy

    User Avatar
    Science Advisor

    You can't prove it- it's not true!

    If A and B are disjoint the [itex]A\cap B[/itex] is empty and, of course, [itex]A\cap A'[/itex] is empty. If A and B are disjoint, then the right side is the empty set. But A is always a subset of [itex]A\cup B[/itex] so [itex](A\cup B)\cap A= A[/itex].

    As a counter example, let A= {1, 2, 3, 4} and B= {0} in the set of integers. Then [itex]A\cap A'= \Phi[/itex], and [itex]A\cap B= \Phi[/itex] so [itex](A\cap A')\cup (A\cap B)[/itex][itex]= \Phi[/itex]. But on the left, [itex]A\cup B= \{0, 1, 2, 3, 4\}[/itex] so [itex](A\cup B)\cap A= \{0, 1, 2, 3, 4\}\cap \{1, 2, 3, 4\}= \{1, 2, 3, 4\}= A[/itex].

    Your hint mentions "complement of a complement" but you have no "complement of a complement" in the problem. Perhaps you have miscopied the problem.

     
  5. May 17, 2010 #4
    You two are my heroes. I started looking into the more because I believed the same thing. I copied the question from my online class system into this forum, but then I found that he had entered the questions online wrong. Else where in our class literature, the question is written as ((A ∪ B) ∩ A) = (A ∩ A'') ∪ (A ∩ B), which I can solve.

    I think I learned more from the original, wrong question!

    Thanks again for the help.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook