I'm working through the set theory exercises in Apostol's Calculus Volume 1. I'm down to the last problem:
Show that one of the following results is always correct and the other one is sometimes wrong. Then find a necessary and sufficient condition for the one that is sometimes wrong to always be correct.
i) $A-(B-C)=(A-B)\cup C$
ii) $A-(B\cup C)=(A-B)-C$.
So far I've worked out (by drawing some venn diagrams) that (i) is sometimes wrong and (ii) is always correct. I even found a counter-example to (i) so it's definitely sometimes wrong. I proved (ii) is always correct. The "necessary and sufficient" condition part is the one that I'm stuck on but I think I found the answer.
Basically I've also worked out that if $C\underline{\subset} A$ then $x\in (A-B)\cup C\Rightarrow x\in A-(B-C)$.
The motivation for $C\subseteq A$ is as follows: From the right side we see that if $x\in (A-B)\cup C$ then $x\in$ at least one of $(A-B)$ or $C$; now in the case that $x\in C$, we see that $x\not\in A-(B-C)$ unless $C\subseteq A$; this is because $B-C$ gets rid of all $C$ elements in $B$, so that $A-(B-C)$ doesn't get rid of any $C$ elements in $A$, SO ALL $C$'s in $A$ are still there; therefore, in order for $x\in C\Rightarrow x\in A-(B-C)$, we must have $C\subseteq A$, so I'm thinking that maybe $C\subseteq A$ is the condition we are looking for.
The only problem now is proving that if $C\subseteq A$ then $x\in A-(B-C)\Rightarrow x\in (A-B)\cup C$ and this is proving difficult.
I think my main problem is that I don't know how to manipulate $A-(B-C)$. I've reasoned as follows so far: If $x\in A-(B-C)$ then $x\in A$ and $\not\in (B-C)$. Then $x\in A$ and $\not\in$ the part of $B$ that isn't $C$. (I think saying it like this isn't rigorous enough, but correct if if I'm wrong.) Then there are two cases: $x\in A$ and $x\in B$, so then $x\in C$, since it cannot be in the part of $B$ that isn't $C$. This checks, because $C\subseteq A$. So one possibility is $x\in C$. On the other hand, we could also have $x\in A$ and $x\not\in B$, i.e. $x\in (A-B)$. Thus $x\in(A-B)\cup C$.
I'm not sure how rigorous this is and would really like to know how someone experienced would write such a proof. It just seems to be hard to word and I'm having trouble going from step to step in set theory proofs in general due to the "vagueness" of such proofs. E.g. What if someone else doesn't agree that my above casework is obvious, and wants something more rigorous?
Thanks
Best Answer
I think the proof becomes easier if you turn the notation $X-Y$ into $X\cap Y^c$, which means the intersection between $X$ and the complement of $Y$. (They're equivalent.)
Your interpretation is right, but more precisely, you could say "$x \not\in (B-C)=B \cap C^c$ means that either $x \not\in B$ or $x \notin C^c$, so $x\not\in B$ or $x \in C$." (To not be in the intersection it is enough for $x$ to not be in one of the sets.)
This sentence is a little unclear. The two cases are
Case 1: $x\in A$ and $x \notin B$ means that $x\in A-B$, so $x \in (A-B)\cup C$.
Case 2: $x \in C \implies x \in (A-B)\cup C$.
(This is pretty much what you wrote in the sentence following the one I just quoted.)
Note that you didn't really use the hypothesis that $C \subseteq A$ anywhere to prove this inclusion.
Another way to check that $C \subseteq A \implies A-(B-C)=(A-B)\cup C$:
\begin{align} A-(B-C) &= A \cap (B\cap C^c)^c \\ &=A\cap (B^c \cup C)\\ &= (A \cap B^c) \cup (A \cap C) \\ &= (A \cap B^c) \cup C \quad \text{ because $C \subseteq A$}\\ &=(A -B)\cup C \end{align}