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$.