# Intersection distributing over an infinite union, union over an infinite intersection

I'm not really sure how to type this in notation...but I hope this makes sense. I help in proving that:

$$F \cap \bigcup\limits_{i=1}^\infty E_i = \bigcup\limits_{i=1}^\infty (F\cap E_i)$$

And

$$F \cup \bigcap\limits_{i=1}^\infty E_i = \bigcap\limits_{i=1}^\infty(F\cup E_i)$$

I really don't know where to begin with this one.

-

Probably the easiest way to prove these statements is by what I call element-chasing: show that every element of the left-hand side is also an element of the right-hand side and vice versa. Let’s look at the first one. Suppose that $x \in F \cap \bigcup\limits_{i=1}^\infty E_i$. The definition of intersection tells you that $x \in F$ and $x \in \bigcup\limits_{i=1}^\infty E_i$. Since $x \in \bigcup\limits_{i=1}^\infty E_i$, the definition of union tells you that $x$ belongs to at least one of the sets $E_1,E_2,E_3,\dots$, so there is some positive integer $k$ such that $x \in E_k$. (There might be more than one such integer, but all we need is one.) Now we know that $x \in F$ and $x \in E_k$, so $x \in F \cap E_k$. But $x \in F \cap E_k$ is one of the sets that goes into the union $\bigcup\limits_{i=1}^\infty (F\cap E_i)$ on the right-hand side, so automatically $F \cap E_k \subseteq \bigcup\limits_{i=1}^\infty (F\cap E_i)$, and therefore $x \in \bigcup\limits_{i=1}^\infty (F\cap E_i)$. We’ve now shown that every member of $F \cap \bigcup\limits_{i=1}^\infty E_i$ is also a member of $\bigcup\limits_{i=1}^\infty (F\cap E_i)$, or in other words that $$F \cap \bigcup\limits_{i=1}^\infty E_i \subseteq \bigcup\limits_{i=1}^\infty (F\cap E_i).$$ To finish the argument, you have to show that $$\bigcup\limits_{i=1}^\infty (F\cap E_i)\subseteq F \cap \bigcup\limits_{i=1}^\infty E_i.$$ You do this the same way, by starting with an arbitrary $x \in \bigcup\limits_{i=1}^\infty (F\cap E_i)$ and showing that it must belong to $F \cap \bigcup\limits_{i=1}^\infty E_i$ as well.

You can handle the second statement the same way: first show that every member of $F \cup \bigcap\limits_{i=1}^\infty E_i$ is a member of $\bigcap\limits_{i=1}^\infty(F\cup E_i)$, and then show the opposite inclusion. I’ll get you started. Suppose that $x \in F \cup \bigcap\limits_{i=1}^\infty E_i$; then $x \in F$ or $x \in \bigcap\limits_{i=1}^\infty E_i$ (or both), and you’ll have to distinguish two cases.

(1) If $x \in F$, then $x \in F \cup E_i$ for every positive integer $i$, so $x \in \bigcap\limits_{i=1}^\infty(F\cup E_i)$ by the definition of intersection.

(2) If $x \in \bigcap\limits_{i=1}^\infty E_i$, then ... what? I’ll leave this case to you, as well as the opposite inclusion.

-
Element chasing. Nice. I will use that in the future. – Asaf Karagila Sep 21 '11 at 5:40
@Asaf Karagila: Element-chasing is actually unfolding of definitions from set theory: definitions of set equality, $\subseteq, \bigcap, \cap, \bigcup, \cup$, \. And this method gives formal proofs as opposed to Venn diagrams. – beroal Sep 26 '11 at 14:04
@beroal: I am not 100% clear on what you were trying to say in that comment of yours. – Asaf Karagila Sep 26 '11 at 14:07
@Asaf: I think that beroal didn’t realize that you were commented on the term, not on the method. – Brian M. Scott Sep 26 '11 at 17:49
@Brian: Oh, that sounds like a reasonable thought. Albeit somewhat amusing (reminiscing how once I explained to a barfly about quantum theory later to find out he has a Ph.D. in physics). – Asaf Karagila Sep 26 '11 at 17:54

For the first one:

We prove that the left hand side is contained in the right hand side, and conversely.

Suppose that $x\in F\cap\bigcup\limits_{i=1}^{\infty}$. That means that $x\in F$, and $x\in \bigcup\limits_{i=1}^{\infty}E_i$; therefore, $x\in F$ and there exists $n$ such that $x\in E_n$. Therefore, there exists $n$ such that $x\in F$ and $x\in E_n$, so $x\in F\cap E_n$. Thus, there exists at least one $n$ such that $x\in F\cap E_n$, so $x\in \bigcup\limits_{i=1}^{\infty}(F\cap E_i)$, as desired.

For the converse inclusion, suppose that $y\in \bigcup\limits_{i=1}^{\infty}(F\cap E_i)$. That means that there exists an $n$ such that $y\in F\cap E_n$. Therefore, $y\in F$, and there is an $n$ such that $y\in E_n$; the latter condition implies that $y\in\bigcup\limits_{i=1}^{\infty}E_i$. Since we also have $y\in F$, then $y$ lies in the intersection $F\cap\bigcup\limits_{i=1}^{\infty}E_i$.

Thus, we have shown that $$F\cap\bigcup_{i=1}^{\infty}E_i \subseteq \bigcup_{i=1}^{\infty}(F\cap E_i)\text{ and } \bigcup_{i=1}^{\infty}(F\cap E_i) \subseteq F\cap\bigcup_{i=1}^{\infty}E_i.$$ Hence, the two sets are equal.

A similar argument holds for the second equality, remembering that lying in the intersection means lying in every one of the sets.

-