# Which definition should I use to prove $\bigcup_i A_i \times \bigcup_j B_j = \bigcup_{i, j}(A_i \times B_j)$

I'm studying some set theory from Halmos' book. He asks to prove $$\bigcup_i A_i \times \bigcup_j B_j = \bigcup_{(i, j) \in I \times J}(A_i \times B_j)$$

I want to prove it using the definition of generalized version of Cartesian product, not just taking $(a, b)$ as elements. But I struggle with the idea that elements of the set from the left side of the equality differ from the ones on the right side. Namely, on the left side we will have a set of families with an unordered pair as the index set (because it is a cartesian product of just two sets in the end) but on the right side we have a set of families with also unordered pairs as index sets but different for each family.

So, what is the proper way to prove it? Is it possible to prove it with the generalized version of the Cartesian product? And if yes, then should I introduce somehow a choice function or what other steps should I take?

P.S.: I am interested in more rigorous proof like taking an element from both sides and showing that it is also in another side. The problem I described appears on that level.

• elements of the set on LHS take the form $(a,b)$ with $a\in\bigcup_iA_i$ and $b\in\bigcup_iB_i$. This is also the case for elements of the set on RHS. So I don't see your problem. Btw, the RHS is formally a union of Cartesian products. In both cases the products that appear are binary products, so why do you tend to "generalized product"? – Vera Jun 2 '18 at 12:07
• @Vera, because I want to make sure that I understand the generalized version and try to use it. The equality also seats in the context together with the generalized version in the book. So, not being able to use it makes me feel sad about consistency of set theory or rather it arises the question "why the definition exists when I can't use it to prove the equality?" – Turkhan Badalov Jun 2 '18 at 12:22
• Then what exactly is the definition of generalized version of Cartesian products? Could you add that in an edit of your question? – Vera Jun 2 '18 at 12:24
• @Vera, I don't think it is necessary to add it in the question. But let $\{X_i\}$ be a family of sets where $I$ is the index set and $i \in I$. Then the cartesian product of the family is a set of all families $\{x_i\}$ with $x_i \in X_i$ for each $i \in I$. – Turkhan Badalov Jun 2 '18 at 12:40
• @Vera, so for example if $X_0 = \{ 1 \}$ and $X_1 = \{2, 3\}$ then the cartesian product of the family $\{X_i\}$ with $i \in \{0, 1\}$ is the set $\{ \{ (0, 1), (1, 2) \}, \{ (0, 1), (1, 3) \} \}$ – Turkhan Badalov Jun 2 '18 at 12:42

## 2 Answers

Equivalent are the statements:

• $(a,b)\in\bigcup_iA_i\times\bigcup_jB_j$
• $a\in\bigcup_iA_i\wedge b\in\bigcup_jB_j$
• $\exists i[a\in A_i]\wedge\exists j[b\in B_j]$
• $\exists (i,j) [a\in A_i\wedge b\in B_j]$
• $\exists (i,j) [(a,b)\in A_i\times B_j]$
• $(a,b)\in\bigcup_{(i,j)}(A_i\times B_j)$

This allows us to conclude that:$$\bigcup_iA_i\times\bigcup_jB_j=\bigcup_{(i,j)}(A_i\times B_j)$$

edit

LHS denotes the set $F$ of functions $\{0,1\}\to(\bigcup_iA_i)\cup(\bigcup_jB_j)$ that satisy $f(0)\in\bigcup_iA_i$ and $f(1)\in\bigcup_jB_j$.

RHS denotes a collection $\bigcup_{i,j}F_{i,j}$ where $F_{i,j}$ is the set of functions $\{0,1\}\to A_i\cup B_j$ that satisfy $f(0)\in A_i$ and $f(1)\in B_j$.

Now it must be proved that $F=\bigcup_{i,j}F_{i,j}$

It is evident that $F_{i,j}\subseteq F$ for every pair $(i,j)$, showing that set on RHS is a subset of set on LHS.

If $f\in F$ then for some pair $(i,j)$ we have $f(0)\in A_i$ and $f(1)\in B_j$, so that $f\in F_{i,j}$. This shows that set on LHS is a subset of set on RHS.

Proved is now that the sets are equal.

• Thanks for the answer! Yes, but now let $x = (a,b) \in \bigcup_i A_i \times\bigcup_j B_j$ then $x$ is the family with the index set $\{0, 1\}$ where $x_0 \in \bigcup_i A_i$ and $x_1 \in \bigcup_j B_j$. And then I don't know how to match these two indices to different index sets of RHS. – Turkhan Badalov Jun 2 '18 at 12:45
• So an element of $A\times B$ is according to that "generalized Cartesian product" actually a function $f:\{0,1\}\to A\cup B$ with the special property that $f(0)\in A$ and $f(1)\in B$. Is that the correct interpretation? – Vera Jun 2 '18 at 12:49
• Yes, right on the button! Now I want to prove based on this definition. – Turkhan Badalov Jun 2 '18 at 12:50

(x,y) in $(\cup_i A_i) × \cup_j B_j$ iff
exists i,j with x in $A_i,$ y in $B_j$ iff
exists i,j with (x,y) in $(A_i × B_j)$ iff
(x,y) in $\cup_{i,j} (A_i × B_j)$

$(\cup_i A_i) × B_j = \cup_i (A_i×B_j)$
Let K = $\cup_i A_i$
K × $\cup_j B_j = \cup_j (K×B_i) = \cup_{i,j} (A_i×B_j)$

• Thanks for the answer. But I am interested in more rigorous proof like taking some element from both sides and showing that it is also in another side. The problem I described appears on that level. – Turkhan Badalov Jun 2 '18 at 12:32
• That algebraic like proof is rigorous. See edit @TurkhanBadalov for a point by point proof. – William Elliot Jun 2 '18 at 22:01