Skip to main content

Section 5.9 The algebra of subsets

The algebra of subsets of a set permits one to perform unions, intersections, and complements, and these satisfy certain rules.

So let \(X\) be a set, and let \(U\colon\fromto{A}{\PP(X)}\) be a map. Then there are two new subsets of \(X\) that can be constructed: the indexed union

\begin{equation*} \bigcup_{a\in A}U(a)\coloneq\{x\in X : (\exists a\in A)\ x\in U(a)\} \end{equation*}

and the indexed intersection

\begin{equation*} \bigcap_{a\in A}U(a)\coloneq\{x\in X : (\forall a\in A)\ x\in U(a)\}\text{.} \end{equation*}

There is only one map \(I\colon \varnothing \PP(X)\text{.}\) The indexed union

\begin{equation*} \bigcup_{a \in \varnothing} I(a) = \varnothing\text{.} \end{equation*}

The indexed intersection

\begin{equation*} \bigcap_{a \in \varnothing} I(a) = X\text{.} \end{equation*}

Let's see what happens when you repeat these operations or mix them. Let \(A\) and \(B\) be sets, and let \(U \colon A \times B \to \PP(X)\text{.}\) We're going to exploit some bijections now: we know that maps \(A \times B \to \PP(X)\) are in bijection with maps \(A \to \Map(B, \PP(X))\text{;}\) we also know that \(A \times B\) is in bijection with \(B \times A\text{,}\) and therefore that maps \(A \times B \to \PP(X)\) are in bijection with maps \(B \times A \to \PP(X)\text{,}\) which are in turn in bijection with maps \(B \to \Map(A, \PP(X))\text{.}\) Here are the formulas:

\begin{align*} \bigcup_{a\in A} \bigcup{b \in B} U(a,b) \amp = \bigcup_{b \in B} \bigcup{a \in A} U(a,b) ;\\ \bigcap_{a\in A} \bigcap{b \in B} U(a,b) \amp = \bigcap_{b \in B} \bigcap{a \in A} U(a,b) ;\\ \bigcap_{a\in A}\bigcup_{b\in B} U(a,b) \amp = \bigcup_{f\in\Map(A,B)} \bigcap_{a\in A} U(a,f(a)) ;\\ \bigcup_{a\in A} \bigcap_{b\in B} U(a,b) \amp = \bigcap_{f\in\Map(A,B)} \bigcup_{a\in A} U(a,f(a)) \text{.} \end{align*}

There is also the complement of any \(A\in\PP(X)\)

\begin{equation*} \complement A = X \smallsetminus A \coloneq \{x\in X : x\notin A)\}\text{.} \end{equation*}

The de Morgan laws state that the formation of the complement exchanges union and intersection: for any map \(U\colon\fromto{A}{\PP(X)}\text{,}\)

\begin{align*} \complement\left(\bigcup_{a\in A}U(a)\right) \amp = \bigcap_{a\in A}\complement U(a);\\ \complement\left(\bigcap_{a\in A}U(a)\right) \amp =\bigcup_{a\in A}\complement U(a) \text{.} \end{align*}