Definition 11 (Complement). Where a domain U is understood and X ⊂ U, the complement of X is Xc = U ∖ X.
16Complements
In some contexts there is tacitly a domain: a largest set which everything we are discussing belongs to. If we are thinking about sets of real numbers, the domain might be ℝ; if we are doing probability theory, it might be the universal event containing all the possible outcomes.
When a domain U is understood, we write Xc as a shorthand for U ∖ X, and we call it simply the complement of X. So the inclusion criterion for Xc is x ∈ U and x ∉ X. Nothing here is new: Xc is the complement of X in U, with the domain left implicit:
In Figure 14, the rectangle is U and the shaded region is Xc.
Throughout this section, X and Y are subsets of U.
Proposition 30 (a set and its complement exhaust the domain). X ∪ Xc = U.
We will apply Proposition 1 (double inclusion). For the first inclusion: we have already X ⊂ U, and it is clear from the definition that Xc ⊂ U. Hence, by Proposition 21 (the union is the smallest set containing both), X ∪ Xc ⊂ U.
For the second inclusion: suppose that x ∈ U. By the law of excluded middle, either x ∈ X or x ∉ X. In the former case, x ∈ X, hence x ∈ X ∪ Xc by Proposition 15 (each set is a subset of the union). In the latter case, x ∈ U and x ∉ X, hence x ∈ Xc, and by Proposition 15 (each set is a subset of the union) x ∈ X ∪ Xc. Therefore U ⊂ X ∪ Xc.
Proposition 31 (a set and its complement are disjoint). X ∩ Xc = ∅.
We will show by contradiction that there are no elements of X ∩ Xc. Suppose there were some such element x. Then, by the definition of intersection and the inclusion criteria for X and Xc, we have x ∈ X and x ∉ X; a contradiction.
Now try and prove the next three propositions yourself:
Proposition 32 (the complement of a complement). (Xc)c = X.
Exercise 13. Prove Proposition 32 (the complement of a complement).
Proposition 33 (the complement of the empty set). ∅c = U.
Exercise 14. Prove Proposition 33 (the complement of the empty set).
Proposition 34 (the complement of the domain). Uc = ∅.
Exercise 15. Prove Proposition 34 (the complement of the domain).
Once a domain has been fixed, a relative complement can always be rewritten using the complement.
Proposition 35 (relative complement via complement). X ∖ Y = X ∩ Yc.
The inclusion criterion for X ∖ Y is x ∈ X and x ∉ Y. The inclusion criterion for X ∩ Yc is x ∈ X and x ∈ U and x ∉ Y. Since X ⊂ U, we have x ∈ X if and only if x ∈ X and x ∈ U by Proposition 14 (inclusion via intersection). Hence the two inclusion criteria are equivalent.
The next two results are named after the nineteenth-century mathematician Augustus De Morgan. They say that taking a complement turns intersection into union, and union into intersection. The shaded region in Figure 15 is everything outside X ∩ Y. Reading it as one region gives (X ∩ Y)c; reading it as everything outside X together with everything outside Y gives Xc ∪ Yc.
Proposition 36 (De Morgan, for intersection). (X ∩ Y)c = Xc ∪ Yc.
We will prove this by showing that the inclusion criteria are logically equivalent.
The inclusion criterion for the set (X ∩ Y)c is x ∈ U and x ∉ X ∩ Y. Unpacking this further by the definition of intersection, the criterion is that (i) x ∈ U and (ii) it is not the case that x is in both X and Y. Equivalently, x is in U and either (i) x is not in X, or (ii) x is not in Y.
The inclusion criterion for the set Xc ∪ Yc is that x is in either Xc or Yc. Thus, either (i) x is in U, but not in X, or (ii) x is in U, but not in Y. Equivalently, x is in U and either (i) x is not in X, or (ii) x is not in Y. But we have seen already that this is the same as the inclusion criterion for (X ∩ Y)c.
Notice that we tacitly helped ourselves to the corresponding logical De Morgan law here, stating that ¬(X ∧ Y) is logically equivalent to ¬ X ∨ ¬ Y. This can be broken down and proved from more basic logical steps; see any introductory logic textbook for the details. For our purposes here, since it’s part of classical logic, we can simply make the move in one go without further explanation.
Now see if you can prove the dual De Morgan law yourself:
Proposition 37 (De Morgan, for union). (X ∪ Y)c = Xc ∩ Yc.
Exercise 16. Prove Proposition 37 (De Morgan, for union).
One more useful fact is that complements reverse the direction of the subset relation.
In Figure 17, Xc is shaded and Yc is shaded twice, so Yc lies inside Xc even though X lies inside Y.
Proposition 38 (complements reverse inclusion). X ⊂ Y if and only if Yc ⊂ Xc.
Left to right: suppose that X ⊂ Y. If it were not the case that Yc ⊂ Xc, then there would be some x which belongs to Yc but not to Xc. In that case, we would have x ∈ X but x ∉ Y, contradicting that X ⊂ Y.
Right to left: this follows from the previous step of the argument if we apply Proposition 32 (the complement of a complement). (Do you see why?)