Solving a Set Theory Dilemma

[coreyB]

Homework Statement

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

Homework Equations

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 C^c. Thoughts, suggestions, hints? Very much appreciated!

 

[rasmhop]

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 C^c. 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.

 

[Eynstone]

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

 

[coreyB]

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?

 

[rasmhop]

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?

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.

 

[coreyB]

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

 

[rasmhop]

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