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.

  • 1
    $\begingroup$ thanks, but how do we know x ∈ A_i ∩ B_j∗ . And doesn't that contradict with x ∉ B_j∗ ? $\endgroup$ – foivos Dec 28 '15 at 13:21
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Clement C. Dec 28 '15 at 13:23
  • $\begingroup$ @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}$ $\endgroup$ – Clement C. Dec 28 '15 at 13:26
  • $\begingroup$ (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$) $\endgroup$ – Clement C. Dec 28 '15 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.