The difference between sets A and B, also known as the relative complement of B in A, is the set A - B defined by

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

If we assume the existence of a universe, U, such that all the sets are subsets of U, then we can considerably simplify our notation. So, for instance, U - B can simply be written as B', which denotes the complement of B in U. Similarly, U' = U - U = \emptyset \,, \emptyset ' = U - \emptyset = U, and so on. A quick look at a few more facts:

  • (A')' = A,
  • A \cap A' = \emptyset,
  • A \cup A' = U
  • A \subset B if and only if B' \subset A'.

The last one is proved as follows. We prove the “if” part first. Suppose B' \subset A'. If x \in A, then clearly x \not\in A'. But, since B' \subset A', we have x \not\in B', which implies x \in B. Hence, A \subset B. This closes the proof of the “if” part. Now, we prove the “only if” part. So, suppose A \subset B. Now, if x \in B', then clearly x \not\in B. But, since A \subset B, we have x \not\in A, which implies x \in A'. Hence, B' \subset A'. This closes the proof of the “only if” part, and, we are done.

The following are the well-known DeMorgan’s laws (about complements):

(A \cup B)' = A' \cap B', and (A \cap B)' = A' \cup B'.

Let’s quickly prove the first one. Suppose x belongs to the left hand side. Then, x \not\in A \cup B, which implies x \not\in A and x \not\in B, which implies x \in A' and x \in B', which implies x \in A' \cap B'. This proves that the left hand side is a subset of the right hand side. We can similarly prove the right hand side is a subset of the left hand side, and this closes our proof.

Though it isn’t very apparent, but if we look carefully at the couple of problems whose proofs we did above, we note something called the principle of duality for sets. One encounters such dual principles in mathematics quite often. In this case, this dual principle is stated a follows.

Principle of duality (for sets): If in an inclusion or equation involving unions, intersections and complements of subsets of U (the universe) we replace each set by its complement, interchange unions and intersections, and reverse all set-inclusions, the result is another theorem.

Using the above principle, it is easy to “derive” one of the DeMorgan’s laws from another and vice versa. In addition, DeMorgan’s laws can be extended to larger collections of sets instead of just pairs.

Here are a few exercises on complementation.

  1. A - B = A \cap B',
  2. A \subset B if and only if A - B = \emptyset,
  3. A - (A - B) = A \cap B,
  4. A \cap (B - C) = (A \cap B) - (A \cap C),
  5. A \cap B \subset (A \cap B) \cup (A \cap C),
  6. (A \cup C) \cap (B \cup C') \subset A \cup B.

 

We will prove the last one, leaving the remaining as exercises to the reader. Suppose x belongs to the left hand side. Then, x \in A \cup C and x \in B \cup C'. Now, note that if x \in C, then x \not\in C', which implies x \in B, which implies x \in A \cup B. If, on the other hand, x \in C', then x \not\in C, which implies x \in A, which implies x \in A \cup B. Hence, in either case, the left hand side is a subset of A \cup B, and we are done.

We now define the symmetric difference (or Boolean sum) of two sets A and B as follows:

A \triangle B = (A-B) \cup (B-A).

This is basically the set of all elements in A or B but not in A \cap B. In other words, A \triangle B = (A \cup B) - (A \cap B). Again, a few facts (involving symmetric differences) that aren’t hard to prove:

  1. A \triangle \emptyset = A,
  2. A \triangle A = \emptyset,
  3. A \triangle B = B \triangle A (commutativity),
  4. (A \triangle B) \triangle C = A \triangle (B \triangle C) (associativity),
  5. (A \triangle B) \triangle (B \triangle C) = A \triangle C,
  6. A \cap (B \triangle C) = (A \cap B) \triangle (A \cap C).

This brings us now to the axiom of powers, which basically states if E is a set then there exists a set that contains all the possible subsets of E as its elements.

Axiom of powers: If E is a set, then there exists a set (collection) P, such that if X \subset E, then X \in P.

The set P, described above, may be too “comprehens ive”, i.e., it may contain sets other than the subsets of E. Once again, we “fix” this by applying the axiom of specification to form the new set P = \{ X: X \subset E \}. The set P is called the power set of E, and the axiom of extension, again, guarantees its uniqueness. We denote P by P(E) to show the dependence of P on E. A few illustrative examples: P(\emptyset) = \{ \emptyset \}, P(\{ a \}) = \{ \emptyset, \{ a \} \}, P(\{ a, b \}) = \{ \emptyset, \{ a \}, \{ b \}, \{ a, b \} \}, and so on.

Note that if E is a finite set, containing n elements, then the power set P(E) contains 2^n elements. The “usual” way to prove this is by either using a simple combinatorial argument or by using some algebra. The combinatorial argument is as follows. An element in E either belongs to a subset of E or it doesn’t: there are thus two choices; since there are n elements in E, the number of all possible subsets of E is therefore 2^n. A more algebraic way of proving the same result is as follows. The number of subsets with k elements is \binom{n}{k}. So, the number of subsets of E is \sum_{k=0}^{n}\binom{n}{k}. But, from the binomial theorem, we have \displaystyle (1 + x)^n = \sum_{k=0}^{n}\binom{n}{k}x^k. Putting x = 1, we get 2^n as our required answer.

A few elementary facts:

  1. \bigcap_{X \in P(E)} X = \emptyset.
  2. If E \subset F, then P(E) \subset P(F).
  3. E = \bigcup P(E) .

EXERCISES:

1. Prove that P(E) \bigcap P(F) = P(E \bigcap F).

2. Prove that P(E) \bigcup P(F) \subset P(E \bigcup F).

 

 

 

 

 

 

 

 

 

 

Advertisements