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 1.5.6 (parts (e) and (f)) concerns the intersection or union of two sets only. This can be extended easily to any intersection or union of a finite number of sets, though even this modest extension does require separate proof. The real problem is with intersections or unions of an infinite number of sets. Though in this case the extension to infinite operations has an easy proof, it is not always the case that what is true for a finite number of operations is true for an infinite number of operations, and even when true, the proof in the infinite case may be more difficult.
The relationships in the following theorem are simple but useful; they illustrate the dual nature of the union and intersection of families of sets.
Theorem 1.6.5 If $\{A_i:i\in I\}$ is an indexed family of sets and $B$ is any set, then
a) $\bigcap_{i\in I} A_i\subseteq A_j$, for each $j\in I$,
b) $A_j\subseteq \bigcup_{i\in I} A_i$, for each $j\in I$.
c) if $B\subseteq A_i$, for all $i\in I$, then $B\subseteq \bigcap_{i\in I} A_i$,
d) if $A_i\subseteq B$, for all $i\in I$, then $\bigcup_{i\in I} A_i\subseteq B$.
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$.