Suppose $I$ is a set, called the index set, and with each $i\in I$ we associate a set $A_i$. We call $\{A_i:i\in I\}$ an indexed family of sets. Sometimes this is denoted by $\{A_i\}_{i\in I}$.

Example 1.6.1 Suppose $I$ is the days of the year, and for each $i\in I$, $A_i$ is the set of people whose birthday is $i$, so, for example, $\hbox{Beethoven}\in A_{({\scriptsize\hbox{December 16}})}$. $\square$

Example 1.6.2 Suppose $I$ is the integers and for each $i\in I$, $A_i$ is the set of multiples of $i$, that is, $A_i=\{x\in \Z: i\vert x\}$ (recall that $i|x$ means that $x$ is a multiple of $i$; it is read "$i$ divides $x$''). $\square$

Given an indexed family $\{A_i:i\in I\}$ we can define the intersection and union of the sets $A_i$ using the universal and existential quantifiers: \eqalign{\bigcap_{i\in I} A_i & = \{ x: \forall i\in I\,(x\in A_i)\}\cr \bigcup_{i\in I} A_i & = \{ x: \exists i\in I\,(x\in A_i)\}.\cr}

Example 1.6.3 If $\{A_i:i\in I\}$ is the indexed family of example 1.6.1, then $\bigcap_{i\in I} A_i$ is the empty set and $\bigcup_{i\in I} A_i$ is the set of all people. If $\{A_i:i\in I\}$ is the indexed family of example 1.6.2, then $\bigcap_{i\in I} A_i$ is $\{0\}$ and $\bigcup_{i\in I} A_i$ is the set of all integers. $\square$

Since the intersection and union of an indexed family are essentially "translations'' of the universal and existential quantifiers, it should not be too surprising that there are De Morgan's laws that apply to these unions and intersections.

Theorem 1.6.4 If $\{A_i:i\in I\}$ is an indexed family of sets then

a) $(\bigcap_{i\in I} A_i)^c = \bigcup_{i\in I} A_i^c$,

b) $(\bigcup_{i\in I} A_i)^c = \bigcap_{i\in I} A_i^c$.

Proof. We'll do (a): $x\in (\bigcap_{i\in I} A_i)^c$ iff $\lnot (x\in \bigcap_{i\in I} A_i)$ iff $\lnot \forall i\,{\in}\, I\,(x\in A_i)$ iff $\exists i\,{\in}\, I\,(x\notin A_i)$ iff $\exists i\,{\in}\, I\,(x\in A_i^c)$ iff $x\in \bigcup_{i\in I} A_i^c$. $\qed$

You may be puzzled by the inclusion of this theorem: is it not simply part of theorem 1.5.6? No: theorem

Theorem 1.6.5 If $\{A_i:i\in I\}$ is an indexed family of sets and $B$ is any set, then

Proof. Part (a) is a case of specialization, that is, if $x\in \bigcap_{i\in I} A_i$, then $x\in A_i$ for all $i\in I$, in particular, when $i=j$. Part (d) also is easy—if $x\in \bigcup_{i\in I} A_i$, then for some $i\in I$, $x\in A_i\subseteq B$, so $x\in B$. Parts (b) and (c) are left as exercises. $\qed$

An indexed family $\{A_i:i\in I\}$ is pair-wise disjoint if $A_i\cap A_j=\emptyset$ whenever $i$ and $j$ are distinct elements of $I$. The indexed family of example 1.6.1 is pair-wise disjoint, but the one in example 1.6.2 is not. If $S$ is a set then an indexed family $\{A_i:i\in I\}$ of subsets of $S$ is a partition of $S$ if it is pair-wise disjoint and $S= \bigcup_{i\in I} A_i$. Partitions appear frequently in mathematics.

Example 1.6.6 Let $I=\{e,o\}$, $A_e$ be the set of even integers and $A_o$ be the set of odd integers. Then $\{A_i:i\in I\}$ is a partition of $S=\Z$. $\square$

Example 1.6.7 Let $I=\R$, $S=\R^2$, and for each $i\in I$, let $A_i=\{(x,i):x\in \R\}$. Each $A_i$ is a horizontal line and the indexed family partitions the plane. $\square$

Sometimes we want to discuss a collection of sets (that is, a set of sets) even though there is no natural index present. In this case we can use the collection itself as the index.

Example 1.6.8 If ${\cal S}=\{\{1,3,4\}, \{2,3,4,6\}, \{3,4,5,7\}\}$, then $\bigcap_{A\in {\cal S}}A =\{3,4\}$ and $\bigcup_{A\in {\cal S}}A =\{1,2,3,4,5,6,7\}$. $\square$

An especially useful collection of sets is the power set of a set: If $X$ is any set, the power set of $X$ is ${\cal P}(X)=\{A:A\subseteq X\}$.

Example 1.6.9 If $X=\{1,2\}$, then ${\cal P}(X)=\{\emptyset,\{1\},\{2\},\{1,2\}\}$. $\square$

Example 1.6.10 ${\cal P}(\emptyset)=\{\emptyset\}$, that is, the power set of the empty set is non-empty. $\square$

## Exercises 1.6

Ex 1.6.1 Let $I=\{1,2,3\}$, $A_1=\{1,3,4,6,7\}$ $A_2=\{1,4,5,7,8,9\}$, $A_3= \{2,4,7,10\}$. Find $\bigcap_{i\in I} A_i$ and $\bigcup_{i\in I} A_i$.

Ex 1.6.2 Suppose $I=[0,1]\subseteq \R$ and for each $i\in I$, let $A_i=(i-1,i+1)\subseteq \R$. Find $\bigcap_{i\in I} A_i$ and $\bigcup_{i\in I} A_i$.

Ex 1.6.3 Prove parts (b) and (c) of theorem 1.6.5.

Ex 1.6.4 Suppose $U$ is the universe of discourse and the index set $I=\emptyset$. What should we mean by $\bigcap_{i\in I} A_i$ and $\bigcup_{i\in I} A_i$? Show that Theorem 1.6.4 still holds using your definitions.

Ex 1.6.5 Suppose $\{A_i\}_{i\in I}$ is a partition of a set $S$. If $T\subseteq S$, show that $\{A_i\cap T\}_{i\in I}$ is a partition of $T$.

Ex 1.6.6 A collection of sets, $\cal S$, is totally ordered if for every $A,B\in {\cal S}$, either $A\subseteq B$ or $B\subseteq A$. If $\cal S$ is totally ordered, show that ${\cal S}^c=\{A^c: A\in {\cal S}\}$ is totally ordered.

Ex 1.6.7 Suppose $\cal S$ is a collection of sets and $B$ is some other set. Show that if $B$ is disjoint from every $A\in {\cal S}$ then $B$ is disjoint from $\bigcup_{A\in {\cal S}} A$.