# Thread: Generalized version of associative law for unions

1. ## Generalized version of associative law for unions

Hi,
I am reading Naive Set Theory by Halmos and I can't wrap my head around this part:
Suppose that $\{I_J\}$ is a family of sets with domain $J$;write $K=\cup_jI_j$, and let $\{A_k\}$ be a familiy of sets with domain $K$.
It is then not difficult to prove that

$\cup_{k\in K}A_k=\cup_{j\in J}(\cup_{i\in I_j}A_i)$.

This is the generalized version of the associative law for unions.

Exercise: formulate and prove a generalized version of the commutative law.
-----------------------------------------------------------------------------------

I do not see how that is the generalized version of the associative law for unions. Could someone please put this in dumber terms?

Thank you.

2. First, I assume that " is a family of sets with domain " means that $I$ is a family indexed by elements of $J$, i.e., for each $j\in J$, $I_j$ is a set.

Each $I_j$ is a set of indices. For example, let $J=\{1,2,3\}$ and let $I_1=\{1,2,3\}$, $I_2=\{4,5,6\}$ and $I_3=\{7,8,9\}$. Then $K=\bigcup_{j\in J}I_j=\{1,2,\dots,9\}$ is the set of all indices.

Now suppose that for each index $k\in K$ there is a set $A_k$. In the equation , the left-hand side is something like $((\dots((A_1\cup A_2)\cup A_3)\cup\dots)\cup A_8)\cup A_9$, if $\cup$ is considered left-associative. The right-hand side is $\Big(\big((A_1\cup A_2)\cup A_3\big)\cup\big((A_4\cup A_5)\cup A_6\big)\Big)\cup \big((A_7\cup A_8)\cup A_9\big)$. The original associative law $(A_1\cup A_2)\cup A_3=A_1\cup(A_2\cup A_3)$ is obtained by taking $J_1=\{1\}$ and $J_2=\{2,3\}$.

3. Something tells me that the book author thought that, for example, the equation $A_1\cup\Big(A_2\cup(A_3\cup A_4)\Big)=\Big((A_1\cup A_2)\cup A_3\Big)\cup A_4$ is a special case of
, but after writing this I don't think so... Challenge problem: write the "general general" associative law that subsumes all distribution of parentheses.

4. Originally Posted by emakarov
Now suppose that for each index $k\in K$ there is a set $A_k$. In the equation , the left-hand side is something like $((\dots((A_1\cup A_2)\cup A_3)\cup\dots)\cup A_8)\cup A_9$, if $\cup$ is considered left-associative. The right-hand side is $\Big(\big((A_1\cup A_2)\cup A_3\big)\cup\big((A_4\cup A_5)\cup A_6\big)\Big)\cup \big((A_7\cup A_8)\cup A_9\big)$. The original associative law $(A_1\cup A_2)\cup A_3=A_1\cup(A_2\cup A_3)$ is obtained by taking $J_1=\{1\}$ and $J_2=\{2,3\}$.
I read the right side as $(A_1\cup A_2\cup A_3)\cup (A_4\cup A_5\cup A_6)\cup(A_7\cup A_8\cup A_9)$.
I do not understand how you get those paranthesis..

My brain hurts.

Thanks

5. There is no such thing as $A_1\cup A_2\cup A_3$. Strictly speaking, $\cup$ is a binary connective, so that formula has to be either $(A_1\cup A_2)\cup A_3$ or $A_1\cup (A_2\cup A_3)$. I assumed that by definition $\cup$ is left-associative (first variant above), so the informal notation $A_1\cup A_2\cup A_3\cup\dots\cup A_n$ has to be understood as $(\dots((A_1\cup A_2)\cup A_3)\cup\dots)\cup A_n$.

6. That makes sense, thanks.

Now for the generalized version of the commutative law for unions..
The only thing I can think of is that I perhaps need to have permutations of $\cup_kA_k$

So it would look something like,

$\cup_kA_k=permutations\;of\;\cup_kA_k$

Not very satisfying I know

7. Nothing really comes to mind that does not quantify over all permutations. One only need to permute the right set. In a permutation of $\textstyle\bigcup_{k}A_k$ one changes the order of the elements of all $A_k$ put together, not the order of the sets $A_k$. I would say, for every permutation $\sigma$ of $\{1,\dots,n\}$ (i.e., for every bijection $\sigma$ on this set), $\textstyle\bigcup_{k=1}^n A_k=\bigcup_{k=1}^n A_{\Box}$ (fill in the box).

8. Originally Posted by Mollier
I read the right side as $(A_1\cup A_2\cup A_3)\cup (A_4\cup A_5\cup A_6)\cup(A_7\cup A_8\cup A_9)$.
I do not understand how you get those paranthesis..

My brain hurts.

Thanks
Mollier,
I do not own a Halmos book. I have heard so much about the book. The book seems so thin. I am wondering if it explains concepts clearly. I have the following questions if you don't mind:

Does your book show the process of permuting union of sets?

Is it reabable?

9. Originally Posted by novice
Mollier,
I do not own a Halmos book. I have heard so much about the book. The book seems so thin. I am wondering if it explains concepts clearly. I have the following questions if you don't mind:

Does your book show the process of permuting union of sets?

Is it reabable?
Hi,

the book does list basic facts about intersections and unions, but as far as I have read it does not show the process.

As this is the only book I have ever picked up on set theory, I have no idea if it is any good..

10. Originally Posted by Mollier
Hi,

the book does list basic facts about intersections and unions, but as far as I have read it does not show the process.

As this is the only book I have ever picked up on set theory, I have no idea if it is any good..
Thank you for the useful information.

11. No problem. Could you recommend some good introductory texts to set theory?

12. Originally Posted by Mollier
No problem. Could you recommend some good introductory texts to set theory?
I am still looking for a good complete book on set theory. A friend of mine loan me a book on Schaum's outline Set Theory. I read it in a hurry and found it very good although I don't retain as much as I would like. It has tons of examples and exercises, but I am using it as a supplement. I am currently reading a very nice book recommended by an MHF member. Mathematical Proofs: A transition to Advanced Mathematics, by Gary Chartrand. The book is not on set theory, but I really like the book. It's well written. It explains basic Set Theory very, very well. I got a used one for \$16 including shipping on internet. You might want to read Chartrand's book first than go back to Halmos' Set Theory or use it side by side.

To MHF member:
Can anyone recommend us a good book on Set Theory--particularly for a serious learner like us?

Hello, hello, anyone home?

13. In order to really understand the scope of Halmos’ NAÏVE SET THEORY read his preface. I think the book was written for use of American graduate students c1960. It is an excellent overview but it is thin on proofs and it is definitely not strictly axiomatic.

I can suggest two texts for extensive set theory study: ELEMENTS OF SET THEORY by Herbert Enderton or SET THEORY AND LOGIC by Robert Stoll.

Just for general set theory study, one might consider a good discrete mathematics textbook.

14. Originally Posted by Plato
In order to really understand the scope of Halmos’ NAÏVE SET THEORY read his preface. I think the book was written for use of American graduate students c1960. It is an excellent overview but it is thin on proofs and it is definitely not strictly axiomatic.

I can suggest two texts for extensive set theory study: ELEMENTS OF SET THEORY by Herbert Enderton or SET THEORY AND LOGIC by Robert Stoll.

Just for general set theory study, one might consider a good discrete mathematics textbook.
Thank you, it's exciting to have your recommendation on the books, Plato.
By the way, the Discrete Math Book, by Kenneth H Rosen, you recommended me is a very good book. My school uses the book for CS Math. I have borrowed it briefly from a friend. When I get the money, I will definitely buy it.