Is Generalized version of associative law in Halmos’s set theory superfluous? How can we write a generalized commutative law

associativityset-theory

In Halmos's naive set theory, section 9 (families), page 35 there is a part about generalized version of the associative law. It reads as follows:

The algebraic laws satisfied by the operation of union for pairs can be generalized to arbitrary unions. Suppose, for instance, that $\{I_j\}$ is a family of of sets with domain $J$, say; write $K=\bigcup\limits_j{I_j}$, and let ${A_k}$ be a family of sets with domain $K$. It is then not difficult to prove that $$\bigcup_{k\in K} A_k = \bigcup\limits_{j \in J}\bigg(\bigcup\limits_{i \in I_j} A_i\bigg);(1)$$this is the generalized version of the associative law for unions. Exercise: formulate and prove the a generalized version of the commutative law.

I have read some of other questions in stackexchange regarding this part of halmos's book like:

  1. A help to understand the generalized version of the associative law of union

  2. Associativity with families in Halmos' Naive Set Theory

  3. Generalized associative law

  4. The analogous generalization for the commutativity of unions.

I know that from formula $(1)$ we can conclude that $A_0 \cup A_1 \cup A_2 = A_0 \cup (A_1 \cup A_2) = (A_0 \cup A_1)\cup A_2$

My question is about whether such formulation of associative law in formula (1) is necessary at all or it is superfluous..

Halmos in section 4 defines union of a colloction of sets $\mathfrak{C}$ as the set $U=\{x: x\in X\ for\ some\ X\ in\ \mathfrak{C}\}$ and he says that by the axiom of unions $U$ exists and by the axiom of specification $U$ is unique.

A collection of sets is a set of sets and there is no notion of order in a set. So the sets that are in a collection can be ordered arbitrarily. When defining union we say "if there exists something in the collection" so writing formulas about associativity and commutativity and proving them seems unnecessary and irrelevant to me. We can see associativity and commutativity just from the definition of union because you can write for example $\{A_0, A_1\} = \{A_1,A_0\}$ which proves commutativity of union of two sets and for associativity it is obvious. For example when you say a red ball exists in a bag of balls, it is obvious that if you shake the bag and the position of balls change without removing any ball from the bag then for sure there is a red ball in the bag after shaking.

I don't say we should not write any proof. I mean that writing a general formula for associativity is irrelevant because when you write $\bigcup\limits_{k\in K} A_k$ and say $K = \{0,1,2,3\}$, how am I supposed to order $A_k$? There is no order.

My second question: How do you formulate commutativity?

Best Answer

Generally speaking, associativity means instead of calculating the union from the main index set, we can break the main index set into a family of smaller index sets and calculate union for every smaller index set and then calculate the union of all the unions of the smaller index sets.

Actually there is no order in computing $\bigcup\limits_{k\in K} A_k$ and $\bigcup\limits_{j \in J}\bigg(\bigcup\limits_{i \in I_j} A_i\bigg)$.

The only order is that for the second formula you must first compute the inner parenthesis. I explain what the formula says by an example.

Suppose $K=\{a, 1, *\}$

$A_a = \{p,q,r\}$

$A_1=\{q,r,s\}$

$A_*=\{s,t\} $

Then you compute $\bigcup\limits_{k\in K} A_k = \bigcup\{A_a,A_1,A_*\}$ by definition and you get $\{p,q,r,s,t\}$ as the union of the collection $\{A_a,A_1,A_*\}$ and obviously there is no order. But you can compute the union another way. You can break the set $K$ into a collection of sets:

Suppose $J=\{11, 12\}$

$I_{11} = \{a, 1\}$

$I_{12} = \{*,1\}$

So now $K = \bigcup_{j \in J} I_j=\bigcup\{I_{11},I_{12}\}=\{a,1,*\}$

and we can compute $\bigcup\limits_{j \in J}\bigg(\bigcup\limits_{i \in I_j} A_i\bigg) = \bigcup \bigg\{\bigcup\limits_{i \in I_{11}}A_i,\bigcup\limits_{i \in I_{12}}A_i\bigg\} = \bigcup\bigg\{\bigcup\{A_a,A_1\},\bigcup\{A_*,A_1\}\bigg\} = \bigcup\bigg\{\{p,q,r,s\},\{q,r,s,t\}\bigg\}=\{p,q,r,s,t\}$

As for the question about commutativity, I think general commutativity means that in a family of sets if we change the function that associates a set to every index, then the union is not altered. For example:

$I = \{0,1,2\}$ is the index set

$B_0=\{a,b\}$

$B_1=\{b,c\}$

$B_2=\{e,f\}$

Now $\bigcup\limits_{i\in I}B_i = \bigcup\bigg\{B_0,B_1,B_2\bigg\}$

If we change the index function, for example by changing the sets of $B_0$ and $B_1$ with each other we get:

$B_0=\{b,c\}$

$B_1=\{a,b\}$

$B_2=\{e,f\}$

and the corresponding union does not change. Mathematically, If $\sigma$ is a permutation on the index set $I$ then $$\bigcup\limits_{k\in K} B_k=\bigcup\limits_{k\in K} B_{\sigma(k)}$$

I wrote about commutativity by getting help from question number 4 in the list of questions I have studied in this website about the topic.

Finally I think it only means to talk about associativity and commutativity when we have a family, namely an indexed collection and as Halmos says every collection can be indexed and the index set can be simply the collection and the function is the identity function. So talking about associativity and commutativity and formulating them and proving them is not irrelevant.

Related Question