Let $\{I_j\}$ be a family of sets indexed by $J$ and let $$K=\bigcup_{j\in J}I_j$$

Then let $\{A_k\}$ be a family of sets indexed by $K$. The generalization of the associative law for unions is that

$$\bigcup_{k\in K}A_k=\bigcup_{j\in J}\left(\bigcup_{i\in I_j}A_i \right)$$

What I interpret this as is: "To take the union over $K$, pick an $I_j \in K$, perform the union of all $A_i$ such that $i\in I_j$, and for each $j\in J$ unite all this possible unions to get $\bigcup_{k\in K}A_k$. What this is saying is that the order in which the $j$ and thus the $I_j$ are picked is of no importance in the ultimate union. The above is a generalization of $$(A\cup B)\cup C=A\cup (B\cup C)$$

How can I find the analogous generalization for $$A \cup B=B \cup A?$$

  • $\begingroup$ Maybe something along the lines of (possibly infinite) permutation groups. $\endgroup$ – user31373 Jul 14 '12 at 22:35

Let $K$ be an index set, and $S(K)$ be group of bijections from $K$ to $K$. Then one can say that for $\sigma\in S(K)$ and arbitrary family $\{A_k:k\in K\}$ we have $$ \bigcup\limits_{k\in K} A_k=\bigcup\limits_{k\in K} A_{\sigma(k)} $$

  • $\begingroup$ @PeterTamaroff, even if you intriduce new notation it still will be $O(K)=S(K)$. As for generalization it is possible but not necessary. $\endgroup$ – Norbert Jul 14 '12 at 22:44
  • $\begingroup$ Oh, right. Silly me. Thank you. $\endgroup$ – Pedro Tamaroff Jul 14 '12 at 22:45

Commutativity simply means that the order of operations is not important. One can see the obviousness of this claim for unions since: $$x\in\bigcup_{\lambda\in\Lambda}A_\lambda\iff\exists\lambda\in\Lambda:x\in A_\lambda$$

Now to say that the order does not matter is to say that if we shift the indices around (but do not remove any index!) then the result would be the same. Mathematically this translates to saying:

If $\sigma$ is any permutation of the index set $K$ then $$\bigcup_{k\in K}A_k=\bigcup_{k\in K}A_{\sigma(k)}$$

One last remark is that one should note that the axioms of ZF do not speak of $A\cup B$ directly, but rather $\bigcup\{A,B\}$, the set which is the union over the pair $\{A,B\}$.

In that aspect $\bigcup_{k\in K}A_k$ should be written as $\bigcup\{A_k\mid k\in K\}$, in which case it is obvious that any permutation of $K$ keeps the union the same, as the set over which we take the union remains the same.

  • $\begingroup$ Peter, if you prove that $\cal A_1=A_2$, then $\bigcup\cal A_1=\bigcup A_2$. If $S$ is any permutation of $K$ then $\{A_k\mid k\in K\}=\{A_k\mid k\in S(K)\}$. $\endgroup$ – Asaf Karagila Jul 14 '12 at 22:50
  • $\begingroup$ @Peter: However Norbert describes a set of permutations of $K$, so the index set is different, and thus the family itself may have changed. $\endgroup$ – Asaf Karagila Jul 14 '12 at 22:52
  • $\begingroup$ Because now your index set is different. Recall that writing $\{A_k\mid k\in K\}$ is to say "I have a function from $K$ into the universe" but now you want to say "I have a function from $S(K)$ into the universe" and there is no guarantee that the range of this function is the same. $\endgroup$ – Asaf Karagila Jul 14 '12 at 22:58
  • $\begingroup$ No, I cannot drop by the chat for a second. Let me clarify. The notation $\mathcal A=\{A_k\mid k\in K\}$ is to say $\mathcal A$ is the range of a function from $K$ into some power set, and $A_k$ is the image of $k$. Look at the comment you wrote, $k\in S(K)$. However $S(K)$ is a group of permutations of $K$, which is not $K$ at all. In fact it is usually of a much larger cardinality. So now you have a different function, which means that the sets may be different. All this, even though you use $A_k$ to denote your sets. Hooray for quantified variables! $\endgroup$ – Asaf Karagila Jul 14 '12 at 23:02
  • $\begingroup$ Yes, you misunderstood what $S(K)$ meant. Read Norbert's answer again. It says $S(K)$ a set of permutation of $K$, then for $\sigma\in S(K)$ ... the set $S(K)$ is a collection of functions, not the image of $K$ under some permutation. Note that my first reply assumed that you meant $S$ to be a specific permutation of $K$, but I figured that since you accepted his answer you read it too. :-) $\endgroup$ – Asaf Karagila Jul 14 '12 at 23:08

I'm trying to answer the question from the point of view of someone who has read just the Halmos' book up to the page 35 and doesn't have any other sources of knowledge about the Set Theory.

At first, let's make a more concise understanding of what we are trying to accomplish. It's important because I couldn't figure out the answer on the aforementioned question about the Associative Law by myself if there were no explanations in the related thread there.

So, the unions were introduced by the Axiom of Specification in the Section 4 of Halmos' book:

$$U = \{x: x \in X \text{ for some $X$ in $\mathfrak{C}$}\}$$ this set is called the union of the collection $\mathfrak{C}$ of sets

thus, being sets in the first place, "plain" unions of collections of sets don't have a notion of order in which we pick the unified sets and thus no property of commutativity.

The notion of commutativity appears when Halmos introduced the notation for the special case of a union of a pair of sets:

$$\bigcup\{X:X \in \{A, B\}\} = A \cup B$$

and when we use that notation, it follows from the definition that:

$$ A \cup B = B \cup A $$

Though we're asked by Halmos to generalize that idea using the notion of families of sets, it seems appealing to stop there and at first try to simply express the very same property of commutativity of pairs of sets using the notion of families of sets. It doesn't seem to be feasible though as the difference between $A \cup B$ and $B \cup A$ is purely notational. Those two notations correspond to the very same object of a union of pair of sets.

So the commutativity that Halmos is asking as to prove should be something else than the order in which we write the elements of the pair that we are applying the union operation to.

When we read the Section 4 further, we encounter the way to generalize pairs to define (unordered) triples, and, probably, n-tuples like

$$\{a, b, c\} = \{a\}\cup \{b\}\cup \{c\}$$

and it is here where we can find an "order" to apply the notion of "commutativity" to. It seems that we can list the singletons in the r.h.s. in any order and still obtain the same n-tuple in the l.h.s. provided the set of the singletons is the same. The "order" is defined by the left associativity of our $\cup$-notation for unions of pairs.

To concoct the generalized version that we're aiming for I used the example instance of it similar to the on provided by Brian M. Scott in the related thread:

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

the "generalization" means that this and similar equalities should hold as long as the "set" of the unified terms is $\{A_0, A_1, A_2\}$.

Up to the moment where the question appears there is only one place where "the order" is mentioned in the book which are sets of the form (it relates to the left hand side order of pair-unions in our example, so it is given a name): $$OrderSet_2 = \{\{2\}, \{2, 1\}, \{2, 1, 0\}\}$$ which, for instance defines "order" of $2-1-0$. The element which is the member of a singleton-element $\{2\}$ is the first element of the defined "order": $2$, by applying the similar procedure to the set of relative complements of other elements of the $OrderSet_2$ with the singleton: $$OrderSet_1 = \{\{1\}, \{1, 0\}\}$$ we obtain the next element of the order: $1$.

$OrderSet_2$ defines the order of commutations in a "reversed" way in a sense that the elements of it which come first correspond to the "outer" unified terms, i.e. the order of $$2-1-0$$ corresponds to the order of commutations: $$(A_0 \cup A_1) \cup A_2$$ We see that union-of-pair is an operation on two arguments so each union in our generalization will consist of just two terms. We are using the notation of families, so that each union will be represented as a union of a range of a family, hence terms united should correspond to the "terms" (according to the Halmos' terminology in the beginning of the chapter), and if we want to have two terms in each union, the index set of each family should contain two elements.

To start with, the resulting union (in the l.h.s.) $(A_0 \cup A_1) \cup A_2$ which we may denote as $U$ or also as $U_2$: $$U = U_2 = (A_0 \cup A_1) \cup A_2$$ is the union of the union denoted as $U_1$: $$U_1 = \bigcup_{X \in S_1}X \:\text{where}\: S_1 = \{A_0, A_1\}$$ and the set $A_2$ so $$U_2 = U_1 \cup A_2$$

We can express it in a form of a family with the domain $I_2$ that we can construct as consisting of two indices: $$I_2 = \{i_{A_2}, i_{U_1}\}$$ and the function (family in Halmos' terminology) $$X_2(i_{A_2}) = A_2 \quad X_2(i_{U_1}) = U_1$$ as: $$U_2 = \bigcup_{i \in I_2}{\{{X_2}_i\}}$$

we can express $U_1$ in a similar way (by an expense of introducing of more notation).

$U_1 = \bigcup_{X \in S_1}X$ where $S_1 = \{A_0, A_1\}$, thus it can be written as the union of the set denoted as $U_0$

$$U_0 = \bigcup_{X \in S_0}X \:\text{where}\: S_0 = \{A_0, \varnothing \}$$ and the set $A_1$ so $$U_1 = U_0 \cup A_1$$

We can express it in a form of a family with the domain $I_1$ that we can construct as consisting of two indices: $$I_1 = \{i_{A_1}, i_{U_0}\}$$ and the function $$X_1(i_{A_1}) = A_1 \quad X_1(i_{U_0}) = U_0$$ as: $$U_1 = \bigcup_{i \in I_1}{\{{X_1}_i\}}$$

Finally, in a similar way, the set $U_0 = \bigcup_{X \in S_0}X \:\text{where}\: S_0 = \{A_0, \varnothing \}$ can be constructed as a family with the domain $$I_0 = \{i_{A_0}, i_{\varnothing}\}$$ and the function $$X_0(i_{A_0}) = A_0 \quad X_0(i_{\varnothing}) = \varnothing$$ as: $$U_0 = \bigcup_{i \in I_0}{\{{X_0}_i\}}$$

Thus the construction of a family of sets $U = U_2$ seems to be finished. That family corresponded to a particular order of the union of pairs operation defined by the set $OrderSet_2$ in a way it was constructed which can be generalized as follows:

if $j$ is some "order set" which defines an order among the unified sets, $$U_{j} = \bigcup_{i \in I_j}\{{X_j}_i\}$$ where $$I_j = \{{i_U}_j, {i_A}_j\}$$ where the term $X_j({i_U}_j)$ is either "$U_{j-1}$" which is defined similarly based on the order set obtained by removing the singleton and the corresponding elements from the other sets of $j$ in a way $OrderSet_1$ was obtained from $OrderSet_2$ above, or $\varnothing$ if $j$ is the "last" order set to consider, i.e. is a singleton of a singleton.

the term $X_j({i_A}_j)$ is an element of a singleton of $j$ (the "first" element of a given order).

Using that generalization the statement of generalized commutativity of unions can be formulated like "unions obtained by the aforementioned procedure from any two order sets which define an order of elements of the same set are equal".


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.