Andrew Cooper

Finite Set Operations

The operations $\cup$ and $\cap$ apply to two sets; we can however use them to combine more than one set. If we have a finite collection of sets $A_1,A_2,\ldots,A_N$, we write

\begin{equation}\begin{aligned}\bigcup_{i=1}^N A_i&=A_1\cup A_2\cup \cdots\cup A_N\\\bigcap_{i=1}^N A_i&=A_1\cap A_2\cap \cdots\cap A_N\end{aligned}\end{equation}

Activity. Give a better definition of $\displaystyle\bigcup_{i=1}^NA_i$ and $\displaystyle\bigcap_{i=1}^NA_i$ . (Hint. What did we say about definitions involving $\cdots$?)

De Morgan’s Laws. For any finite collection of sets $A_1,\ldots, A_n$,

\begin{align*}\left(\bigcup_{i=1}^N A_i\right)^c=&\bigcap_{i=1}^NA_i^c\\\left(\bigcap_{i=1}^N A_i\right)^c=&\bigcup_{i=1}^NA_i^c \end{align*}

Exercise. Prove this version of de Morgan’s Laws.

Transfinite Operations

There is no reason to restrict our attention to {\em finite} collections of sets. For example, we might consider

the collection of intervals of the form $[n,n+1]$, where $n$ is allowed to be an natural number,

or perhaps

the set of all disks centered at the origin

each of which consists of an infinite number of sets. We usually use set-builder notation to write something like

\begin{equation}\left\{[n,n+1]\middle\vert n\in\mathbb{N}\right\}\end{equation}

or

\begin{equation}\left\{D_r\middle\vert r\in(0,\infty) \right\}\end{equation}

to emphasize that what we are dealing with is a(n infinite) set of sets. (Here we have written $D_r=\left\{(x,y)\middle\vert x^2+y^2<r^2\right\}$ for the disk of radius $r$ centered at the origin.) We call the set to the right of the pipe the index set: in these collections  the index sets are $\mathbb{N}$ and the interval $(0,\infty)$, respectively.

We can define unions and intersections of such infinite collections of sets by recalling that $\exists$ acts like a souped-up version of $\vee$ and $\forall$ acts like a souped-up version of $\wedge$.

Given a collection of sets $\mathcal{A}=\left\{A_\lambda\middle\vert \lambda\in\Lambda\right\}$, we set

Definition. \begin{align*}\bigcup\mathcal{A}&=\bigcup_{\lambda\in\Lambda}A_\lambda=\left\{x\middle\vert \exists\lambda\in\Lambda:x\in A_\lambda\right\}\\\bigcap\mathcal{A}&=\bigcap_{\lambda\in\Lambda}A_\lambda=\left\{x\middle\vert \forall\lambda\in\Lambda,x\in A_\lambda\right\}\end{align*}

E.g. $\displaystyle\bigcup_{n\in\mathbb{N}} [n,n+1]=[1,\infty)$

Proof. Let $x\in[1,\infty)$. Then there is some $n\in\mathbb{N}$ with $n\leq x\leq n+1$, so $x\in[n,n+1]$. Thus $\displaystyle x\in\bigcup_{n\in\mathbb{N}} [n,n+1]$.

Now let $\displaystyle x\in\bigcup_{n\in\mathbb{N}} [n,n+1]$. Then there is some $n\in\mathbb{N}$ with $x\in[n,n+1]$. But $[n,n+1]\subseteq [1,\infty)$, so $x\in[1,\infty)$. $\Box$

E.g. $\displaystyle\bigcap_{r\in(0,\infty)} D_r=\{(0,0)\}$

Proof. Certainly the origin $(0,0)$ is in each disk $D_r$. We will show it is the only such point.

Consider any point $(x,y)$ in the plane. Let $r_1=\sqrt{x^2+y^2}$ be the distance between $(x,y)$ and the origin. Then if we select $r=\frac{1}{2}r_1$, we see that $(x,y)\notin D_r$. Thus $(x,y)$ cannot be in every $D_r$.

de Morgan’s Laws. For any collection $\{A_\lambda|\lambda\in\Lambda\}$, we have \begin{align*}\left(\bigcup_{\lambda\in\Lambda} A_\lambda\right)^c=&\bigcap_{\lambda\in\Lambda}A_\lambda^c\\ \left(\bigcap_{\lambda\in\Lambda} A_\lambda\right)^c=&\bigcup_{\lambda\in\Lambda}A_\lambda^c \end{align*}

Exercise. Prove this version of de Morgan’s Laws.

Exercise. What is each of the following sets?

1. $\displaystyle\bigcap_{n\in\mathbb{N}} [n,n+1]$
2. $\displaystyle\bigcup_{r\in(0,\infty)} D_r$
3. $\displaystyle\bigcup_{n\in\mathbb{N}}\left[\frac{1}{n},1\right]$
4. $\displaystyle\bigcap_{n\in\mathbb{N}}\left[\frac{1}{n},1\right]$

Exercise Express each set below as either a generalized union or a generalized intersection, and also express it in set-builder notation.

1. $\displaystyle B\setminus\left(\bigcap_{\lambda\in\Lambda} A_\lambda\right)$
2. $\displaystyle B\setminus\left(\bigcup_{\lambda\in\Lambda} A_\lambda\right)$
3. $\displaystyle \left(\bigcap_{\lambda\in\Lambda} A_\lambda\right)\setminus B$
4. $\displaystyle \left(\bigcup_{\lambda\in\Lambda} A_\lambda\right)\setminus B$