PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] properties of set difference (Derivation)

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^\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$ . $ \qedsymbol$
  3. $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$ . $ \qedsymbol$
  4. $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$ . $ \qedsymbol$
  5. $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. $ \qedsymbol$
  6. (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. $ \qedsymbol$
  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^\complement = (A\cap B^\complement)\cup (B\cap B^\complement)= A\cap B^\complement =A\setminus B$ , proving the second equation. $ \qedsymbol$
  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^\complement = (A\cap C^\complement)\cap (B\cap C^\complement) = (A\setminus C)\cap (B\setminus C)$ . $ \qedsymbol$
  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)^\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)$ . $ \qedsymbol$
  10. $(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. $ \qedsymbol$
  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. $ \qedsymbol$

Remarks.

  1. Many of the proofs above use the properties of the set complement. Please see this link for more detail.
  2. 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)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

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 MSC03E20 (Mathematical logic and foundations :: Set theory :: Other classical set theory )

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)