Results 1 to 14 of 14

Math Help - Generalized version of associative law for unions

  1. #1
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    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\}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    Quote Originally Posted by emakarov View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    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).
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Mollier View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    Quote Originally Posted by novice View Post
    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..
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Mollier View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    No problem. Could you recommend some good introductory texts to set theory?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Mollier View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,709
    Thanks
    1640
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Plato View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Is Cartesian Product associative?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 1st 2010, 12:55 PM
  2. Commutative and Associative 71.5
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: October 26th 2009, 09:12 AM
  3. commutative, associative
    Posted in the Algebra Forum
    Replies: 8
    Last Post: October 22nd 2009, 09:52 PM
  4. generalized version of Therorem 4
    Posted in the Calculus Forum
    Replies: 1
    Last Post: October 4th 2009, 10:39 AM
  5. associative law
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: July 14th 2008, 03:08 PM

Search Tags


/mathhelpforum @mathhelpforum