1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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




Loading...