3.2: 4.2 The Boolean Algebra of Sets

Last updated
Save as PDF

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}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

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 A∪B = B∪A 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∪(B∩C) = (A∪B)∩(A∪C)

and

A∩(B∪C) = (A∩B)∪(A∩C)
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∪(B∩C)

↔ (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.