Families of Sets

Families of Sets (Finite and Arbitrarily Indexed)


Master of Science in Mathematics
Lecture Notes. Accessed on: 2019-10-21 18:42:50

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.

5/5 (1 Review)

Leave a Comment

Scroll to Top