Let A, B and C be subsets of a universal set U.
Prove C $\subseteq$ (A-B)$^c$ $\to$ A $\cap$ C $\subseteq$ B
My attempt:
Suppose C $\subseteq$ (A-B)$^c$
$\forall$x$\in$C, x$\in$(A-B)$^c$
$\forall$x$\in$C, x$\not\in$(A-B)
$\forall$x$\in$C, x$\not\in$A $\lor$ x$\in$B
Now I'm stuck, it seems like that last statement isn't where I want to go, but I can't see a better way to go about this.
Any help would be awesome!
$\endgroup$ 33 Answers
$\begingroup$First of all: I always draw Venn-diagrams to visualize proofs of set theory (in cases where we are considering a small number of sets, such as in this case). These help me to see what I am doing.
Second hint: If you have to prove the inclusion of one set in another, the way to proceed is: take an arbitrary element of set $1$ and show that it is an element of set $2$. Since the element was arbitrary, it is valid for all elements of set $1$, proving the inclusion.
So let me use this second hint to prove your problem. Suppose $x \in A \cap C$. This means that $x \in A$ and $x \in C$. Because of the assumption that $C \subseteq (A - B)^c$, we know that $x \in (A-B)^c$, which means that $x \notin A - B$. Since $x \in A$, we must have that $x \in A \cap B$. Hence in particular we have that $x \in B$.
Since $x$ was chosen arbitrary, this holds for all elements of $A \cap C$ and hence $A \cap C \subseteq B$.
As a last hint, specifically on proof-writting: try to use full sentences instead of lines of symbols. Using full sentences makes it easier to follow your argument and also makes it easier for yourself to keep track of what exactly you are doing.
$\endgroup$ 0 $\begingroup$Take $x \in A\cap C $, then $x \in A $ and $x\in C $ It implies $x \in A $ and $x\in (A-B)^c $ It implies $x \in A$ and $x \notin A-B $ Then $x$ must be in $A \cap B$ and in particular $x\in B $.
$\endgroup$ $\begingroup$The last line before "Now I'm stuck" is wrong. If you apply correctly De Morgan laws from the line before, you obtain $\forall x\in C,\,x\notin A\vee x\in B$. Now, you can proceed with a proof of the RHS: $$(\forall y,\ y\in A\wedge y\in C)\implies (\forall y,\ y\in A\wedge(y\notin A\vee y\in B)) \stackrel{\text{distributive}}{\implies}\cdots$$
$\endgroup$
