# Set Theory Contradiction Proof Verification

Let A, B and C be subsets of a universal set U.

Prove by contradiction that $$A\cap B \subseteq C \to (A-C)\cap B = \emptyset$$

Suppose otherwise, $A\cap B\subseteq C \land (A-C)\cap B \neq \emptyset$. Let $n\in A$, then by definition of the subset, $n\in C$. Since $n\in A \land n\in C, n\not \in (A-C)$, by definition of the set difference, this means $(A-C)= \emptyset$. Therefor, $n\not \in (A-C)\cap B$, by definition of the intersection. Thus, by definition of the empty set, $(A-C)\cap B = \emptyset$. This is a contradiction. Thus, $A\cap B \subseteq C \to (A-C)\cap B = \emptyset$ must be true.

Can someone tell me whether I did this right. I think it makes sense, but it also seems like I made a mistake somewhere because it seems too easy and short. Thank you.

• Problem: "let $n\in A$, then by definition (of what), $n \in C$". No. If we let $n\in A\cap B$, then we can say $n \in C$. That is, $$(n\in A \land n\in B) \rightarrow n\in C,$$ by definition of $A \cap B\subseteq C$. – Namaste Mar 10 '17 at 20:34
• The "definition of subset" is the flaw in the proof. You appear to be trying to conclude that $A\cap B \subseteq\ C$ implies that $A\subseteq C$, but that is clearly false – adfriedman Mar 10 '17 at 20:43
• So would my prove work if I added $n\in A \land n\in B$? Since then that part would be true? It seems that I don't need to use the B at all here, that's why I left it out of the proof. – Maritza Mar 10 '17 at 20:48
• Yes, it should work. Why don't you edit your post, scroll down just below your question, write "edit": and take it from there, amending the statement to state $(A\cap B) \subseteq C$ means $n \in (A\cap B) \rightarrow n\in C$. – Namaste Mar 10 '17 at 21:05
• Just be careful: $A\cap B$ means $n \in A \land n\in B$. The fact that this intersection is a subset of $C$ does not mean we can then say: "$n \in A \land n\in B\land n\in C".$ Rather, $(A\cap B) \subseteq C$ means that "IF $(n \in A \land n\in B)$, THEN $n \in C$. – Namaste Mar 10 '17 at 21:12

We prove following:

(a) $(A \cap B)-C=(A-C)\cap B$

\begin{align} x \in (A \cap B ) - C &\leftrightarrow x \in (A \cap B) \wedge x \notin C \\ &\leftrightarrow (x \in A \wedge x \in B)\wedge x \notin C \\ &\leftrightarrow x \in A \wedge (x \in B\wedge x \notin C )\\ &\leftrightarrow x \in A \wedge (x \notin C \wedge x \in B) \\ &\leftrightarrow (x \in A \wedge x \notin C) \wedge x \in B \\ &\leftrightarrow x \in (A -C) \wedge x \in B \\ &\leftrightarrow x \in (A -C)\cap B \end{align}

(b) $(A \cup B)\setminus B=A \setminus B$ \begin{align*} x \in(A \cup B)\setminus B &\leftrightarrow x \in (A\cup B) \wedge x \notin B \\ &\leftrightarrow (x \in A \vee x \in B)\wedge x \notin B\\ &\leftrightarrow (x \in A \wedge x \notin B) \vee (x \in B \wedge x \notin B) \\ &\leftrightarrow x \in (A\setminus B) \vee x \in (B\setminus B) \\ &\leftrightarrow x \in ((A\setminus B) \cup \emptyset )\\ &\leftrightarrow x \in (A\setminus B) \end{align*}

We prove

(c) $A\cap B \subseteq C \to (A-C)\cap B = \emptyset$

direct \begin{align} (A-C)\cap B &= (A \cap B)-C \text{ (by (a))} \\ &=((A\cap B) \cup C) -C \text{ (by (b))}\\ &= C -C \text{ (because } A\cap B \subseteq C) \\&= \emptyset \end{align}

by contrapositive \begin{align} (A -C)\cap B \neq \emptyset &\to \exists x : x\in (A -C)\cap B \\&\to \exists x :x \in (A \cap B) -C \text{ (by (a))}\\ &\to \exists x : (x \in A \wedge x \in B )\wedge x \notin C \text{ (by Definition)}\\ &\to A\cap B \nsubseteq C \end{align}

by contradiction \begin{align} (A -C)\cap B \neq \emptyset &\to \exists x : x\in (A -C)\cap B \\&\to \exists x :x \in (A \cap B) -C \text{ (by (a))}\\ &\to \exists x : x \in C \wedge x \notin C \text{ (by hypothesis)}\\ &\to \exists x: x \in \emptyset \text{ (Absurd!)} \end{align}

You have proven that, for every $n\in A$, $n\notin (A-C)\cap B$. That does not make $(A-C)\cap B$ the empty set, since you haven't proven that it has no elements, only that it has no elements that belong to $A$.

The answer is even shorter than yours: suppose that $(A-C)\cap B\neq\emptyset$. Then, there exists some $x\in (A-C)\cap B$. This means that $x\in A$, $x\notin C$ and $x\in B$, that is, $x\in A\cap B$ but $x\notin C$. This proves by definition of inclusion that the statement $A\cap B\subseteq C$ is false. Since we find that $(A-C)\cap B\neq\emptyset\Rightarrow A\cap B\not\subseteq C$, we conclude that $(A\cap B)\subseteq C\Rightarrow (A-C) \cap B=\emptyset$.

• You proof is essentially a proof of the contrapositive. (You assume only the negation of the consequent, and derive the negation of the antecedent. And note your typo: You should have..."This means that $x \in A, x\notin C,$ and $x \in B$,..." If you don't correct the typo, I'm afraid your answer is more confusing and helpful. – Namaste Mar 10 '17 at 20:45
• The conclusion statement you write, starting with "We then conclude" is incorrect. What you should have written is something to the effect: Since we find that $((A-C)\cap B \neq \emptyset) \rightarrow ((A\cap B \not\subseteq C)$, we conclude that $$((A\cap B)\subset C) \rightarrow ((A-C) \cap B = \emptyset)$$ – Namaste Mar 10 '17 at 20:56
• @amWhy Thank you, I've edited my answer and rewritten the conclusion as you suggested. What I was trying to say is that the proof can be easily adapted to be a proof by contradiction, you just have to suppose that the hypothesis and the opposite of the thesis are true at the same time, and from this follows a contradiction. – Wild Feather Mar 10 '17 at 22:06
• Nicely done, WildFeather. And yes, the only change to make it a proof by contradiction would be just as you suggest. The only reason I've been persistent in comments, and a "stickler" for precision has been to assist the Asker in making distinctions between various proof approaches, and also to aid them in sticking to definitions, etc. You've been very cooperative and deserve an upvote for your conscientiousness and clarity!. – Namaste Mar 10 '17 at 23:51
• @amWhy Thank you very much! I'm glad I could help! :) – Wild Feather Mar 11 '17 at 8:39