# Associativity with families in Halmos' Naive Set Theory

I'm going through Halmos' naive set theory and am having trouble with the statement on page 35 in the Families section.

We have the family $$\{I_j\}$$ with domain $$J$$, so in other words $$I$$ is a function $$I: J \rightarrow$$ some other set.

We are also given $$K = \bigcup\limits_{j} I_j$$; and let $$\{A_k\}$$ be a family with domain $$K$$ (so $$A: K \rightarrow$$ some other set).

It then asserts $$\bigcup\limits_{k \in K} A_k = \bigcup\limits_{j \in J} \left(\bigcup\limits_{i \in I_j} A_i\right)$$

My question: why is the last union operator is iterating over $$i \in I_j$$?

Since $$K$$ is the union of the family $$\{I_j\}$$, I think that also means $$K$$ is the image of the function $$I$$. So each $$I_j$$ is a member of $$K$$. Perhaps worth noting is that everything in Halmos so far is a set, numbers haven't been constructed yet. So the $$I_j$$'s make up the members of $$K$$, but each $$I_j$$ is itself a set with an unknown count of elements.

To construct the set $$\bigcup\limits_{i \in I_j} A_i$$, $$A_i$$ would have to be defined on the elements of each individual $$I_j$$. But the elements $$i \in I_j$$ are not the same thing as the elements $$I_j$$ $$\in K$$. The domain of $$A$$ is given as $$K$$. So the arguments of $$A$$ are $$I_j \in K$$, not $$i \in I_j$$.

Have I misunderstood something about families? The book goes on to say this equality is the generalization of the associative law for unions. But I'm not sure how this demonstrates that since I'm not sure that $$A$$ is defined on the elements of $$I_j$$.

I think that also means $$K$$ is the $$\color{red}{\text{image}}$$ of the function $$I$$. So each $$I_j$$ is a $$\color{red}{\text{member}}$$ of $$K$$.

Incorrect. $$K = \bigcup_{i \in J}I_j$$ the arbitrary union of the image of $$I : J \to \mathcal{I}$$. So in fact each $$I_j$$ is a subset of $$K$$.

By the way the arbitrary union of a set $$S$$ is defined as $$x \in \bigcup S$$ $$\iff$$ there exists some $$s \in S$$ such that $$x \in s$$.

And for sake of comparison I also include the definition of the indexed union of a family of sets $$I : J \to \mathcal{I}$$: $$x \in \bigcup_{j \in J}I(j)$$ $$\iff$$ there is some $$t \in J$$ such that $$x \in I(t)$$.

Indeed we can calculate:

\begin{align*} x \in K = \bigcup_{j \in J} I_j &\iff x \in I_t = I(t) \text{ for some } t \in J \\ &\iff x \in I_t \text{ for some } I_t \in I(J) \\ &\iff x \in \bigcup I(J) \end{align*}

That is every element of $$K$$ is an element of an element of the image of $$I$$ (that was not a typo).

With this correction your confusion disappears. For if $$A : K \to \mathcal{A}$$ is some family of sets then:

$$x \in \bigcup_{k \in K}A_k$$ $$\iff$$ $$x \in A_i = A(i)$$ for some $$i \in K$$. But what does $$i \in K$$ mean? Well that itself means $$i \in I_j = I(j)$$ for some $$j \in J$$. And hence chaining everything together we get $$x \in \bigcup_{k \in K}A_k$$ $$\iff$$ $$x \in A_i = A(i)$$ for some $$i \in I_j$$ for some $$j \in J$$. And that last statement is true $$\iff$$ $$x \in \bigcup_{j \in J}\big(\bigcup_{i \in I_j}A_i\big)$$.

• Thanks for clearing that up! You're right, I was misinterpreting $\bigcup\limits_{j \in J} I_j$. – Benjamin Aug 13 at 16:44
• @Benjamin By the way, if your confusions have been cleared, then you should consider accepting one of the answers here. – 0XLR Aug 15 at 9:14

For each $$j$$, $$I_j$$ is a subset of $$K$$, and thus, for each $$i\in I_j$$, you get a set $$A_i$$ (because $$i\in I_j\subset \bigcup_{j\in J}I_j = K$$).

Thus, the last union is going over each element in $$K=\bigcup_{j\in J}I_j$$ by going through each element of each $$I_j$$.

$$K$$ is not quite the image of $$I$$; it’s the union of the elements in the image.

Let’s do an example. Say $$J=\{1,2,3\}$$, and $$I$$ is the function with images \begin{align*} I_1 &= \{ a, b, c\}\\ I_2 &= \{a,y\}\\ I_3 &= \{x\} \end{align*}

Then $$K= \bigcup_{j}I_j = \{a,b,c,y,x\}$$. Note that this is not the image of $$I$$ (which is the set $$\{I_1, I_2, I_3\}$$) but rather the union of the elements of the image; this is sometimes called the “amalgamated union” of the image, though the term is not very common. It is the set guaranteed by the Axiom of Unions, which says that given a set $$X$$, there is a set $$Z$$ with the property that $$z\in Z$$ if and only if there exists $$Y\in X$$ with $$z\in Y$$.

Thus, we have five sets indexed by $$K$$: $$A_a$$, $$A_b$$, $$A_c$$, $$A_y$$, and $$A_x$$.

The union on the left would just be the union of these five sets.

The union of the right is the union of three sets, namely \begin{align*} \bigcup_{i\in I_1}A_i &= A_a\cup A_b\cup A_c\\ \bigcup_{i\in I_2}A_i &= A_x\cup A_y;\\ \text{and }\bigcup_{i\in I_3}A_i &= A_{x}. \end{align*} Then you take the union of these three sets.

• Is each $I_j$ a member of $K$ or a subset of $K$? – Benjamin Aug 13 at 16:04
• @Benjamin: A subset. – Arturo Magidin Aug 13 at 16:57

Rewrite $$\{A_k:k\in K\}$$ as $$\{A_i:i\in K\}.$$

For all $$i$$ we have $$i\in K\iff \exists j\in J\,(i\in I_j)\}.$$

Therefore $$\cup_{i\in K}A_i=\bigcup \{A_i:i\in K\}=$$ $$=\bigcup \{A_i:\exists j\in J\,(i\in I_j)\}=$$ $$=\cup_{j\in J}\bigcup \{A_i:i\in J\}=$$ $$=\cup_{j\in J}\cup_{i\in I_j}A_i\,.$$