Question about proving that a ﬁnite intersection of big unions is a big union of ﬁnite intersections

Let $I_{1}$,...$I_{k}$ be index sets and for each $1 \leq m \leq k$ and each $j \in I_{m}$, let $U_{j}$ be a set.

Prove that: $$(\bigcup\limits_{j_{1}\in I_{1}}U_{j_{1}}) \cap ... \cap(\bigcup\limits_{j_{k}\in I_{k}}U_{j_{k}}) = \bigcup\limits_{(j_{1},...,j_{k})\in I_{1} \times ... \times I_{k}}U_{j_{1}} \cap ... \cap U_{j_{k}}$$

I understand that I need to prove a finite intersection of big unions is a big union of finite intersections. How would I prove this?

• A standard way to prove that two sets are equal is to show that each is a subset of the other. – Dan Z Jul 26 '14 at 18:18

This reminds me of the distributive law for set theory operations. You can prove it by proving the following statements:

1. $(\bigcup\limits_{j_{1}\in I_{1}}U_{j_{1}}) \cap ... \cap(\bigcup\limits_{j_{k}\in I_{k}}U_{j_{k}}) \subseteq \bigcup\limits_{(j_{1},...,j_{k})\in I_{1} \times ... \times I_{k}}U_{j_{1}} \cap ... \cap U_{j_{k}}$

2. $\bigcup\limits_{(j_{1},...,j_{k})\in I_{1} \times ... \times I_{k}}U_{j_{1}} \cap ... \cap U_{j_{k}} \subseteq (\bigcup\limits_{j_{1}\in I_{1}}U_{j_{1}}) \cap ... \cap(\bigcup\limits_{j_{k}\in I_{k}}U_{j_{k}})$.

I'll prove the first statement. The second is left to you.

Proof. Suppose $x \in (\bigcup\limits_{j_{1}\in I_{1}}U_{j_{1}}) \cap ... \cap(\bigcup\limits_{j_{k}\in I_{k}}U_{j_{k}})$. This means that for all $i \in \{1, 2, \ldots, k\}$, $x \in (\bigcup\limits_{j_{i}\in I_{i}}U_{j_{i}})$. Then for all $i \in \{1, 2, \ldots, k\}$, we can choose some $j_i \in I_i$ such that $x \in U_{j_{i}}$. But then since $j_1 \in I_1, \ldots, j_k \in I_k$, we can conclude that $(j_1, \ldots, j_k) \in I_1 \times \ldots \times I_k$. We also know that for all $i \in \{1, 2, \ldots, k\}$, $x \in U_{j_{i}}$, so we can say that $x \in U_{j_1} \cap \ldots \cap U_{j_k}$. Therefore, $x \in \bigcup\limits_{(j_{1},...,j_{k})\in I_{1} \times ... \times I_{k}}U_{j_{1}} \cap ... \cap U_{j_{k}}$.