# For an universal set $U$, prove or disprove, for sets $A,B,C \subseteq U, A \cap C = B \cap C \implies A = B$

I've tried to solve the question in two different ways :

1. Using Characteristic function(CF).

$$CF(A) = \{ 1, x \in A \text{ ; } 0, \text{elsewhere}\}$$ $$CF(B) = \{ 1, x \in B \text{ ; } 0, \text{elsewhere} \}$$ $$CF(C) = \{ 1, x \in C \text{ ; } 0, \text{elsewhere} \}$$

Since, $$A \cap C = B \cap C$$ $$CF(A) * CF(B) = CF(B) * CF (C)$$ $$\text{Therefore, } CF(A) = CF(B)$$ $$\implies A=B$$

1. Consider the following counter example :

Let $$A = \{1,2,3\} , B = \{2,3,4,5\} , C = \{2,3\}.$$ $$A \cap C = \{2,3\} \text{ and } B \cap C = \{2,3\} \text{ but } A \neq B.$$ Hence disproved by counter example.

Which one is correct ? Many thanks in advance.

-

The statement $A \cap C = B \cap C \implies A = B$ is false.

Your conclusion that "Therefore, $CF(A) = CF(B)$" is false, since you didn't consider the possibility of dividing by zero.

Your counterexample is sufficient to disprove the statement. Also, I would suggest considering three disjoint sets $A, B, C$. In this case, $A \cap C = \varnothing = B \cap C$, yet $A \neq B$

-
I'm studying this concept in school; only there's bit more to this shown here than I've learnt so far. – David Sep 28 '11 at 2:24
@David: I'm not sure I get what you're trying to say. Would you like me to elaborate? – The Chaz 2.0 Sep 28 '11 at 2:27
Thank you very much. Could you please elaborate how o disprove using characteristic functions i.e. by considering dividing by 0 ? – Sunil Sep 28 '11 at 14:24
@Sunil How do you go from $CF(A) * CF(C) = CF(B) * CF (C)$ to Therefore $CF(A)=CF(B)$? ;) – N. S. Oct 23 '12 at 21:21

A picture might help with this one too:

-

And, of course, if $C = \varnothing$ then $A \cap C = B \cap C = \varnothing$ for any $A$ and $B$.

-