# Is this proof by contradiction using sets correct?

Suppose $A \subseteq B$ and $x \in A$ and $x \notin B$ \ $C$. Prove that $x \in C$.

Basically what i need to do is to prove this by contradiction, so what i made was:

first of all, by applying the definitions of symetric diference, De Morgan and the definition of implication i found an equivalent expression for $x \notin B$ \ $C$, as $x \in B \rightarrow x \in C$.

Proof:

Suppose that $x \notin C$, since $x \in A$ and $A \subseteq B$ it follows that $x \in B$, because $x \in B \rightarrow x \in C$ it contradicts that $x \notin C$, so it follows that $x \in C$

is this correct?

-
The part of your proof that you wrote out is correct. Together with the unseen part where you reached the (correct) expression with implication, it is not as short as it could be. A small point: $B\setminus C$ is not called the symmetric difference. The symmetric difference of $X$ and $Y$, often written as $X\:\Delta\:Y$, consists of the points that are in $A\cup B$ but not in $A\cap B$. It can be expressed in various ways, for example $(X\setminus Y)\cup (Y\setminus X)$. Note that it is symmetric in $X$ and $Y$, while $X\setminus Y$ isn't. –  André Nicolas Feb 1 '12 at 7:28
Sorry, typo above, where it says $A\cup B$, read $X\cup Y$, and same with intersection. –  André Nicolas Feb 1 '12 at 7:42
Yes, sorry about that, you are right –  mayhem Feb 1 '12 at 7:42

## 2 Answers

The statement "because $x\in B\rightarrow x\in C$" should be justified: you have $x\in B$, and you also have the hypothesis $x\notin B/C$. By definition, $B/C$ is the set of all $x$ that are in $B$ but not in $C$. So, now you can conclude $x\in C$.

It would be just as easy to argue straightforwardly:

Let $x\in A$. Since $A\subset B$, we have $x\in B$.

Now suppose $x\notin B/C$.

By the definition of $B/C$ either $x\notin B$ or $x\in C$. Since we have $x\in B$, it follows that $x\in C$, and we are done.

-

Here is a more calculation-style answer to this old question. Since the first part ($\;A \subseteq B\;$) means $\;\langle \forall x : x \in A : x \in B \rangle\;$, it seems we'd best start with the rest of what we're given, and try to simplify that while assuming the first part.

So we calculate, for every $x$:

\begin{align} & x \in A \;\land\; x \not\in B \setminus C \\ \equiv & \;\;\;\;\;\text{"definition of $\;\setminus\;$"} \\ & x \in A \;\land\; \lnot(x \in B \land x \not\in C) \\ \equiv & \;\;\;\;\;\text{"use assumption: by $\;A \subseteq B\;$, $\;x \in A\;$ implies $\;x \in B\;$"} \\ & x \in A \;\land\; \lnot(\textrm{true} \land x \not\in C) \\ \equiv & \;\;\;\;\;\text{"logic: simplify"} \\ & x \in A \;\land\; x \in C \\ \Rightarrow & \;\;\;\;\;\text{"logic: weaken -- to reach the requested goal"} \\ & x \in C \\ \end{align} And that concludes the proof.

Note how this proof is really mechanical, as in every step there is only one thing to do. (Except that in the second step one might be tempted to first apply De Morgan, but it is obvious that after that we really must start to use the assumption that $\;A \subseteq B\;$.)

-