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: Set theory dilemma

  1. Mar 28, 2010 #1
    1. The problem statement, all variables and given/known data
    Let A,B,C be sets where A n C = B n C and A n Cc = B n Cc. Then A=B.


    2. Relevant equations



    3. The attempt at a solution

    To prove two sets equal, i think we want to let x be in A, and then show as a result that x in B also. However, i don't see how this is possible given our hypothesis. x in A does not mean x in A n C. Also, x in A does not mean x in A n Cc. Thoughts, suggestions, hints? Very much appreciated!
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Mar 29, 2010 #2
    What if x is in C?

    What if x is not in C?

    If you can do these cases separately you can piece them together to get a complete proof.
     
  4. Mar 29, 2010 #3
    If possible, let A contain an element x which is not in B.
    x can't belong to C ( otherwise , it would belong to B too ;A n C = B n C ).
    Hence, x is in C' ,i.e., x is in A n C' . This is a contradiction as A n C' = B n C' .
     
  5. Mar 29, 2010 #4
    case 1: let x in A and x in C. therefore, x in AnC by definition, and x in BnC by our hypothesis(AnC = BnC). Therefore x in B by definition. A=B.

    case 2: let x in A and x not in C. therefore, x in AnC' by definition, and x in BnC' by our hypothesis(AnC' = BnC'). Therefore x in B by definition. A=B.

    RASMHOP, what do you think about this?
     
  6. Mar 29, 2010 #5
    The idea is completely right though some of your statements are a bit misplaced. At the end of case 1 you assert A=B, but you have not proven this yet. What you have proven at the end of case 1 is that if x is in A and C, then x is in B. Similarly at the end of case 2 you have proven that if x is in A and not in C, then x is in B. Thus you can now note that if x is in A, then x is in B (since it's in either C or C'). This proves [itex]A \subseteq B[/itex]. Of course technically you also need the reverse direction where you assume that x is in B, but since the statement is symmetric you can simply note that by replacing the role of A and B you get [itex]B \subseteq A[/itex] so you have A=B.
     
  7. Mar 29, 2010 #6
    Excellent. I decided to investigate Eynstone's suggestion of proof by contradiction as well.

    Assume AnC=BnC, AnC'=BnC', and A not= B.

    Then there exists x such that x in A and x not in B.

    case 1: x in C. therefore x in AnC. therefore x in BnC, so x in B and x in C. (contradiction, we are done)

    case 2: x in C'. therefore x in AnC'. therefore x in BnC', so x in B and x in C'. (contradiction, we are done)

    since A not= B leads to contradiction, we conclude that A=B.

    also must prove cases for when x in B and x not in A, but they are symmetric.

    how does this look to you guys? and which one is preferable? Thanks
     
  8. Mar 29, 2010 #7
    Good job. It looks like you nailed it.

    Both proofs are very similar to each other, and use the same basic idea. Both would be perfectly acceptable and I see no real reason to prefer one over the other. Together they showcase a wide range of common techniques in problem solving and proving theorems:
    - Using symmetry
    - Proving set equality A=B by proving x is in A if and only if x is in B.
    - Splitting an argument into cases.
    - Using contradiction.
    I would probably say that the proof by contradiction is the easiest to think of. If something doesn't directly work out for you often you can get a much clearer picture by assuming the negation of your desired conclusion and then thinking about why this case is absurd. However while contradiction is often a great way to come up with an argument in many cases you can tidy up the proof slightly by transforming the proof into a direct one using the same ideas.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook