While I was looking for a better understanding of the the concept of families (which is not yet entirely clear) in the Halmos book, I found me with this:

Let $\left\{ I_j \right\}$ be a family of sets with domain $J$; write $K = \bigcup_j I_j$ and let $\left\{ A_k \right\}$ be a family of sets with domain $K$. It is not difficult to prove that:

$$\bigcup_k A_k = \bigcup_{j\in J} \bigg( \, \bigcup_ {i\in I_j}A_i\, \bigg) $$

So, I have two question about this:

First: Is the next proof correct?

$$\bigcup_k A_k = \bigcup_{j\in J} \bigg( \, \bigcup_ {i\in I_j}A_i\, \bigg) $$

($\Rightarrow$) Suppose $z\in \bigcup_k A_k $. Then there is some $k\in K$ such that $z\in A_k$. But since $K = \bigcup_j I_j$, $k\in K$ means $k\in I_j$ for at least one $j\in J$. So, $z\in A_k$ for some $k\in I_j$, i.e., $z\in \bigcup_{k\in I_j} A_k$; for at least one $j\in J$. So then, $z\in \bigcup_{k\in I_j} A_k$ for some $j\in J$, i.e., $z\in \bigcup_{j\in J} \big( \, \bigcup_ {k\in I_j}A_k\, \big).$

($\Leftarrow$) Now suppose $z \in \bigcup_{j\in J} \big( \, \bigcup_ {i\in I_j}A_i\, \big)$. Then there is some $j\in J$ such that $z \in \bigcup_ {i\in I_j}A_i$. For $z \in \bigcup_ {i\in I_j}A_i$ in turn there is an $i\in I_j$ such that $z\in A_i$. Let's define the set $K := \bigcup_j I_j$ so clearly $i \in K$. Then there exists an $i \in K$ such that $z\in A_i$, so $z\in \bigcup_{i\in k} A_i$. $\;\;\; \Box$

And second: At the end of the paragraph the author says: "This is the generalized version of the associative law of union". But I cannot see how that generalized the associative law. Could somebody explain me the reason for which it is the generalized form, if it is not too much trouble, please?

As usual thanks in advance.


Your proof is fine.

Consider $I_0=\{0\}$, $I_1=\{1,2\}$, and $J=\{0,1\}$. Then $K=\{0,1,2\}$, so the result essentially says that

$$\bigcup_{k\in K}A_k=A_0\cup(A_1\cup A_2)\;.$$

If instead you set $I_0=\{0,1\}$ and $I_1=\{2\}$, it essentially says that

$$\bigcup_{k\in K}A_k=(A_0\cup A_1)\cup A_2\;.$$

Indirectly, therefore, it says that

$$A_0\cup(A_1\cup A_2)=(A_0\cup A_1)\cup A_2\;.$$

  • $\begingroup$ Thanks. The example is pretty illustrative of the main point. I realize that the idea can be use to intersection but only if we assumed that the indexes sets are non empty, is that right? $\endgroup$ – Jose Antonio Aug 16 '13 at 22:05
  • 2
    $\begingroup$ @Jose: You’re welcome. Yes, that’s right, though if you’re working in a setting in which all sets under consideration are subsets of some fixed set $X$, you can make it work even with empty index sets by setting $\bigcap\varnothing=X$. $\endgroup$ – Brian M. Scott Aug 16 '13 at 22:08
  • $\begingroup$ Sorry to abuse of your kindness but the idea of generalize the associative law to intersection is something that got in my mind since I published the question. So I think that $K$ is left equal and because we are not using a context here we assume that the family $\left\{I_j\right\}$ is non empty. With that in mind I tried to prove $\bigcap_k A_k = \bigcap_ {j\in J} \big (\bigcap_{i\in I_j} A_i \big)$. So using element chasing. $z\in \bigcap_k A_k, $ so $z\in A_k $ for each $k\in K = \bigcup_j I_j$. $\endgroup$ – Jose Antonio Aug 19 '13 at 3:23
  • $\begingroup$ Let $k$ be arbitrary. So there is some $j\in J$ such that $k\in I_j$. Then, $z\in A_k$ for each arbitrary $k\in I_j$, so $z\in \bigcap_{k\in I_j} A_k$. And here I'm a little stuck I know the answer but I'm not completely sure how to argue it. Therefore, if it is too much trouble for you could give me a help, please? $\endgroup$ – Jose Antonio Aug 19 '13 at 3:24
  • $\begingroup$ @Jose: Suppose that $z\in\bigcap_kA_k$; then $z\in A_k$ for each $k\in K$. Now let $j\in J$ be arbitrary. $I_j\subseteq K$, so $z\in A_i$ for each $i\in I_j$, and therefore $z\in\bigcap_{i\in I_j}A_i$. Since $j\in J$ was arbitrary, it follows that $z\in\bigcap_{i\in I_j}A_i$ for each $j\in J$ and hence that $z\in\bigcap_{j\in J}\bigcap_{i\in I_j}A_i$. To go the other way, assume that $z\in\bigcap_{j\in J}\bigcap_{i\in I_j}A_i$, let $k\in K$ be arbitrary, and show that $z\in A_k$. $\endgroup$ – Brian M. Scott Aug 19 '13 at 3:39

Your proof is correct. I guess one way to see why this is a generalization is to note that usually the associative law of union is stated via three sets:$$A \cup (B \cup C) = (A\cup B)\cup C.$$ We can also write it in this form: $$A_1 \cup (A_2 \cup A_3) = (A_1\cup A_2)\cup A_3.$$ The LHS corresponds to the case where $I_1 = \{1\}$, $I_2 = \{2,3\}$, and $J=\{1,2\}$, and the RHS corresponds to the case where $I_1 = \{1,2\}$, $I_2 = \{3\}$ and $J=\{1,2\}$. They are both equal to $\bigcup_{k\in K} A_k$ with $K = \{1,2,3\}$


$\cup_k A_k$ is defined in your equations to be a union of unions, with potentially infinitely many sets being unioned together in each union and potentially infinitely many unions being joined together into the final union. So the fact that the "union of unions" is equal to the union of all the constituents is a generalization of the basic associative law fact that $(A \cup B) \cup C$ = $A \cup (B \cup C)$, because you could define the union-of-unions any way you want, distributing the sets among the individual unions being unioned together, just as long as the final collection of constituent sets is the same. Hope that helps. And yes, your proof looks correct. :)

  • $\begingroup$ The first part sounds very cumbersome :P. But I think I understand the bottom line. I can pick in any way the $j \in J$ and $i\in I_j $ without altering the final result, which is the final union (as shown the illustrative examples above). $\endgroup$ – Jose Antonio Aug 16 '13 at 21:59

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.