# Proving elementary set theory equalities/inclusions

Could you please correct/help me on my work bellow about basic set theory?

Currently trying to prove the following sets:

$$\quad$$a)$$\quad$$ $$C\subseteq A \implies A\setminus (B\setminus C) = (A\setminus B)\cup C$$

PROOF: Let $$x\in (A\setminus C)$$, if $$C\not\subseteq B$$ then $$A\setminus(B\setminus C)=A$$ and $$(A\setminus B)\cup C=A$$, hence the statement is true for $$C\not\subseteq B$$. However, if $$C\subseteq B$$, then $$(A\setminus B)\cup C=A\setminus (B\setminus C)$$, thus the proof is complete.

$$\quad$$b)$$\quad$$ $$A\vartriangle B = (A\cup B)\setminus (A\cap B)$$, where $$A\vartriangle B = (A\setminus B)\cup (B\setminus A)$$

PROOF: Let set $$X=A\cup B$$, then $$X\setminus(A\cap B)=A\vartriangle B$$, since $$X=(A\cup B)$$ then $$A\vartriangle B = (A\cup B)\setminus (A\cap B)$$.

$$\quad$$c)$$\quad$$ $$(A\setminus B)\cap C = (A\cap C)\setminus (B\cap C)$$

I'm not sure how to start the proof for c), I'm trying using Venn diagrams to understand the set interactions easier but it seems that in the end that everything is easy to comprehend but harder to put into mathematical language. Thanks.

• I dk whether you have some typos or are using a non-standard notation. For example, what does $A(B$ \ $C)$ mean? – DanielWainfleet Sep 7 '19 at 3:15
• @DanielWainfleet it seems some backslashes did not show up – Vsotvep Sep 7 '19 at 4:01
• Ah So. Sometimes I type the \ symbol $outside$ of the dollar signs, preceded and followed by a space, instead of typing \setminus or \backslash. – DanielWainfleet Sep 9 '19 at 4:51

As a general advice, often it is easiest to show two sets $$X$$ and $$Y$$ are equal, by showing that $$X\subseteq Y$$ and $$Y\subseteq X$$. We do this by taking an arbitrary element in one set, and showing it is in the other, and vice versa.

## a)

You start with taking some $$x$$, which is then never used in the proof.

Also, $$A\setminus (B\setminus C)=A$$ is true if and only if all elements of $$B\setminus C$$ lie outside $$A$$. This is only true if all elements of $$B\cap A$$ are elements of $$C$$, i.e. the following shaded area is empty: $$C\not\subseteq B$$ does not imply any of the sort. The only thing it states, is that there is some element in $$C$$ that is not in $$B$$, i.e. the shaded area is nonempty: Instead, we can prove the exercise by using the tactic I suggested. We start with $$A\setminus (B\setminus C)\subseteq (A\setminus B)\cup C$$:

Suppose that $$x\in A\setminus(B\setminus C)$$, then we know that $$x\in A$$ and $$x\notin B\setminus C$$. Since $$x\notin B\setminus C$$, we also know that $$x\notin B$$ or that $$x\in C$$. So in case $$x\notin B$$, then we have that $$x\in A$$ and $$x\notin B$$, and thus $$x\in A\setminus B$$, implying that $$x\in (A\setminus B)\cup C$$ as well. On the other hand, if $$x\in C$$, then clearly $$x\in (A\setminus B)\cup C$$.

Now we do the other direction $$(A\setminus B)\cup C\subseteq A\setminus (B\setminus C)$$:

Suppose $$x\in (A\setminus B)\cup C$$, then $$x\in A\setminus B$$ or $$x\in C$$. We have to show that $$x\in A$$ and that $$x\notin B\setminus C$$. In case that $$x\in A\setminus B$$, we see that $$x\in A$$ and that $$x\notin B$$, which implies $$x\notin B\setminus C$$ either. On the other hand, if $$x\in C$$, we see that $$x\notin B\setminus C$$, and we have $$x\in A$$ because $$C\subseteq A$$.

## b)

Your second proof does not really show anything, since the first "then" basically contains everything you need to prove. You don't use the definition of $$A\vartriangle B:=(A\setminus B)\cup (B\setminus A)$$, so that is a red flag that something is missing.

By substituting the definition of $$A\vartriangle B$$, what you have to show is $$(A\setminus B)\cup (B\setminus A)=(A\cup B)\setminus (A\cap B)$$. Using my advice, by showing these sets are subsets of each other, it should be not too difficult, so I leave this to you.

## c)

See the other answer for this.

Suppose we have $$x \in (A\setminus B)\cap C$$. Then $$x \in C$$ and $$x \in A$$, but $$x \notin B$$. So $$x \in A \cap C$$, but $$x \notin B\cap C$$, therefore $$x \in (A\cap C)\setminus (B\cap C)$$. This proves that $$(A\setminus B)\cap C \subseteq (A\cap C)\setminus(B\cap C)$$. Can you prove the reverse inclusion?

It is often useful to re-write the parts of a "formula" as their "1st-order" meanings, i.e. their unabbreviated definitions, And to apply the laws of logic that for propositions $$P,Q$$ we have $$(\neg (P\lor Q))\iff ((\neg P)\land (\neg Q))$$ and we have $$(\neg (P\land Q))\iff ((\neg P)\lor (\neg Q))$$ and (of course) $$(\neg \neg P)\iff P.$$ And that each of $$\lor, \land$$ is distributive over the other.

It is often best to do this from the inside outward or from R to L. To demonstrate:

For any $$x$$ we have:

$$x\in B\setminus C\iff (x\in B\land x\not \in C).$$

So $$x\not \in B\setminus C\iff [\neg (x\in B\land x\not \in C)]\iff (x\not \in B\lor x\in C).\quad \bullet$$

Therefore $$x\in A\setminus (B\setminus C) \iff (x\in A\land x \not \in B\setminus C)$$ $$\iff (x\in A\land (x\not \in B\lor x\in C)) \quad \text {(by \bullet)}$$ $$\iff ((x\in A\land x\not \in B)\lor (x\in A\land x\in C))\quad \text { (Distributive)}$$ $$\iff ((x\in A\setminus B)\lor (x\in A\cap C))$$ $$\iff x\in (A\setminus B)\cup (A\cap C).$$ Now if $$C\subset A$$ then $$A\cap C=C$$. So from the 1st & last displayed (centered) lines we conclude

that $$C\subset A$$ implies that for all $$x$$ we have $$x\in A\setminus (B\setminus C)$$ $$\iff x\in (A\setminus B)\cup (A\cap C)$$ $$\iff x\in (A\setminus B)\cup C.$$

• The modern convention is that $C\subset A$ means $C\subseteq A.$ To say $D$ is a proper subset of $E$ you must write $D\subsetneq E$. – DanielWainfleet Sep 9 '19 at 6:25
1. To solve this problem, it may be approached as \begin{align*} C\subseteq A \Longrightarrow A - (B - C) & = A\cap\overline{(B \cap \overline{C})} = A\cap(\overline{B}\cup C)\\ & = (A\cap\overline{B})\cup(A\cap C)\\ & = (A\cap\overline{B})\cup C = (A-B)\cup C \end{align*}

2. For the second question, we have \begin{align*} (A\cup B) - (A\cap B) & = (A\cup B)\cap(\overline{A\cap B}) = (A\cup B)\cap(\overline{A}\cup\overline{B})\\ & = [(A\cup B)\cap\overline{A}]\cup[(A\cup B)\cap\overline{B}]\\ & = [(A\cap\overline{A})\cup(B\cap\overline{A})]\cup[(A\cap\overline{B})\cup(B\cap\overline{B})]\\ & = (B\cap\overline{A})\cup(A\cap\overline{B}) = (B-A)\cup(A-B) \end{align*}

3. Finally, the last part can be solved as follows

\begin{align*} (A\cap C) - (B\cap C) & = (A\cap C)\cap(\overline{B\cap C}) = (A\cap C)\cap(\overline{B}\cup\overline{C})\\ & = (A\cap C\cap\overline{B})\cup(A\cap C\cap\overline{C})\\ & = A\cap C\cap\overline{B} = (A\cap\overline{B})\cap C = (A-B)\cap C \end{align*}