Skip to main content
Engineering LibreTexts

3.2: 4.2 The Boolean Algebra of Sets

  • Page ID
    9680
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    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.


    3.2: 4.2 The Boolean Algebra of Sets is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Stefan Hugtenburg & Neil Yorke-Smith.

    • Was this article helpful?