We are now ready to discuss a couple of familiar set theoretic operations: unions and intersections. Given two sets A and B, it would be “nice” to have a set U that contains all the elements that belong to at least one of A or B. In fact, it would be nicer to generalize this to a collection of sets instead of just two, though we must be careful about using words like “two”, “three” and so on, since we haven’t really defined what numbers are so far. We don’t want to run the risk of inadvertently introducing circularity in our arguments! Anyway, this brings us to the following axiom.

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.

In other words, for every collection C, there exists a set U such that if x \in X for some X in C, then x \in U. Now, the set U may contain “extra” elements that may not belong to any X in C. This can be easily fixed by invoking the axiom of specification to form the set \{ x \in U: x \in X \mbox{ for some } X \mbox{ in } C \}. This set is called the union of the collection C of set. Its uniqueness is guaranteed by the axiom of extension.

Generally, if C is a collection of sets, then the union is denoted by \bigcup \{  X: X \in C \}, or \bigcup_{X \in C} X.

A quick look at a couple of simple facts.

1) \bigcup \{  X: X \in \emptyset \} = \emptyset, and

2) \bigcup \{  X: X \in \{ A \} \} = A.

We finally arrive at the definition of the union of two sets, A and B. A \cup B = \{ x: x \in A \mbox{ or } x \in B \}.

Below is a list of a few facts about unions of pairs:

  • A \cup \emptyset = A,
  • A \cup B = B \cup A (commutativity),
  • A \cup ( B \cup C) = (A \cup B) \cup C (associativity),
  • A \cup A = A (idempotence),
  • A \subset B if and only if A \cup B = B.

Now, we define the intersection of two sets, A and B as follows.

A \cap B = \{ x: x \in A \mbox{ and } x \in B\}.

Once again, a few facts about intersections of pairs (analogous to the ones involving 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 if and only if A \cap B = A.

Also, if A \cap B = \emptyset, then the sets A and B are called disjoint sets.

Two useful distributive laws involving unions and intersections:

  • A \cap (B \cup C) = (A \cap B) \cup (A \cap C),
  • A \cup (B \cap C) = (A \cup B) \cap (A \cup C).

We prove the first one of the above. The proof of the second one is left as an exercise to the reader. The proof relies on the idea that we show each side is a subset of the other. So, suppose x belongs to the left hand side; then x \in A and x \in B \cup C, which implies x \in A and x \in B or C, which implies x \in A \cap B or x \in A \cap C, which implies x \in (A \cap B) \cup (A \cap C); hence x belongs to the right hand side. This proves that the left hand side is a subset of the right hand side. A similar argument shows that the right hand side is a subset of the left hand side. And, we are done.

The operation of the intersection of sets from a collection, C, is similar to that of the union of sets from C. However, the definition will require that we prohibit C from being empty, and we will see why in the next section. So, for each collection, C, there exists a set V such that x \in V if and only if x \in X for every X in C. To construct such a set V, we choose any set A in C – this is possible because C \not= \emptyset – and write \{ x \in A: x \in X \mbox{ for all } X \mbox{ in } C\}.

Note that the above construction is only used to prove that V exists. The existence of V doesn’t depend on any arbitrary set A in the collection C. We can, in fact, write

\{ x: x \in X \mbox{ for all } X \mbox{ in } C\}.

The set V is called the intersection of the collection C of sets. The axiom of extension, once again, guarantees its uniqueness. The usual notation for such a set V is \bigcap \{ X: X \in C \} or \bigcap_{X \in C} X.

EXERCISE: (A \cap B) \cup C = A \cap (B \cup C) if and only if C \subset A.

SOLUTION: We first prove the “if” part. So, suppose C \subset A. Now, if x \in (A \cap B) \cup C, then either x \in A \cap B or x \in C. In the first case, x \in A and x \in B, which implies x \in A and x \in B \cup C. In the second case, we again have x \in A (since C \subset A), which implies x \in A and x \in B \cup C. In either case, we have x \in A \cap (B \cup C). Hence, (A \cap B) \cup C is a subset of A \cap (B \cup C).

Similarly, if x \in A \cap (B \cup C), then x \in A and x \in B \cup C. Now, if x \in B, then x \in A \cap B, which implies x \in (A \cap B) \cup C. And, if x \in C, then once again x \in (A \cap B) \cup C. Thus, in either case, x \in (A \cap B) \cup C. Hence, A \cap (B \cup C) is a subset of (A \cap B) \cup C. We, thus, proved (A \cap B) \cup C = A \cap (B \cup C). This concludes the proof of the “if” part.

Now, we prove the “only if” part. So, suppose (A \cap B) \cup C = A \cap (B \cup C). If x \in C, then x belongs to the left hand side of the equality, which implies x belongs to the right hand side. This implies x \in A (and x \in B \cup C.) Hence, C \subset A. And, we are done.

About these ads