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 set equality

  1. Apr 19, 2010 #1
    1. The problem statement, all variables and given/known data

    Prove the following identities involving complementation of sets.
    1. A ∩ [(A ∩ B)C] = A - B
    2. A ∩ [(A ∩ BC)C] = A ∩ B
    3. (A ∪ B) ∩ AC = B - A

    2. Relevant equations
    AC = A complement. If A is contained in some understood universal set U, then the complement of A is the set AC = {x ∈ U: x ∉ A}.
    A - B = { x ∈ A and x ∉ B}
    B - A = { x∈ B and x ∉ A}
    A ∪ B = {x ∈ A or x ∈ B}
    A ∩ B = { x ∈ A and x ∈ B}

    3. The attempt at a solution
    Since I am dealing with set equality and trying to show when one set equals another, I have been trying to show that x ∈ the first set if and only if x ∈ the second set in each of these cases.

    I am not actually going to put this in legit proof form here but I will just summarize my steps for you and know that I plan on doing it better later once I figure it out entirely.

    For part 1, I started off by choosing an arbitrary x in A ∩ [(A ∩ B)C]. Then, if x is in this set, x ∈ A and x ∉ A ∩ B. This means that x ∈ A and x ∉ A or x ∉ B. Well I am trying to show that this is equal to A - B, where x ∈ A and x ∉ B so I have the parts I need, however, I don't know what to do with the part where it says x ∉ A.

    For part 2, I started off by choosing an arbitrary x in A ∩ [(A ∩ BC/SUP])C/SUP]]. Then, if x is in this set, x∈ A and x ∉ A ∩ BC/SUP]. This means that x ∈ A and x ∉ A or x ∉ B^C. Once again, this means that x∈A and x∉A or x∈ B. Well I am trying to show that this set is equal to A ∩ B, where x ∈ A and x ∈ B. But, once again, I have that extra part in the middle where x ∉ A that I don't know what to do about.

    For part 3, I chose an arbitrary x in (A ∪ B) ∩ AC. Then, if x is in this set, x ∈ A or x ∈ B and x ∈ AC. Well, this means x ∈ A or x ∈ B and x ∉ A. This time, I have that other term in the front saying x ∈ A when I really need to get to B - A, where x∈ B and x ∉ A.

    Am I completely missing something here?
    Thanks.
     
  2. jcsd
  3. Apr 19, 2010 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    That sort of proof gets tedious after while. Do you know deMorgan's laws applied to sets? http://planetmath.org/encyclopedia/DeMorgansLaws.html [Broken] and the distributive laws of union and intersection?
     
    Last edited by a moderator: May 4, 2017
  4. Apr 19, 2010 #3
    All we really know about de Morgan's laws is that, prior to this problem, we had to prove de Morgan's second law.
     
  5. Apr 19, 2010 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Well, ok then. For the first part if x is not in A, then x is not in A intersect anything, nor is it in A minus anything. So x is not in either side. So x is in one side iff x is in the other side. Because it's not in either. That's how the negative side of these things works. These things are a lot easier just using set algebra than juggling words. Hope you get to that phase soon.
     
  6. Apr 20, 2010 #5
    We are actually completely done with discussing sets so I don't know it we are going to get to there. :/
     
  7. Apr 20, 2010 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Too bad, maybe next course? Here's the first one. An(AnB)^C=An(A^C U B^C)=(An(A^C))U(An(B^C)=An(B^C), since An(A^C) is empty. And An(B^C)=A-B. Done.
     
  8. Apr 20, 2010 #7
    That actually makes some sense to me but I wonder if I will even be away to get away with set algebra since we haven't covered it.
    But thank you so much for that.
     
  9. Apr 20, 2010 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You can do it just by logic too. Take the first one, you got up to "This means that x ∈ A and x ∉ A or x ∉ B." If x is in A, then x can't NOT be in A too. So the second part of the 'or' must be true. So you get x ∈ A and x ∉ B. Which is A-B.
     
  10. Apr 20, 2010 #9
    Thank you.
    It's all solved now.
    :)
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook