Families of Sets (Finite and Arbitrarily Indexed)

Direct Knowlege Contributor David A. Smith
  • By David A. Smith, Founder & CEO, Direct Knowledge
  • David Smith has a B.S. and M.S. in Mathematics and has enjoyed teaching calculus, linear algebra, and number theory at both Tarrant County College and the University of Texas at Arlington. David is the Founder and current CEO of Direct Knowledge.

Families of Sets

Finite Unions and Intersections

Given any $n$ sets $A_1, A_2, \ldots, A_n$, we define their union to be the set $$A_1 \cup A_2 \cup \cdots \cup A_n =\{x\mid x\in A_i \text{ for some } i, 1\leq i \leq n\}. $$ and their intersection to the the set  $$ A_1 \cap A_2 \cap \cdots \cap A_n =\{x\mid x\in A_i \text{ for all } i, 1\leq i \leq n\}.$$ These sets can be written as $$ \bigcup_{i=1}^n A_i  \qquad \text{and}\qquad \bigcap_{i=1}^n A_i  $$ respectively. 

Example. For $i\in \{1,2,3,\ldots, 10\}$, define  $$A_i=[-i,10-i].$$ Find $A_1$, $A_2, \ldots, A_{10}$ and then find $\bigcup_{i=1}^{10} A_i$ and $\bigcap_{i=1}^{10} A_i$.

Proof. We find  $$ A_1=[-1,9], \quad  A_2=[-2,8], \quad \ldots, \quad  A_{10}=[-10,0].  $$ Hence \begin{equation} \bigcup_{i=1}^{10} A_i=[-10,9] \qquad  \text{and} \qquad  \bigcap_{i=1}^{10} A_i=[-1,0]. \end{equation}

Example. For $k\in \{1,2,\ldots, 100\}$, define $$ B_k=\{r\in \mathbb{Q} \mid -1\leq k \cdot r \leq 1\}. $$ Find $B_k$ for $1\leq k\leq 100$, compare these sets, and then find $\bigcup_{k=1}^{100} B_k$ and $\bigcap_{k=1}^{100} B_k$.

Proof. We find  \begin{alignat*}{2} & B_1=\{r\in \mathbb{Q} \mid -1 \leq r \leq 1\},  & \qquad & B_2=\left\{\{r\in \mathbb{Q} \mid -\frac{1}{2} \leq r \leq \frac{1}{2}\right\},  \\ & \qquad \cdots \qquad \cdots  & & B_{100}=\left\{r\in \mathbb{Q} \mid -\frac{1}{100} \leq r \leq \frac{1}{100}\right\}, \end{alignat*} and so  $$ B_{100}\subseteq B_{99} \subseteq B_{98} \subseteq \cdots \subseteq B_2 \subseteq B_1. $$ It follows that  \begin{equation*} \bigcup_{k=1}^{100} B_k=B_1 \qquad \text{and} \qquad  \bigcap_{k=1}^{100} B_k=B_{100}.  \end{equation*}

Families of Sets

Indexed Sets

Let $I$ be a nonempty set, and suppose that for each element $i\in I$ there is associated a set $A_i$. We then call $I$ an index set for the collection of sets $\mathcal{A}=\{A_i \mid i\in I\}$.

Definition. Let $I$ be an indexed set and suppose that $\mathcal{A}=\{A_i\mid i\in I\}$ is a collection of sets. Then

the union of the collection $\mathcal{A}$ is defined to be the set  $$ \bigcup_{i\in I} A_i  =\{x\mid x\in A_i \text{ for some } i\in I\},  $$

the intersection of the collection $\mathcal{A}$ is defined to be the set  $$ \bigcap_{i\in I} A_i  =\{x\mid x\in A_i \text{ for each } i\in I\}. $$

Theorem. Given the collection of sets $\{A_i \mid i\in \mathbb{N}\}$ the following properties hold. 

$\quad (1)$ If $A_i \subseteq A_{i+1}$ for all $i\in \mathbb{N}$, then $\bigcap_{i=1}A_i=A_1$. 

$\quad (2)$ If $A_i \supseteq A_{i+1}$ for all $i\in \mathbb{N}$, then $\bigcup_{i=1}A_i=A_1$.

Proof. We prove first and leave second for the reader as an exercise. Let $T=\cap_{i=1}A_i=A_0$ and let $x$ be an arbitrary element of $T$. Then $x\in A_i$ for each $i\in \mathbb{N}$, and this certainly implies that $x\in A_1$. So $T\in A_1$. Conversely, assume $x\in A_1$.  Since $A_i \subseteq A_{i+1}$ for all $i\in \mathbb{N}$, we have that $A_1\subseteq A_i$ for every $i\in \mathbb{N}$, and hence $x\in T$. This shows that $A_1\subseteq T$; hence we conclude that $T=A_1$.

Example. Let $n\in \mathbb{N}$ and let  $$ A_n=\{m\in \mathbb{Z} \mid -n \leq m \land 2^m\leq n\}. $$ Use \cref{thm:ardntuni} to find $\bigcap_{i=1}^{\infty} A_i$ and $\bigcup_{i=1}^{\infty} A_i$.

Proof. We find \begin{align*} A_1=\{-1,0\},  \qquad A_2=\{-2,-1,0,1\}, \end{align*} \begin{align*} A_3=\{-3,-2,-1,0,1\},  \qquad A_4=\{-3,-2,-1,0,1,2\}  \end{align*} and so on.  Note that $A_1\subseteq A_2 \subseteq A_3 \subseteq \cdots$. Hence we have $$\bigcap_{n=1}^\infty A_n=A_1 $$ The reader should verify that \begin{equation*} \label{intexa} \bigcup_{n=1}^\infty A_n=\mathbb{Z}. \end{equation*}

Example. Let $I=(0,1)$, and for $i\in I$, define $A_i=(-i,i)$. Find $\bigcap_{i\in I} A_i$ and $\bigcup_{i\in I} A_i$.

Proof. For example,  $$ A_{1/2}=\left(-\frac{1}{2},\frac{1}{2}\right) \qquad \text{and}\qquad A_{\sqrt{2}/3}=\left(-\frac{\sqrt{2}}{3},\frac{\sqrt{2}}{3}\right). $$ Notice that if $0<i<j<1$, then $\{0\}\subset A_i \subset A_j \subset (-1,1)$. It follows that  \begin{equation*} \label{intexatwo} \bigcup_{i\in I} A_i =(-1,1) \qquad \text{and} \qquad  \bigcap_{i\in I} A_i =\{0\} \end{equation*}

Theorem. Let $\{A_i \mid i\in I\}$ be a collection of sets indexed by $I$. Then

$\quad (1)$ $\left(\bigcup_{i\in I} A_i\right)’ =\bigcap_{i\in I} A_i’$

$\quad (2)$ $\left(\bigcap_{i\in I} A_i\right)’ =\bigcup_{i\in I} A_i’$

Proof. We prove the first and leave second for the reader as an exercise. Let $x$ be an arbitrary element in $\left(\cup_{i\in I} A_i\right)’$.  Then  \begin{alignat*}{2} & x\in \left(\cup_{i\in I} A_i\right)’ & \qquad & \\ & \quad \rightarrow [x\notin \cup_{i\in I} A_i] & &  \text{by Definition of complement} \\ & \quad \rightarrow [\neg(x\in \cup_{i\in I} A_i)] & &  \text{by Definition of $\notin$} \\ & \quad \rightarrow [\neg(\exists i\in I, x\in A_i)] & &  \text{by Definition of $\cup$} \\ & \quad \rightarrow [\forall i\in I, x\notin A_i] & &  \text{by logic rule} \\ & \quad \rightarrow [\forall i\in I, x\in A_i’] & &  \text{by Definition of complement} \\ & \quad \rightarrow [x\in \cap_{i\in I} A_i’] & &  \text{by Definition of $\cap$} \end{alignat*} Thus $x\in \cap_{i\in I} A_i’$ and consequently $\left(\cup_{i\in I} A_i\right)’ \subseteq x\in \cap_{i\in I} A_i’.$ In a similar fashion (simply reverse the implications) one may prove the reverse containment. Therefore, we conclude $\left(\cup_{i\in I} A_i\right)’ = \cap_{i\in I} A_i’.$ as desired.