Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Associativity and commutativity of sets

  1. May 16, 2012 #1
    Hi all. In chapter 9 of Halmos's book titled Naive set theory, he talks about families of sets. He then talks about the associativity of sets as follows
    "The algebraic laws satisfied by the operation of union for pairs can be
    generalized to arbitrary unions. Suppose, for instance, that {Ij} is a
    family of sets with domain J, say; write K = [itex]\bigcup[/itex]j Ij and Ak be a family
    of sets with domain K. It is then not difficult to prove that
    [itex]\bigcup[/itex]k[itex]\in[/itex]KAk= [itex]\bigcup[/itex]j[itex]\in[/itex]J([itex]\bigcup[/itex]i[itex]\in[/itex]IjAi);
    this is the generalized version of the associative law for unions. Exercise:
    formulate and prove a generalized version of the commutative law".

    I could prove the associative law; however, I cannot formulate the commutative law. Basically formulating the generalized commutativity of union of sets in terms of indexed family of sets is not clear to me. How will the commutative law look like when written using the jargon of indexed family of sets? I would greatly appreciate your help in this matter.
    Last edited: May 16, 2012
  2. jcsd
  3. May 16, 2012 #2
    Think about permuting the indexing set.
  4. May 26, 2012 #3
    Thanks very much dcpo. I also got the same advice from Steve. I am having trouble formalizing the whole thing. Steve suggested that I should take a permutation 's' of the indexing set, say 'I', where the permutation 's' on 'I' maps 'I' to 'I' itself and is a bijection from I to I.

    I thought of another way to attack this and that was to use ordered sets.

    Let a set O be any ordered set with each of its elements being distinct members of I. Let A be the family of sets indexed by O and let B be the intersection of the indexed sets. Formally, let B=[itex]\bigcup[/itex][itex]_{\left\{i \in O\right\}}[/itex]A[itex]_{i}[/itex]. Then the set B is uniquely defined for any such ordered set O.

    It is easy to prove the above statement but the main problem was the formulation of the statement of commutativity.

    I'd greatly appreciate it if you can kindly comment about the correctness of the above formulation of commutativity of sets.
  5. Jun 1, 2012 #4
    I'm sorry I missed this reply earlier. I'm not entirely sure what you're trying to say with your formulation. If you mean to say that distinct orderings define distinct sets then you are incorrect (and such a property is the opposite of what you're after anyway). For example, we can let [itex]I=\{1,2\}[/itex] with its natural ordering and take [itex]O=\{1,2\}[/itex] ordered by [itex]2\leq 1[/itex], then [itex]A_1\cup A_2= A_2\cup A_1[/itex], which is basic commutativity.

    You don't need to bring ordered set into this. An ordinal is already a total order (it's a canonical well ordered set), and you could formalize a commutativity law in terms of alternative total orders with the same carrier (underlying set), but to make this precise you'd be using a laboured permutation argument so we might as well just be direct.

    So, given [itex]I[/itex] let [itex]\sigma\colon I\to I[/itex] be a bijection, think about [itex]\bigcup_I A_{\sigma(i)}[/itex]. What does this look like when [itex]I[/itex] is finite? Is it the same as [itex]\bigcup_I A_i[/itex]? Does this generalize to the infinite case?
  6. Jun 2, 2012 #5
    Thanks dcpo. I was trying to prove the opposite. I was trying to prove that distinct ordering result in the same set, namely the union.

    The reason why I did not use bijection is because Halmos had not introduced bijection at that point; he has defined only ordered pairs/sets.

    Also, I know that for the finite set case, commutativity, the way you have formulated, is true. For the infinite case also, it must be true as the simple fact is that a bijection has to have every element in the range, a corresponding element in the domain. Hence if x[itex]\in[/itex]X[itex]_{i}[/itex], then there is a σ(j)=i (as σ is a bijection) such that x[itex]\in[/itex]X[itex]_{σ(j)}[/itex] and each step in this is reversible simply because σ is a bijection. Please do correct me if I am wrong.

    Is it possible to use ordered sets instead? Was my formulation incorrect?
  7. Jun 2, 2012 #6
    Ok, I've not read the Halmos book so I don't know what ideas are available to you at this point, but from what you say my guess is that Halmos is aiming to get you to arrive at the idea of a bijection using ordered pairs. I may have misunderstood but it seems like you're trying to extend the ordered pair idea idea to [itex]I[/itex], and this is what you're referring to by an ordering of [itex]I[/itex]. This confused me in my last response as there is another notion of an ordered set which is a little different. In any case, I don't think the way you want to do it will work, because the standard ordered pair construction does not extend easily to the infinite case, in fact, in the infinite case you define them to be special kinds of functions.

    I wouldn't worry about it, if you understand how the permutation based formulation works you should move on.
  8. Jun 2, 2012 #7
    Thanks very much dcpo. Makes a lot of sense.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook