Algebra of Sets

Overview

The algebra of sets concerns itself with the operations of union ( $\cup$ ), intersection ( $\cap$ ), and set difference ( $-$ ), together with the inclusion relation ( $\subseteq$ ).

Union

The union of two sets, say $A$ and $B$ , is defined as

A \cup B = {x ∣ x \in A \lor x \in B} .

More generally, let ${A_{i} ∣ i \in I}$ be an indexed family of sets. Then the union of this famliy is given by

⋃_{i \in I} A_{i} = {x ∣ \exists i \in I, x \in A_{i}} .

The union axioms assert the union's existence.

Disjoint Union

The disjoint union of two sets, say $A$ and $B$ , is defined as

A ⊔ B = {⟨ x, 0 ⟩ ∣ x \in A} \cup {⟨ x, 1 ⟩ ∣ x \in B} .

More generally, let ${A_{i} ∣ i \in I}$ be an indexed family of sets. Then the disjoint union of this family is given by

⨆_{i \in I} A_{i} = ⋃_{i \in I} {⟨ x, i ⟩ ∣ x \in A_{i}} .

Intersection

The intersection of two sets, say $A$ and $B$ , is defined as

A \cap B = {x ∣ x \in A \land x \in B} .

More generally, let ${A_{i} ∣ i \in I}$ be a nonempty indexed family of sets. Then the intersection of this family is given by

⋂_{i \in I} A_{i} = {x ∣ \forall i \in I, x \in A_{i}} .

The subset axioms asserts the intersection's existence.

Symmetric Difference

The symmetric difference of two sets, say $A$ and $B$ , is defined as

A △ B = (A - B) \cup (B - A)

Cartesian Product

The Cartesian product of two sets, say $A$ and $B$ , is defined as

A \times B = {⟨ x, y ⟩ ∣ x \in A \land y \in B} .

The Cartesian square of a set $A$ is the Cartesian product $A^{2} = A \times A$ . The $n$ -ary Cartesian power of a set $A$ , denoted $A^{n}$ , is defined as

\begin{aligned} A^{n} & = A \times A \times \dots \times A \\ = {⟨ a_{1}, \dots, a_{n} ⟩ ∣ a_{i} \in A for every i \in {1, \dots, n}} . \end{aligned}

As a special case, the $0$ -ary Cartesian power, denoted $A^{0}$ , is defined as the singleton set containing the empty function (with codomain $A$ ).

Properties

Commutativity

Union and intersection are commutative operations. That is, for any sets $A$ and $B$ ,

\begin{aligned} A \cup B & = B \cup A \\ A \cap B & = B \cap A \end{aligned}

Associativity

Union and intersection are associative operations. That is, for any sets $A$ and $B$ ,

\begin{aligned} A \cup (B \cup C) & = (A \cup B) \cup C \\ A \cap (B \cap C) & = (A \cap B) \cap C \end{aligned}

Distributivity

For any sets $A$ , $B$ , and $C$ ,

\begin{aligned} A \cap (B \cup C) & = (A \cap B) \cup (A \cap C) \\ A \cup (B \cap C) & = (A \cup B) \cap (A \cup C) \\ A \times (B \cap C) & = (A \times B) \cap (A \times C) \\ A \times (B \cup C) & = (A \times B) \cup (A \times C) \\ A \times (B - C) & = (A \times B) - (A \times C) \end{aligned}

More generally, for any sets $A$ and $B$ ,

\begin{aligned} A \cup ⋂ B & = ⋂ {A \cup X ∣ X \in B}, where B \neq \emptyset \\ A \cap ⋃ B & = ⋃ {A \cap X ∣ X \in B} \\ A \times ⋃ B & = ⋃ {A \times X ∣ X \in B} \\ A \times ⋂ B & = ⋂ {A \times X ∣ X \in B} \end{aligned}

De Morgan's Laws

For any sets $A$ , $B$ , and $C$ ,

\begin{aligned} C - (A \cup B) & = (C - A) \cap (C - B) \\ C - (A \cap B) & = (C - A) \cup (C - B) \end{aligned}

More generally, for any sets $C$ and $A \neq \emptyset$ ,

\begin{aligned} C - ⋃ A & = ⋂ {C - X ∣ X \in A} \\ C - ⋂ A & = ⋃ {C - X ∣ X \in A} \end{aligned}

Monotonicity

Let $A$ , $B$ , and $C$ be arbitrary sets. Then

$A \subseteq B ⟹ A \cup C \subseteq B \cup C$ ,
$A \subseteq B ⟹ A \cap C \subseteq B \cap C$ ,
$A \subseteq B ⟹ ⋃ A \subseteq ⋃ B$
$A \subseteq B ⟹ A \times C \subseteq B \times C$

Antimonotonicity

Let $A$ , $B$ , and $C$ be arbitrary sets. Then

$A \subseteq B ⟹ C - B \subseteq C - A$ ,
$\emptyset \neq A \subseteq B ⟹ ⋂ B \subseteq ⋂ A$

Cancellation

Let $A$ , $B$ , and $C$ be sets. If $A \neq \emptyset$ ,

$(A \times B = A \times C) ⟹ B = C$
$(B \times A = C \times A) ⟹ B = C$