properties of set difference


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

  1. 1.

    ABA. This is obvious by definition.

  2. 2.

    If A,BX, then

    AB=AB,(AB)=AB,and  AB=BA

    where denotes complementPlanetmathPlanetmath in X.

    Proof.

    For the first equation, see here (http://planetmath.org/PropertiesOfComplement). The second equation comes from the first: (AB)=(AB)=(A)(B)=AB. The last equation also follows from the first: AB=A(B)=BA=BA. ∎

  3. 3.

    AB iff AB=.

    Proof.

    Since AB, BA. Then AB=ABAA=. On the other hand, suppose AB=. Then AB= by property 1, which means A(B)=B. ∎

  4. 4.

    AB= iff AB=A.

    Proof.

    Suppose first that AB=. If aA, then aB, so aAB, and hence AAB. The equality is shown by applying property 1. Next suppose AB=A. If aA, then aAB, so aB, which means AB, or AB=. ∎

  5. 5.

    A=A and AA==A.

    Proof.

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

  6. 6.

    (de Morgan’s laws on set differenceMathworldPlanetmath):

    A(BC)=(AB)(AC)   and   A(BC)=(AB)(AC).
    Proof.

    These laws follow from property 2 and the de Morgan’s laws on set complement. For example, A(BC)=(AB)(AC)=A(BC)=A(BC)=(AB)(AC)=(AB)(AC). The other equation is proved similarly. ∎

  7. 7.

    A(AB)=AB=(AB)B.

    Proof.

    The first equation follows from property 6: A(AB)=(AA)(AB)=AB by property 5. Next, (AB)B=(AB)B=(AB)(BB)=AB=AB, proving the second equation. ∎

  8. 8.

    (AB)C=(AC)(BC).

    Proof.

    Using property 2, we get (AB)C=(AB)C=(AC)(BC)=(AC)(BC). ∎

  9. 9.

    A(BC)=(AB)(AC).

    Proof.

    (AB)(AC)=(AB)(AC)=(AB)(AC)=((AB)A)((AB)C)=(AB)C=A(BC)=A(BC). ∎

  10. 10.

    (AB)(CD)=(CB)(AD)

    Proof.

    Expanding the LHS, we get ABCD. Expanding the RHS, we get the same thing. ∎

  11. 11.

    (AB)(CD)=(AC)(BD).

    Proof.

    Starting from the RHS: (AC)(BD)=((AC)B)((AC)D)=(AB)(CB)(AD)(CD)=(AB)(CD), where the last equality comes from property 10. ∎

Remarks.

  1. 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. 2.

    All of the properties of on sets can be generalized to Boolean subtraction (http://planetmath.org/DerivedBooleanOperations) on Boolean algebrasMathworldPlanetmath.

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