PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (210)
Orphanage
Unclass'd (1)
Unproven (473)
Corrections (37)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
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
    $\displaystyle A\setminus B = A\cap B^\complement,\qquad (A\setminus B)^\complement = A^\complement \cup B,$   and$\displaystyle \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):
    $\displaystyle A\setminus (B\cap C)=(A\setminus B)\cup (A\setminus C)$    and $\displaystyle \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)^\comp... ...p 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)... ...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)... ...inus 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)

View style:


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

Cross-references: Boolean algebras, 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 146 times total.

Classification:
AMS MSC: 03E20 (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)