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: 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