Skip to main content
Engineering LibreTexts

3.2: 4.2 The Boolean Algebra of Sets

  • Page ID
    9680
  • It is clear that set theory is closely related to logic. The intersection and union of sets can be defined in terms of the logical ‘and’ and logical ‘or’ operators. The notation {x | P(x)} makes it possible to use predicates to specify sets. And if A is any set, then the formula x A defines a one place predicate that is true for an entity x if and only if x is a member of A. So it should not be a surprise that many of the rules of logic have analogues in set theory.

    For example, we have already noted that ∪ and ∩ are commutative operations. This fact can be verified using the rules of logic. Let A and B be sets. According to the definition of equality of sets, we can show that AB = BA by showing that ∀x((x A B) ↔ (x B A)). But for any x,

    x A B x A x B (definition of ∪)

    x B x A (commutativity of ∨)

    x B A (definition of ∪)

    The commutativity of ∩ follows in the same way from the definition of ∩ in terms of ∧and the commutativity of ∧, and a similar argument shows that union and intersection are associative operations.

    The distributive laws for propositional logic give rise to two similar rules in set theory. Let A, B, and C be any sets. Then

    A∪(BC) = (AB)∩(AC)

    and

    A∩(BC) = (AB)∪(AC)
    These rules are called the distributive laws for set theory. To verify the first of these laws, we just have to note that for any x,

    x A∪(BC)

    ↔ (x A) ∨ ((x B) ∧ (x C)) (definition of ∪, ∩)

    ↔ ((x A) ∨ (x B)) ∧ ((x A) ∨ (x C)) (distributivity of ∨)

    ↔ (x A B) ∧ (x A C) (definition of ∪)

    x ∈ ((A B) ∩ (A C)) (definition of ∩)

    The second distributive law for sets follows in exactly the same way.