Suppose that $A$, $B$ and $C$ are sets, and $A\setminus B\subseteq C$. Show that $A\setminus C\subseteq B$.

Question

Suppose that $A$, $B$ and $C$ are sets, and $A\setminus B\subseteq C$. Show that $A\setminus C\subseteq B$.

$A\setminus B\subseteq C$ means that there are $x\in A, x\notin B$ and $x\in C$.

Using contradiction, we say that $C \not\supset A\setminus B$ therefore $x\in A, x\notin B$ and $x\notin C$, however this contradicts my hypothesis.

Is this right? It looks kind of weird.

Answer 1

$A\setminus B \subseteq C$ means that whenever there exists $x \in A,x \notin B,$ then we must have $x \in C.$

Using contradiction, we assume $A \setminus C \not\subseteq B,$ then there must exist $x\in A,x \notin C$ such that $x \notin B.$ Thus $x \in A \setminus B \subseteq C,$ so $x \in C$ which contradicts the given hypothesis.

When proving by contradiction, you assume that the hypothesis is true but the assertion is false.

Answer 2

Let $x\in A\setminus C$; suppose $x\notin B$, then $x\in A\setminus B$, then by hypothesis we have $x\in C$. A contradiction.

We have that if $x\in A\setminus C$, then $x\in B$, or which is equivalent $A\setminus C\subseteq B$

Answer 3

(1) $A$\ $ B \subseteq C$

(2) $(x\in A \land x\notin B) \rightarrow x\in C$ , for all $x$.

(3) $A$ \ $C \nsubseteq B$ ( Hypothesis, for refutation).

(4) $\neg \forall(x) ( (x\in A \land x\notin C) \rightarrow x\in B)$

(5) $(x\in A \land x\notin C) \land x\notin B$, for some $x$ ( by $\neg(X\rightarrow Y)\equiv (X\land \neg Y)$).

(6) $(x\in A \land x\notin B) \land x\notin C$, for some $x$ ( by $\land$ commutatvity and associativity).

(7) $\neg\exists (x) [ (x\in A \land x\notin B) \land x\notin C ]$ ( by (2) )

(8) Contradiction ( by (6) and (7) )

(9) $A$ \ $C \subseteq B$ ( by (3-8) and reductio ad absurdum)