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