# Set theory dilemma

## Homework Statement

Let A,B,C be sets where A n C = B n C and A n Cc = B n Cc. Then A=B.

## 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!

## 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!

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.

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' .

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.

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.

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 $A \subseteq B$. 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 $B \subseteq A$ so you have A=B.

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)

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

Excellent. I decided to investigate Eynstone's suggestion of proof by contradiction as well.
Good job. It looks like you nailed it.

how does this look to you guys? and which one is preferable? Thanks
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.