2
$\begingroup$

If there is two family of sets $\left\{A_i:i\in I\right\}$, $\left\{B_j:j\in J\right\}$,
Prove$$\left(\bigcap_{i\in I}A_i\right)\cup\left(\bigcap_{j\in J}B_j\right)=\bigcap_{(i,j)\in I\times J}{(A_i\cup B_j)}$$ My approach $$x\in\left(\bigcap_{i\in I}A_i\right)\cup\left(\bigcap_{j\in J}B_j\right)\\ \Leftrightarrow x\in \left(\bigcap_{i\in I}A_i\right)\lor x\in\left(\bigcap_{j\in J}B_j\right)\\\Leftrightarrow x\in\bigcap_{(i,j)\in I\times J}{(A_i\cup B_j)}$$ But, I am not sure I did it right between the second and the third expression.

Please check if my approach is right, and if there is some ways to improve it. And if there is other ways to prove this, show them too.

$\endgroup$
5
  • 1
    $\begingroup$ 2nd line is incorrect. 3rd line is jumping to a conclusion. $\endgroup$ Dec 26, 2019 at 8:37
  • $\begingroup$ If $I=\emptyset$ and $J\neq\emptyset$, what does this mean? Is there a missing assumption that $I$ and $J$ are both nonempty? $\endgroup$
    – Steve Kass
    Dec 26, 2019 at 15:29
  • $\begingroup$ @SteveKass In this case, intersection is ill-defined, and I think this is what you have intended. However, we may simply take $\bigcap_{i\in I} A_i$ be the class of all sets (as $\forall i\in \varnothing (x\in A_i)$ holds for all sets $x$), and under this definition, the equality still holds. $\endgroup$
    – Hanul Jeon
    Dec 26, 2019 at 17:35
  • $\begingroup$ Suppose $A_i=\{i+{1\over2}\}$ and $B_i=\{i,i+1\}$, $I=\emptyset$, and $J=\{0,1\}$. Now consider your proposition. $$\left(\bigcap_{i\in I}A_i\right)\cup\left(\bigcap_{j\in J}B_j\right)=\bigcap_{(i,j)\in I\times J}{(A_i\cup B_j)}$$ The left side is $\left(\bigcap_{i\in \emptyset}A_i\right)\cup\{1\}$, which depends on $J$, but the right side is $\bigcap_{(i,j)\in \emptyset}\{i+{1\over2},j,j+1\}$, which is independent of $J$. How do you propose to define the empty intersections in a way that this identity is true without a restriction that $I$ and $J$ be nonempty? $\endgroup$
    – Steve Kass
    Dec 26, 2019 at 23:05
  • 1
    $\begingroup$ @SteveKass I have already given an answer to your question: just simply take the class of all sets. This is not a set, of course. $\endgroup$
    – Hanul Jeon
    Dec 27, 2019 at 8:35

2 Answers 2

1
$\begingroup$

As @William Elliot stated, you need more justification to imply the conclusion from the second line.

For the left-to-right direction, we have either $x\in \bigcap_{i\in I} A_i$ or $x\in \bigcap_{j\in J} B_j$. In the former case, we have $x\in A_i$ for all $i$, so $x\in A_i\cup B_j$ for all $i\in I$ and $j\in J$. You can see that this is equivalent to $x\in A_i\cup A_j$ for all $(i,j)\in I\times J$. Therefore $x\in \bigcap_{(i,j)\in I\times J} A_i\times B_j$. The remainder case is similar.

Now assume that $x\in \bigcap_{(i,j)\in I\times J} A_i\cup B_j$, so that $x\in A_i\cup B_j$ for all $(i,j)\in I\times J$. Assume the contraty that we have $x\notin (\bigcap_{i\in I} A_i)\cup (\bigcap_{j\in J}B_j)$. Then you can see that

  1. $x\notin \bigcap_{i\in I} A_i$ and

  2. $x\notin \bigcap_{j\in J} B_j$.

Each of them is equivalent to $\lnot (\forall i\in I : x\in A_i)$ and $\lnot (\forall j\in J : x\in B_j)$ respectively. In addition, they are equivalent to $\exists i\in I: x\notin A_i$ and $\exists j\in J: x\notin B_j$. That is, we found $(i,j)\in I\times J$ such that $x\notin A_i\cup B_j$. This contradicts with the assumption.


In fact, we can derive the folloiwng general distribution law: $$\bigcup_{i\in I} \bigcap_{j\in J_i} A_j = \bigcap_{f\in C}\bigcup_{i\in I} A_{f(i)},$$ where $C$ is the set of all 'choice functions' over the family $\langle J_i\mid i\in I\rangle$: $$C := \left\{\left.f : I\to\bigcup_{i\in I} J_i \,\right\vert\, \forall i\in I (f(i)\in J_i) \right\}.$$

The statement you asked is a special case ($I=\{0,1\}$) of the generalized distributive law. Note that it is easier to prove the following dual form of the generalized distribution law:

$$\bigcap_{i\in I} \bigcup_{j\in J_i} A_j = \bigcup_{f\in C}\bigcap_{i\in I} A_{f(i)}.$$ It could be worth mentioning that the generalized distribution law is equivalent to the axiom of choice (in fact, the left-to-right inclusion is another form of the axiom of choice.)

$\endgroup$
1
$\begingroup$

The core of a proof uses the logical equivalence
for all x, P(x) or for all y, Q(y)
iff for all x,y, (P(x) or Q(y)).

Left to right is a simple proof.
For right to left, prove the counter positive.
Negating the left side one has
exists x with not-P(x) and exists y with not-Q(x)
exists x,y with (not-P(x) and not-Q(x))
exists x,y with not-(P(x) or Q(y))
which is the negation of the right side

$\endgroup$

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.