# 3.2: 4.2 The Boolean Algebra of Sets

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\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 \|}$$ $$\newcommand{\inner}{\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 \|}$$ $$\newcommand{\inner}{\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 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.

This page titled 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 (TU Delft Open) .