# Homework Help: Set theory dilemma

1. Mar 28, 2010

### coreyB

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. Mar 29, 2010

### rasmhop

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.

3. Mar 29, 2010

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

4. Mar 29, 2010

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

5. Mar 29, 2010

### rasmhop

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.

6. Mar 29, 2010

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

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

7. Mar 29, 2010

### rasmhop

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.