5  Complements and Powers

If \(A\) and \(B\) are sets, the difference between \(A\) and \(B\), more often known as the relative complement of \(B\) in \(A\), is the set \(A - B\) defined by

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

Note that in this definition it is not necessary to assume that \(B \subset A\). In order to record the basic facts about complementation as simply as possible, we assume nevertheless (in this section only) that all the sets to be mentioned are subsets of one and the same set \(E\) and that all complements (unless otherwise specified) are formed relative to that \(E\). In such situations (and they are quite common) it is easier to remember the underlying set \(E\) than to keep writing it down, and this makes it possible to simplify the notation. An often used symbol for the temporarily absolute (as opposed to relative) complement of \(A\) is \(A'\). In terms of this symbol the basic facts about complementation can be stated as follows:

\[(A')' = A,\] \[\emptyset' = E, \: E' = \emptyset,\] \[A \cap A' = \emptyset, \: A \cup A' = E,\] \[A \subset B \mathit{\ if\ and\ only\ if\ } B' \subset A'.\]

The most important statements about complements are the so-called De Morgan laws:

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

(We shall see presently that the De Morgan laws hold for the unions and intersections of larger collections of sets than just pairs.) These facts about complementation imply that the theorems of set usually come in pairs. If in an inclusion equation involving unions, intersections, and complements of subsets of \(E\) we replace each set by its complement, interchange unions and intersections, and reverse all inclusions, the result is another theorem. This fact is sometimes referred to as the principle of duality for sets.

Here are some easy exercises on complementation.

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

If \(A\) and \(B\) are sets, the symmetric difference (or Boolean sum of \(A\) and \(B\) is the set \(A + B\) defined by

\[ A + B = (A - B) \cup (B - A). \]

This operation is commutative \((A + B = B + A)\) and associative \((A + (B + C) = (A + B) + C)\), and is such that \(A + \emptyset = A\) and \(A + A = \emptyset\).

This may be the right time to straighten out a trivial but occasionally puzzling part of the theory of intersections. Recall, to begin with, that intersections were defined for non-empty collections only. The reason is that the same approach to the empty collection does not define a set. Which \(x\)’s are specified by the sentence

\[ x \in X \mathit{\ for\ every\ } X \mathit{\ in\ } \emptyset ? \]

As usual for questions about \(\emptyset\) the answer is easier to see for the corresponding negative question. Which \(x\)’s do not satisfy the stated condition? If it is not true that \(x \in X\) for every \(X\) in \(\emptyset\), then there must exist an \(X\) in \(\emptyset\) such that \(x \notin X\); since, however, there do not exist any \(X\)’s in \(\emptyset\) at all, this is absurd. Conclusion: no \(x\) fails to satisfy the stated condition, or, equivalently, every \(x\) does satisfy it. In other words, the \(x\)’s that the condition specifies exhaust the (nonexistent) universe. There is no profound problem here; it is merely a nuisance to be forced always to be making qualifications and exceptions just because some set somewhere along some construction might turn out to be empty. There is nothing to be done about this; it is just a fact of life.

If we restrict our attention to subsets of a particular set \(E\), as we have temporarily agreed to do, then the unpleasantness described in the preceding paragraph appears to go away. The point is that in that case we can define the intersection of a collection \(\mathcal{C}\) (of subsets of \(E\)) to be the set

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

This is nothing revolutionary; for each non-empty collection, the new definition agrees with the old one. The difference is in the way the old and the new definitions treat the empty collection; according to the new definition \(\bigcap_{X \in \emptyset} X\) is equal to \(E\). (For which elements \(x\) of \(E\) can it be false that \(x \in X\) for every \(X\) in \(\emptyset\)?) The difference is just a matter of language. A little reflection reveals that the “new” definition offered for intersection of a collection \(\mathcal{C}\) of subsets of \(E\) is really the same as the old definition of the intersection of the collection \(\mathcal{C} \cup \{ E \}\), and the latter is never empty.

We have been considering the subsets of a set \(E\); do those subsets themselves constitute a set? The following principle guarantees that the answer is yes.

Axiom 5.1 (Axiom of powers) For each set there exists a collection of sets that contains among its elements all the subsets of the given set.

In other words, if \(E\) is a set, then there exists a set (collection) \(\mathcal{P}\) such that if \(X \subset E\), then \(X \in \mathcal{P}\).

The set \(\mathcal{P}\) described above may be larger than wanted; it may contain elements other than subsets of \(E\). This is easy to remedy; just apply the axiom of specification to form the set \(\{ X \in \mathcal{P}: X \subset E \}\). (Recall that “\(X \subset E\)” says the same thing as “\(\mathit{\ for\ all\ x\ (if\ } x \in X \mathit{\ then\ } x \in E)\).”) Since, for every \(X\), a necessary and sufficient condition that \(X\) belong to this set is that \(X\) be a subset of \(E\), it follows that if we change notation and call this set \(\mathcal{P}\) again, then

\[ \mathcal{P} = \{ X : X \subset E \}. \]

The set \(\mathcal{P}\) is called the power set of \(E\); the axiom of extension guarantees its uniqueness. The dependence of \(\mathcal{P}\) on \(E\) is denoted by writing \(\mathcal{P}(E)\) instead of just \(\mathcal{P}\).

Because the set \(\mathcal{P}(E)\) is very big in comparison with \(E\), it is not easy to give examples. If \(E = \emptyset\), the situation is clear enough; the set \(\mathcal{P}(\emptyset)\) is the singleton \(\{ \emptyset \}\). The power sets of singletons and pairs are also easily describable; we have

\[ \mathcal{P} ( \{ a \} ) = \{ \emptyset, \{ a \} \} \]

and

\[ \mathcal{P} ( \{ a, b \} ) = \{ \emptyset, \{ a \} , \{ b \} , \{ a,b \} \}. \]

The power set of a triple has eight elements. The reader can probably guess (and is hereby challenged to prove) the generalization that includes all these statements: the power set of a finite set with, say, \(n\) elements has \(2^n\) elements. (Of course concepts like “finite” and “\(2^{n}\)” have no official standing for us yet; this should not prevent them from being unofficially understood.) The occurrence of \(n\) as an exponent (the \(n\)-th power of 2) has something to do with the reason why power set bears its name.

If \(\mathcal{C}\) is a collection of subsets of a set \(E\) (that is, \(\mathcal{C}\) is a subcollection of \(\mathcal{P}(E)\)), then write

\[ \mathcal{D} = \{ X \in \mathcal{P}(E): X' \in \mathcal{C} \}. \]

(To be certain that the condition used in the definition of \(\mathcal{D}\) is a sentence in the precise technical sense, it must be rewritten in something like the form

\[ \mathit{for\ some\ Y\ } [Y \in \mathcal{C} \mathit{\ and\ for\ all\ x\ } ( x \in X \mathit{\ if\ and\ only\ if\ } (x \in E \mathit{\ and\ } x \notin Y))]. \]

Similar comments often apply when we wish to use defined abbreviations instead of logical and set-theoretic primitives only. The translation rarely requires any ingenuity and we shall usually omit it.) It is customary to denote the union and the intersection of the collection \(\mathcal{D}\) by the symbols

\[ \bigcup_{X \in \mathcal{C}} X' \mathit{\ and\ } \bigcap_{X \in \mathcal{C}} X'. \]

In this notation the general forms of the De Morgan laws become

\[ \left( \bigcup_{X \in \mathcal{C}} X \right)' = \bigcap_{X \in \mathcal{C}} X' . \]

and

\[ \left( \bigcap_{X \in \mathcal{C}} X \right)' = \bigcup_{X \in \mathcal{C}} X'. \]

The proofs of these equations are immediate consequences of the appropriate definitions.

Exercise 5.1 Prove that \(\mathcal{P}(E) \cap \mathcal{P}(F) = \mathcal{P}(E \cap F)\) and \(\mathcal{P}(E) \cup \mathcal{P}(F) \subset \mathcal{P}(E \cup F)\). These assertions can be generalized to

\[ \bigcap_{X \in \mathcal{C}} \mathcal{P} (X) = \mathcal{P} \left( \bigcap_{X \in \mathcal{C}} X \right) \]

and

\[ \bigcup_{X \in \mathcal{C}} \mathcal{P}(X) \subset \mathcal{P} \left( \bigcup_{X \in \mathcal{C}} X \right); \]

find a reasonable interpretation of the notation in which these generalizations were here expressed and then prove them. Further elementary facts:

\[ \bigcap_{X \in \mathcal{P}(E)} X = \emptyset, \]

and

\[ \mathit{if\ } E \subset F, \mathit{\ then\ } \mathcal{P}(E) \subset \mathcal{P}(F). \]

A curious question concerns the commutativity of the operators \(\mathcal{P}\) and \(\bigcup\). Show that \(E\) is always equal \(\bigcup_{X \in \mathcal{P}(E)} X\) (that is \(E = \bigcup \mathcal{P}(E)\)), but that the result of applying \(\mathcal{P}\) and \(\bigcup\) to \(E\) in the other order is a set that includes \(E\) as a subset, typically a proper subset.