Tao Analysis I - 3.5.9

Exercise 3.5.9

Suppose that $I$ and $J$ are two sets, and for all $\alpha \in I$ let $A_{\alpha}$ be a set, and for all $\beta \in J$ let $B_{\beta}$ be a set. Show that

$$(\bigcup_{\alpha \in I} A_{\alpha}) \cap (\bigcup_{\beta \in J} B_{\beta}) = \bigcup_{(\alpha,\beta) \in I \times J} (A_{\alpha} \cap B_{\beta})$$

What happens if one interchanges all the union and intersection symbols here?

Solution Strategy

For this solution I wanted to develop the proof using only a chain of equivalences $\iff$, rather than the more verbose approach of proving one direction $\implies$, and the other direction $\impliedby$.

This math stack exchange answer helped clarify this approach, which is still unfamiliar to me (link). 

In addition this wikipedia article on manipulating prenex normal form is useful (link).

Solution Part One

Let's start with the LHS.

$$x \in (\bigcup_{\alpha \in I} A_{\alpha}) \cap (\bigcup_{\beta \in J} B_{\beta}) \iff x \in (\bigcup_{\alpha \in I} A_{\alpha}) \land x \in (\bigcup_{\beta \in J} B_{\beta})$$

Using the definition of the union of sets, this means both of the following are true:

• $x$ is an element of at least one $A_{\alpha}$
• $x$ is an element of at least one $B_{\beta}$

For the next step we have to take care with the use of the $\exists$ existential quantifier.

$$x \in (\bigcup_{\alpha \in I} A_{\alpha}) \cap (\bigcup_{\beta \in J} B_{\beta}) \iff (\exists \alpha\in I) \; [x \in A_{\alpha}] \land (\exists \beta\in J) \; [x \in B_{\beta}]$$

This is essentially writing out what we have written in the bullet points.

If there exists an $\alpha \in I$ and a $\beta \in J$ which meet certain conditions,  then there exists an $(\alpha, \beta) \in I \times J$ where the same conditions are met. That is,

$$\begin{align}x \in (\bigcup_{\alpha \in I} A_{\alpha}) \cap (\bigcup_{\beta \in J} B_{\beta}) & \iff (\exists \alpha\in I) \; [x \in A_{\alpha}] \land (\exists \beta\in J) \; [x \in B_{\beta}] \\ \\ & \iff (\exists (\alpha, \beta) \in I\times J ) \; [x\in A_{\alpha} \land x \in B_{\beta}] \\ \\ & \iff (\exists (\alpha, \beta) \in I\times J ) \; [x\in A_{\alpha}\cap B_{\beta}] \\ \\ & \iff x \in \bigcup_{(\alpha,\beta) \in I \times J} (A_{\alpha} \cap B_{\beta})  \end{align}$$

Thus, we have shown

$$(\bigcup_{\alpha \in I} A_{\alpha}) \cap (\bigcup_{\beta \in J} B_{\beta}) = \bigcup_{(\alpha,\beta) \in I \times J} (A_{\alpha} \cap B_{\beta}) \; \square$$

Solution Part Two

Now consider what happens if we interchange the union and intersection symbols. We have a new proposal to show:

$$(\bigcap_{\alpha \in I} A_{\alpha}) \cup (\bigcap_{\beta \in J} B_{\beta}) = \bigcap_{(\alpha,\beta) \in I \times J} (A_{\alpha} \cup B_{\beta})$$

The proof is almost the same, so we'll only write down the essence of it.

Let's start with the LHS.

$$(\bigcap_{\alpha \in I} A_{\alpha}) \cup (\bigcap_{\beta \in J} B_{\beta}) \iff x \in (\bigcap_{\alpha \in I} A_{\alpha}) \lor x \in (\bigcap_{\beta \in J} B_{\beta})$$

Using the definition of the intersection of sets, this means either or both of the following are true:

• $x$ is an element of every $A_{\alpha}$
• $x$ is an element of every $B_{\beta}$

For the next step we have to take care with the use of the $\forall$ "for all" quantifier.

$$x \in (\bigcap_{\alpha \in I} A_{\alpha}) \cup (\bigcap_{\beta \in J} B_{\beta}) \iff (\forall \alpha\in I) \; [x \in A_{\alpha}] \lor (\forall \beta\in J) \; [x \in B_{\beta}]$$

We continue in a similar manner to the above,

$$\begin{align}x \in (\bigcap_{\alpha \in I} A_{\alpha}) \cup (\bigcap_{\beta \in J} B_{\beta}) & \iff (\forall \alpha\in I) \; [x \in A_{\alpha}] \lor (\forall \beta\in J) \; [x \in B_{\beta}] \\ \\ & \iff (\forall (\alpha, \beta) \in I\times J ) \; [x\in A_{\alpha} \lor x \in B_{\beta}] \\ \\ & \iff (\forall (\alpha, \beta) \in I\times J ) \; [x\in A_{\alpha}\cup B_{\beta}] \\ \\ & \iff x \in \bigcap_{(\alpha,\beta) \in I \times J} (A_{\alpha} \cup B_{\beta})  \end{align}$$

Thus, we have shown

$$(\bigcup_{\alpha \in I} A_{\alpha}) \cup (\bigcup_{\beta \in J} B_{\beta}) = \bigcap_{(\alpha,\beta) \in I \times J} (A_{\alpha} \cup B_{\beta}) \; \square$$