3.3. Indexed families of sets

This section is meant to be used as a reference, rather than as lecture content. You may cite results from here for your problem sets or tests, but it is not expected you know all of this specifically.

Union and intersection

Notation.

Let $X$ be a set. The union of $X$, denoted $\bigcup X$ is the set

$$\{x:\exists A\in X,x\in A\}.$$

If $X$ is nonempty, the intersection $\bigcap X$ is the set

$$\{x:\forall A\in X,x\in A\}.$$

You are likely familiar with the following particular cases of union and intersection.

Example.

1. If $X=\{A,B\}$, then $\bigcup X=A\cup B$ and $\bigcap X=A\cap B$.
2. If $X=\{A_0,A_1,\dots ,A_n\}$, then

$$\bigcup X=\bigcup _{i\le n}{A}_i\text{ and }\bigcap X=\bigcap _{i\le n}{A}_i.$$

I am in need of more general notation. An indexed family of sets is a set of the form $\mathcal{F}=\{x_{\alpha }:\alpha \in I\}$. $I$ is called the indexing set, and $\alpha$ is called the index.

The intersection and union over indexed families is treated the same way as above.

$$\bigcup \mathcal{F}=\bigcup _{\alpha \in I}{x}_{\alpha }\text{ and, if }I\ne \varnothing ,\bigcap \mathcal{F}=\bigcap _{\alpha \in I}{x}_{\alpha }.$$

Here is a concrete example: let $\mathcal{F}$ be the collection of all open intervals of the form $(a,b):=\{x\in \mathbb{R}:a<x<b\}$ for all $0<a<b$. I claim that $\bigcup \mathcal{F}={\mathbb{R}}^{+}:=\{x\in \mathbb{R}:x>0\}$. To prove this, notice that every element of the left set is a real number, by definition. Thus I only focus on the $\boxed{\supseteq }$ containment.

Let $x$ be a positive real. Then $a:=x/2$ is also positive. Therefore, $x\in (a,x+1)\subseteq \bigcup \mathcal{F}$, and I am done.

Products

I defined the Cartesian product of two sets $A\times B$. Here is how to define the generalized Cartesian product.

Definition (Cartesian product).

Let $\mathcal{F}=\{X_i:i\in I\}$ be an indexed family. The product is defined as

$$\prod _{i\in I}{X}_i:=\left\{f\in {\left(\bigcup _{i\in I}{X}_i\right)}^I:\forall i\in I,f(i)\in X_i\right\}.$$

That is, the elements of the product are all the functions $f:I\to {\bigcup }_{i\in I}{X}_i$ that for each index choose an element out of each set $X_i$. (These $f$ are often called choice functions.)

It is clear that the product of two nonempty sets is always empty. However for the general case, it is possible for the product to be empty even if all the $X_i$ are nonempty. This requires failure of the axiom of choice, and thus it is also impossible for me to give you an example using any of the tools developed so far in this course.

I will use the following meta-symbols $♣$ and $♠$. Let one of them by the union $\bigcup$ and the other one the intersection $\bigcap$. The theorems below are true for any nonempty indexed family of sets.

General distributivity laws.

$$\underset{i\in I}{♣}\underset{j\in J}{♠}{A}_{i,j}=\underset{f\in {\prod }_{i\in I}{J}_i}{♠}\underset{j\in J}{♣}{A}_{i,f(i)}$$

and

$$\prod _{i\in I}\left(\underset{j\in J_i}{♠}{A}_{i,j}\right)=\underset{f\in {\prod }_{i\in I}{J}_i}{♠}\left(\prod _{i\in I}{A}_{i,f(i)}\right).$$

General commutativity laws.

Let $\Phi :\mathcal{F}\to \mathcal{F}$ be a bijection. Then,

$$♠\mathcal{F}=♠\Phi [\mathcal{F}].$$

Equivalently, if $\phi :I\to I$ is a bijection, then

$$\underset{i\in I}{♠}{A}_i=\underset{i\in I}{♠}{A}_{\phi (i)}.$$

General associativity laws.

Let $\sim$ be an equivalence relation on $\mathcal{F}$. Then,

$$♣\mathcal{F}=♣♣\frac{\mathcal{F}}{\sim }.$$

Equivalently, if $\sim$ is an equivalence relation on $I$,

$$\underset{i\in I}{♣}{A}_i=\underset{C\in I/\sim }{♣}♣A_{i\in C}.$$

Laws for products.

All of the above are true when $♣$ is $\prod$, but both sides of every equality need to be enclosed in vertical bars (cardinality).

Basic exercises

Exercise.

Prove that for any set $X$, $X={\bigcup }_{x\in X}\{x\}$.

Exercise.

Let $A_k:=\{n\in \mathbb{Z}:n>k\}$ for any integer $k$. What is ${\bigcap }_{k\in \mathbb{Z}}{A}_k$?

Exercise.

If $\varnothing \ne \mathcal{A}\subset \mathcal{B}$, what is the relation between $\bigcap \mathcal{A}$ and $\bigcap \mathcal{B}$?

Exercise.

Show that the powerset operator commutes with the intersection but not the union. That is,

$$\bigcap _{i\in I}\mathcal{P}(A_i)=\mathcal{P}\left(\bigcap _{i\in I}{A}_i\right)\bigcup _{i\in I}\mathcal{P}(A_i)\subseteq \mathcal{P}\left(\bigcup _{i\in I}{A}_i\right).$$

Exercise.

1. For any set $X$, $\bigcap \mathcal{P}(X)=\varnothing$.
2. $\bigcup X=\varnothing$ if and only if $X=\varnothing$ or $A\in X$ implies $A=\varnothing$ for all $A$.