0
$\begingroup$

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?

  • 0
    Yes, sorry about that, you are right2012-02-01

2 Answers 2

1

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.

0

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\;$.)