# Equality between expressions for 2 families of sets

For families of sets $\{A_i \}$ and $\{B_j \}$

$(\bigcap _i A_i) \cup (\bigcap _j B_j) = \bigcap _{i,j} (Ai ∪ Bj)$.

If the left-hand side is the union of the most frequently occurring elements $(>1)$ in each set, I can't see how it equals the right-hand side. If the right-hand side is the intersection of the pairs $(a_i,b_j)$ for $I\times J$, wouldn't that result in a maximum of a 2 element set? Is this the right course?

It may be simpler to use the more down-to-earth view (or proof) of this equality. We can show more easily that both RHS $\subseteq$ LHS and LHS $\subseteq$ RHS, which implies LHS = RHS. This is done by taking an arbitrary element of the LHS and showing it also appears in the RHS, and vice-versa.

• Take an element $x$ in the LHS (we want to show that it also belongs to the RHS): by definition, it either belongs to (i) $A_i$ for every $i$; or (ii) $B_j$ for every $j$ (or (iii) both). Assume without loss of generality that it is (i): then, $x$ belong to $A_i\cup B_j$ for every pair $(i,j)$, since it belongs to $A_i$ for every $i$. But then, it belongs to the intersetion, and therefore LHS is a subset of the RHS: LHS $\subseteq$ RHS.

• Now, the other way around: take any $x$ in the RHS. For any pair $(i,j)$, by definition $x\in A_i\cup B_j$, i.e. $x$ belongs to at least one of the $A_i$ or $B_j$. You need to prove that it belongs to (i) all $A_i$'s or (ii) to all $B_j$'s (so that it belongs to the union of the $\bigcap_i A_i$ and $\bigcap_j B_j$, which is the LHS). Assume, again wlog -- the other case is symmetric -- that $x$ does not belong to all $B_j$'s, i.e. $x\notin \bigcap_j B_j$. This means there exists $j^\ast$ such that $x\notin B_{j^\ast}$; and you need to prove that $x\in \bigcap_i A_i$.

But then, we know that $x\in A_i\cup B_{j^\ast}$ for all $i$. Since $x\notin B_{j^\ast}$, this amounts to saying that $x\in A_i$ for all $i$, that is $x\in \bigcap_i A_i$. So in particualr $x\in \left(\bigcap_i A_i\right)\cup\left(\bigcap_j B_j\right)$, which is the LHS: RHS $\subseteq$ LHS.

Overall, LHS = RHS.

• thanks, but how do we know x ∈ A_i ∩ B_j∗ . And doesn't that contradict with x ∉ B_j∗ ? – foivos Dec 28 '15 at 13:21
• The proof is correct, but what is confusing right now is that the person that edited the question changed it -- as currently written, what is asked has become incorrect. The RHS should have a $\bigcap_{i,j}$, not a $\bigcup_{i,j}$. – Clement C. Dec 28 '15 at 13:23
• @foivos By definition of $\bigcap_{i,j}$, $x$ is in the RHS iff it belongs to every single set $A_i\cup B_j$. By assumption in the proof, we then know that it does not belong to $\cap_j B_j$ (if it does, then it belongs to the LHS and we are done anyway). So there is a $B_{j^\ast}$ as stated; but $x$ belongs to all $A_i\cup B_j$'s, so it in particular also has to belong to $A_i\cup B_{j^\ast}$ – Clement C. Dec 28 '15 at 13:26
• (and you were right, there was a $A_i\cap B_j$ in my answer that needed to be a $A_i \cup B_j$) – Clement C. Dec 28 '15 at 13:29