properties of set difference
Let be sets.
- 1.
. This is obvious by definition.
- 2.
If , then
where denotes complement
in .
Proof.
For the first equation, see here (http://planetmath.org/PropertiesOfComplement). The second equation comes from the first: . The last equation also follows from the first: .∎
- 3.
iff .
Proof.
Since , . Then . On the other hand, suppose . Then by property 1, which means .∎
- 4.
iff .
Proof.
Suppose first that . If , then , so , and hence . The equality is shown by applying property 1. Next suppose . If , then , so , which means , or .∎
- 5.
and .
Proof.
The first equation follows from property 4 and the last two equations from property 3.∎
- 6.
(de Morgan’s laws on set difference
):
Proof.
These laws follow from property 2 and the de Morgan’s laws on set complement. For example, . The other equation is proved similarly.∎
- 7.
.
Proof.
The first equation follows from property 6: by property 5. Next, , proving the second equation.∎
- 8.
.
Proof.
Using property 2, we get .∎
- 9.
.
Proof.
.∎
- 10.
Proof.
Expanding the LHS, we get . Expanding the RHS, we get the same thing.∎
- 11.
.
Proof.
Starting from the RHS: , 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 on sets can be generalized to Boolean subtraction (http://planetmath.org/DerivedBooleanOperations) on Boolean algebras
.