Set Algebra

Overview

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

Symmetric Difference

Define the symmetric difference of sets $A$ and $B$ as $$A \vartriangle B = (A - B) \cup (B - A)$$

Cartesian Product

Given two sets $A$ and $B$, the Cartesian product $A\times B$ is defined as: $$A \times B = {\langle x, y \rangle \mid 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{align*} A^n & = A \times A \times \cdots \times A \ & = { \langle a_1, \ldots, a_n \rangle \mid a_i \in A \text{ for every } i \in {1, \ldots, n }}. \end{align*}$$

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

We can also form (something like) the Cartesian product of infinitely many sets, provided that the sets are suitably indexed. Let $I$ be an index set and $H$ a function whose domain includes $I$. Define $$\bigtimes_{i \in I} H(i) = {f \mid f \text{ is a function with domain } I \text{ and } \forall i \in I, f(i) \in H(i)}$$

Laws

Commutative Laws

For any sets $A$ and $B$, $$\begin{align*} A \cup B & = B \cup A \ A \cap B & = B \cap A \end{align*}$$

Associative Laws

For any sets $A$ and $B$, $$\begin{align*} A \cup (B \cup C) & = (A \cup B) \cup C \ A \cap (B \cap C) & = (A \cap B) \cap C \end{align*}$$

Distributive Laws

For any sets $A$, $B$, and $C$, $$\begin{align*} A \cap (B \cup C) & = (A \cap B) \cup (A \cap C) \ A \cup (B \cap C) & = (A \cup B) \cap (A \cup C) \end{align*}$$

More generally, for any sets $A$ and $\mathcal{B}$, $$\begin{align*} A \cup \bigcap \mathscr{B} & = \bigcap, {A \cup X \mid X \in \mathscr{B}}, \text{ for } \mathscr{B} \neq \varnothing \ A \cap \bigcup \mathscr{B} & = \bigcup, {A \cap X \mid X \in \mathscr{B}} \end{align*}$$

For any sets $A$, $B$, and $C$, $$\begin{align*} 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{align*}$$

In addition, $$\begin{align*} A \times \bigcup \mathscr{B} & = \bigcup, {A \times X \mid X \in \mathscr{B}} \ A \times \bigcap \mathscr{B} & = \bigcap, {A \times X \mid X \in \mathscr{B}} \end{align*}$$

De Morgan's Laws

For any sets $A$, $B$, and $C$, $$\begin{align*} C - (A \cup B) & = (C - A) \cap (C - B) \ C - (A \cap B) & = (C - A) \cup (C - B) \end{align*}$$

More generally, for any sets $C$ and $\mathcal{A}\ne \varnothing$, $$\begin{align*} C - \bigcup \mathscr{A} & = \bigcap, {C - X \mid X \in \mathscr{A}} \ C - \bigcap \mathscr{A} & = \bigcup, {C - X \mid X \in \mathscr{A}} \end{align*}$$

Monotonicity

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

• $A\subseteq B\Rightarrow A\cup C\subseteq B\cup C$,
• $A\subseteq B\Rightarrow A\cap C\subseteq B\cap C$,
• $A\subseteq B\Rightarrow \bigcup A\subseteq \bigcup B$
• $A\subseteq B\Rightarrow A\times C\subseteq B\times C$

Antimonotonicity

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

• $A\subseteq B\Rightarrow C-B\subseteq C-A$,
• $\varnothing \ne A\subseteq B\Rightarrow \bigcap B\subseteq \bigcap A$

Cancellation Laws

Let $A$, $B$, and $C$ be sets. If $A\ne \varnothing$,

• $(A\times B=A\times C)\Rightarrow B=C$
• $(B\times A=C\times A)\Rightarrow B=C$

Index Sets

Let $I$ be a set, called the index set. Let $F$ be a function whose domain includes $I$. Then we define $$\bigcup_{i \in I} F(i) = \bigcup,{F(i) \mid i \in I}$$
and, if $I\ne \varnothing$, $$\bigcap_{i \in I} F(i) = \bigcap, {F(i) \mid i \in I}$$

Function Sets

For sets $A$ and $B$, the collection of functions $F$ from $A$ into $B$ is: $$^AB = {F \mid F \colon A \rightarrow B}$$
${}^{A}B$ is read as "$B$-pre-$A$". It is often written as $B^A$ instead.

Bibliography

• “Cartesian Product,” in Wikipedia, April 17, 2024, https://en.wikipedia.org/w/index.php?title=Cartesian_product.
• Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).