|
|
|
|
properties of set difference
|
(Derivation)
|
|
|
Let $A,B,C,D,X$ be sets.
- $A\setminus B\subseteq A$ . This is obvious by definition.
- If $A,B\subseteq X$ , then $$A\setminus B = A\cap B^\complement,\qquad (A\setminus B)^\complement = A^\complement \cup B,\qquad\mbox{and}\qquad A^\complement\setminus B^\complement = B\setminus A$$ where $^\complement$ denotes complement in $X$ .
Proof. For the first equation, see here. The second equation comes from the first: $(A\setminus B)^\complement=(A\cap B^\complement)^\complement = (A^\complement)\cup (B^\complement)^\complement = A^\complement \cup B$ . The last equation also follows from the first: $A^\complement\setminus B^\complement = A^\complement \cap (B^\complement)^\complement = B\cap A^\complement = B\setminus A$ . 
- $A\subseteq B$ iff $A\setminus B=\emptyset$ .
Proof. Since $A\subseteq B$ , $B^\complement \subseteq A^\complement$ . Then $A\setminus B= A\cap B^\complement \subseteq A\cap A^\complement=\emptyset$ . On the other hand, suppose $A\setminus B=\emptyset$ . Then $A\cap B^\complement = \emptyset$ by property 1, which means $A\subseteq (B^\complement)^\complement=B$ . 
- $A\cap B=\emptyset$ iff $A\setminus B=A$ .
Proof. Suppose first that $A\cap B=\emptyset$ . 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^\complement$ , or $A\cap B=\emptyset$ . 
- $A\setminus\emptyset = A$ and $A\setminus A = \emptyset = \emptyset\setminus A$ .
Proof. The first equation follows from property 4 and the last two equations from property 3. 
- (de Morgan's laws on set difference): $$A\setminus (B\cap C)=(A\setminus B)\cup (A\setminus C)\qquad \mbox{ and }\qquad 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)^\complement = A\cap (B^\complement \cup C^\complement) = (A\cap B^\complement) \cup (A\cap C^\complement) = (A\setminus B)\cup (A\setminus C)$ . The other equation is proved similarly. 
- $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^\complement = (A\cap B^\complement)\cup (B\cap B^\complement)= A\cap B^\complement =A\setminus B$ , proving the second equation. 
- $(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^\complement = (A\cap C^\complement)\cap (B\cap C^\complement) = (A\setminus C)\cap (B\setminus C)$ . 
- $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)^\complement = (A\cap B)\cap (A^\complement \cup C^\complement) = ((A\cap B)\cap A^\complement)\cup ((A\cap B)\cap C^\complement) = (A\cap B)\cap C^\complement = A\cap (B\cap C^\complement) = A\cap (B\setminus C)$ . 
- $(A\setminus B)\cap (C\setminus D) = (C\setminus B)\cap (A\setminus D)$
Proof. Expanding the LHS, we get $A\cap B^\complement \cap C \cap D^\complement$ . Expanding the RHS, we get the same thing. 
- $(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.
- Many of the proofs above use the properties of the set complement. Please see this link for more detail.
- All of the properties of $\setminus$ on sets can be generalized to Boolean subtraction on Boolean algebras.
|
"properties of set difference" is owned by CWoo.
|
|
(view preamble | get metadata)
Cross-references: Boolean algebras, proofs, set difference, de Morgan's laws, equality, property, iff, equation, complement, obvious
There is 1 reference to this entry.
This is version 4 of properties of set difference, born on 2008-03-19, modified 2008-04-29.
Object id is 10420, canonical name is PropertiesOfSetDifference.
Accessed 1143 times total.
Classification:
| AMS MSC: | 03E20 (Mathematical logic and foundations :: Set theory :: Other classical set theory ) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|