properties of set difference

Let $A,B,C,D,X$ be sets.

1. $A\setminus B\subseteq A$. This is obvious by definition.

2. If $A,B\subseteq X$, then

   $$A\setminus B=A\cap B^{\mathrm{\complement }},{(A\setminus B)}^{\mathrm{\complement }}=A^{\mathrm{\complement }}\cup B,\text{and}\mathit{\hspace{1em}\hspace{1em}}{A}^{\mathrm{\complement }}\setminus B^{\mathrm{\complement }}=B\setminus A$$

   where ${}^{\mathrm{\complement }}$ denotes complement in $X$.

   Proof.

   For the first equation, see here (http://planetmath.org/PropertiesOfComplement). The second equation comes from the first: ${(A\setminus B)}^{\mathrm{\complement }}={(A\cap B^{\mathrm{\complement }})}^{\mathrm{\complement }}=(A^{\mathrm{\complement }})\cup {(B^{\mathrm{\complement }})}^{\mathrm{\complement }}=A^{\mathrm{\complement }}\cup B$. The last equation also follows from the first: $A^{\mathrm{\complement }}\setminus B^{\mathrm{\complement }}=A^{\mathrm{\complement }}\cap {(B^{\mathrm{\complement }})}^{\mathrm{\complement }}=B\cap A^{\mathrm{\complement }}=B\setminus A$. ∎

3. $A\subseteq B$ iff $A\setminus B=\mathrm{\varnothing }$.

   Proof.

   Since $A\subseteq B$, $B^{\mathrm{\complement }}\subseteq A^{\mathrm{\complement }}$. Then $A\setminus B=A\cap B^{\mathrm{\complement }}\subseteq A\cap A^{\mathrm{\complement }}=\mathrm{\varnothing }$. On the other hand, suppose $A\setminus B=\mathrm{\varnothing }$. Then $A\cap B^{\mathrm{\complement }}=\mathrm{\varnothing }$ by property 1, which means $A\subseteq {(B^{\mathrm{\complement }})}^{\mathrm{\complement }}=B$. ∎

4. $A\cap B=\mathrm{\varnothing }$ iff $A\setminus B=A$.

   Proof.

   Suppose first that $A\cap B=\mathrm{\varnothing }$. If $a\in A$, then $a\notin B$, so $a\in A\setminus B$, and hence $A\subseteq A\setminus B$. The equality is shown by applying property 1. Next suppose $A\setminus B=A$. If $a\in A$, then $a\in A\setminus B$, so $a\notin B$, which means $A\subseteq B^{\mathrm{\complement }}$, or $A\cap B=\mathrm{\varnothing }$. ∎

5. $A\setminus \mathrm{\varnothing }=A$ and $A\setminus A=\mathrm{\varnothing }=\mathrm{\varnothing }\setminus A$.

   Proof.

   The first equation follows from property 4 and the last two equations from property 3. ∎

6. (de Morgan’s laws on set difference):

   $$A\setminus (B\cap C)=(A\setminus B)\cup (A\setminus C)\mathit{\hspace{1em}\hspace{1em}}\text{ and }\mathit{\hspace{1em}\hspace{1em}}A\setminus (B\cup C)=(A\setminus B)\cap (A\setminus C).$$

   Proof.

   These laws follow from property 2 and the de Morgan’s laws on set complement. For example, $A\setminus (B\cap C)=(A\setminus B)\cup (A\setminus C)=A\cap {(B\cap C)}^{\mathrm{\complement }}=A\cap (B^{\mathrm{\complement }}\cup C^{\mathrm{\complement }})=(A\cap B^{\mathrm{\complement }})\cup (A\cap C^{\mathrm{\complement }})=(A\setminus B)\cup (A\setminus C)$. The other equation is proved similarly. ∎

7. $A\setminus (A\cap B)=A\setminus B=(A\cup B)\setminus B$.

   Proof.

   The first equation follows from property 6: $A\setminus (A\cap B)=(A\setminus A)\cup (A\setminus B)=A\setminus B$ by property 5. Next, $(A\cup B)\setminus B=(A\cup B)\cap B^{\mathrm{\complement }}=(A\cap B^{\mathrm{\complement }})\cup (B\cap B^{\mathrm{\complement }})=A\cap B^{\mathrm{\complement }}=A\setminus B$, proving the second equation. ∎

8. $(A\cap B)\setminus C=(A\setminus C)\cap (B\setminus C)$.

   Proof.

   Using property 2, we get $(A\cap B)\setminus C=(A\cap B)\cap C^{\mathrm{\complement }}=(A\cap C^{\mathrm{\complement }})\cap (B\cap C^{\mathrm{\complement }})=(A\setminus C)\cap (B\setminus C)$. ∎

9. $A\cap (B\setminus C)=(A\cap B)\setminus (A\cap C)$.

   Proof.

   $(A\cap B)\setminus (A\cap C)=(A\cap B)\cap {(A\cap C)}^{\mathrm{\complement }}=(A\cap B)\cap (A^{\mathrm{\complement }}\cup C^{\mathrm{\complement }})=((A\cap B)\cap A^{\mathrm{\complement }})\cup ((A\cap B)\cap C^{\mathrm{\complement }})=(A\cap B)\cap C^{\mathrm{\complement }}=A\cap (B\cap C^{\mathrm{\complement }})=A\cap (B\setminus C)$. ∎

10. $(A\setminus B)\cap (C\setminus D)=(C\setminus B)\cap (A\setminus D)$

    Proof.

    Expanding the LHS, we get $A\cap B^{\mathrm{\complement }}\cap C\cap D^{\mathrm{\complement }}$. Expanding the RHS, we get the same thing. ∎

11. $(A\setminus B)\cap (C\setminus D)=(A\cap C)\setminus (B\cup D)$.

    Proof.

    Starting from the RHS: $(A\cap C)\setminus (B\cup D)=((A\cap C)\setminus B)\cap ((A\cap C)\setminus D)=(A\setminus B)\cap (C\setminus B)\cap (A\setminus D)\cap (C\setminus D)=(A\setminus B)\cap (C\setminus D)$, where the last equality comes from property 10. ∎

Remarks.

1. Many of the proofs above use the properties of the set complement. Please see this link (http://planetmath.org/PropertiesOfComplement) for more detail.

2. All of the properties of $\setminus$ on sets can be generalized to Boolean subtraction (http://planetmath.org/DerivedBooleanOperations) on Boolean algebras.

Title	properties of set difference
Canonical name	PropertiesOfSetDifference
Date of creation	2013-03-22 17:55:35
Last modified on	2013-03-22 17:55:35
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	7
Author	CWoo (3771)
Entry type	Derivation
Classification	msc 03E20