4 Unions and Intersections

If \(A\) and \(B\) are sets, it is sometimes natural to wish to unite their elements into one comprehensive set. One way of describing such a comprehensive set is to require it to contain all the elements that belong to at least one of the two members of the pair \(\{ A, B \}\). This formulation suggests a sweeping generalization of itself; surely a similar construction should apply to arbitrary collections of sets and not just to pairs of them. What is wanted, in other words, is the following principle of set construction.

Axiom 4.1 (Axiom of unions) For every collection of sets there exists a set that contains all the elements that belong to at least one set of the given collection.

Here it is again: for every collection \(\mathcal{C}\) there exists a set \(U\) such that if \(x \in X\) for some \(X\) in \(\mathcal{C}\), then \(x \in U\). (Note that “at least one” is the same as “some.”)

The comprehensive set \(U\) described above may be too comprehensive; it may contain elements that belong to none of the sets \(X\) in the collection \(\mathcal{C}\). This is easy to remedy; just apply the axiom of specification to form the set

\[ \{ x \in U: x \in X \mathit{\ for\ some\ } X \mathit{\ in\ } \mathcal{C} \}. \]

(The condition here is a translation into idiomatic usage of the mathematically more acceptable “for some \(X\ (x \in X \mathit{\ and\ } X \in \mathcal{C})\).”) It follows that, for every \(x\), a necessary and sufficient condition that \(x\) belong to this set is that \(x\) belong to \(X\) for some \(X\) in \(\mathcal{C}\). If we change notation and call the new set \(U\) again, then

\[ U = \{ x: x \in X \mathit{\ for\ some\ } X \mathit{\ in\ } \mathcal{C} \}. \]

This set \(U\) is called the union of the collection \(\mathcal{C}\) of sets; note that the axiom of extension guarantees its uniqueness. The simplest symbol for \(U\) that is in use at all is not very popular in mathematical circles; it is

\[ \bigcup \mathcal{C}. \]

Most mathematicians prefer something like

\[ \bigcup \{ X: X \in \mathcal{C} \} \]

\[ \bigcup_{X \in \mathcal{C}} X. \]

Further alternatives are available in certain important special cases; they will be described in due course.

For the time being we restrict our study of the theory of unions to the simplest facts only. The simplest fact of all is that

\[ \bigcup \{ X: X \in \emptyset \} = \emptyset, \]

and the next simplest fact is that

\[ \bigcup \{ X: X \in \{ A \} \} = A. \]

In the brutally simple notation mentioned above these facts are expressed by

\[ \bigcup \emptyset = \emptyset \]

and

\[ \bigcup \{ A \} = A. \]

The proofs are immediate from the definitions.

There is a little more substance in the union of pairs of sets (which is what started this whole discussion anyway). In that case special notation is used:

\[ \bigcup \{ X: X \in \{A, B \} \} = A \cup B. \]

The general definition of unions implies in the special case that \(x \in A \cup B\) if and only if \(x\) belongs to either \(A\) or \(B\) or both; it follows that

\[ A \cup B = \{x: x \in A \mathit{\ or\ } x \in B \}. \]

Here are some easily proved facts about the unions of pairs:

\[ A \cup \emptyset = A, \] \[ A \cup B = B \cup A \ (commutatitivity), \] \[ A \cup (B \cup C) = (A \cup B) \cup C \ (associativity), \] \[ A \cup A = A \ (idempotence), \] \[ A \subset B \mathit{\ if\ and\ only\ if\ } A \cup B = B. \]

Every student of mathematics should prove these things for himself at least once in his life. The proofs are based on the corresponding elementary properties of the logical operator or.

An equally simple but quite suggestive fact is that

\[ \{ a \} \cup \{ b \} = \{ a, b \}. \]

What this suggests is the way to generalize pairs. Specifically, we write

\[ \{ a, b, c \} = \{ a \} \cup \{ b \} \cup \{ c \}. \]

The equation defines its left side. The right side should by rights have at least one pair of parentheses in it, but, in view of the associative law, their omission can lead to no misunderstanding. Since it is easy to prove that

\[ \{ a, b, c \} = \{ x: x = a \ or \ x = b \: or \: x = c \}, \]

we know now that for every three sets there exists a set that contains them and nothing else; it is natural to call that uniquely determined set the (unordered) triple formed by them. The extension of the notation and terminology thus introduced to more terms (quadruples, etc.) is obvious.

The formation of unions has many points of similarity with another set-theoretic operation. If \(A\) and \(B\) are sets, the intersection of \(A\) and \(B\) is the set

\[ A \cap B \]

defined by

\[ A \cap B = \{ x \in A: x \in B \}. \]

The definition is symmetric in \(A\) and \(B\) even if it looks otherwise; we have

\[ A \cap B = \{ x \in B: x \in A \}, \]

and, in fact, since \(x \in A \cap B\) if and only if \(x\) belongs to both \(A\) and \(B\), it follows that

\[ A \cap B = \{x: x \in A \mathit{\ and\ } x \in B \}. \]

The basic facts about intersections, as well as their proofs, are similar to the basic facts about unions:

\[ A \cap \emptyset = \emptyset, \] \[ A \cap B = B \cap A, \] \[ A \cap (B \cap C) = (A \cap B) \cap C, \] \[ A \cap A = A, \] \[ A \subset B \mathit{\ if\ and\ only\ if\ } A \cap B = A. \]

Pairs of sets with an empty intersection occur frequently enough to justify the use of a special word: if \(A \cap B = \emptyset\), the sets \(A\) and \(B\) are called disjoint. The same word is sometimes applied to a collection of sets to indicate that any two distinct sets of the collection are disjoint; alternatively we may speak in such a situation of a pairwise disjoint collection.

Two useful facts about unions and intersections involve both the operations at the same time:

\[ A \cap (B \cup C) = (A \cap B) \cup (A \cap C), \] \[ A \cup (B \cap C) = (A \cup B) \cap (A \cup C). \]

These identities are called the distributive laws. By way of a sample of a set-theoretic proof, we prove the second one. If \(x\) belongs to the left side, then \(x\) belongs either to \(A\) or to both \(B\) and \(C\); if \(x\) is in \(A\), then \(x\) is in both \(A \cup B\) and \(A \cup C\), and if \(x\) is in both \(B\) and \(C\), then, again, \(x\) is in both \(A \cup B\) and \(A \cup C\); it follows that, in any case, \(x\) belongs to the right side. This proves that the right side includes the left. To prove the reverse inclusion, just observe that if \(x\) belongs to both \(A \cup B\) and \(A \cup C\), then \(x\) belongs either to \(A\) or to both \(B\) and \(C\).

The formation of the intersection of two sets \(A\) and \(B\), or, we might as well say, the formation of the intersection of a pair \(\{ A, B \}\) of sets, is a special case of a much more general operation. (This is another respect in which the theory of intersections imitates that of unions.) The existence of the general operation of intersection depends on the fact that for each non-empty collection of sets there exists a set that contains exactly those elements that belong to every set of the given collection. In other words: for each collection \(\mathcal{C}\), other than \(\emptyset\), there exists a set \(V\) such that \(x \in V\) if and only if \(x \in X\) for every \(X\) in \(\mathcal{C}\). To prove this assertion, let \(A\) be any particular set in \(\mathcal{C}\) (this step is justified by the fact that \(\mathcal{C} \neq \emptyset\)) and write

\[ V = \{ x \in A: x \in X \mathit{\ for\ every\ } X \mathit{\ in\ } \mathcal{C} \}. \]

(The condition means “for all \(X\) (if \(X \in \mathcal{C}\), then \(x \in X\)).”) The dependence of \(V\) on the arbitrary choice of \(A\) is illusory; in fact

\[ V = \{ x : x \in X \mathit{\ for\ every\ } X \mathit{\ in\ } \mathcal{C} \}. \]

The set \(V\) is called the intersection of the collection \(\mathcal{C}\) of sets; the axiom of extension guarantees its uniqueness. The customary notation is similar the one for unions: instead of the unobjectionable but unpopular

\[ \bigcap \mathcal{C}, \]

the set \(V\) is usually denoted by

\[ \bigcap \{ X : X \in \mathcal{C} \} \]

\[ \bigcap_{X \in \mathcal{C}} X. \]

Exercise 4.1 A necessary and sufficient condition that \((A \cap B) \cup C = A \cap (B \cup C)\) is that \(C \subset A\). Observe that the condition has nothing to do with the set \(B\).