Definition 12 (Disjoint). X and Y are disjoint when X ∩ Y = ∅.
17Disjointness
Two sets are disjoint when they have no elements in common at all:
The paradigm case is a set and its complement. Proposition 31 (a set and its complement are disjoint) tells us that X and Xc are disjoint, and Proposition 30 (a set and its complement exhaust the domain) that between them they take up the whole of U.
Splitting a set into disjoint pieces can be useful in certain contexts, so it’s worth getting used to doing it. The reason is that pieces which do not overlap can be counted or measured separately without anything being counted twice.
Taking a relative complement is the basic way of producing a pair of disjoint sets.
Proposition 39 (a set is disjoint from what is taken off another). For any sets X and Y, X and Y ∖ X are disjoint.
Suppose for contradiction that there is some x ∈ X ∩ (Y ∖ X). Then we have x ∈ X by the definition of intersection and x ∉ X by the definition of intersection and relative complement. These two statements are contradictory.
Disjointness is also inherited by subsets: if two sets do not overlap, then neither do any smaller sets taken from them.
Proposition 40 (disjointness passes to subsets). For any sets X, Y and Z, if X and Y are disjoint and Z ⊂ X, then Z and Y are disjoint.
Suppose that X and Y are disjoint and that Z ⊂ X. Since Z ⊂ X, Proposition 9 (intersection respects inclusion) gives us Z ∩ Y ⊂ X ∩ Y. But X ∩ Y = ∅, since X and Y are disjoint, so Z ∩ Y ⊂ ∅. By Proposition 6 (the only subset of ∅), then, Z ∩ Y = ∅; that is, Z and Y are disjoint.
The next three propositions give us ways of decomposing a set into two disjoint components. In the first two, the components are disjoint by Proposition 39 (a set is disjoint from what is taken off another). In the third they are disjoint by Propositions 39 (a set is disjoint from what is taken off another) and 40 (disjointness passes to subsets) together, since X ∩ Y ⊂ X.
Each of the propositions has a diagram to help you understand. In the first, X sits inside Y, and the two pieces are X itself and the ring around it.
Proposition 41 (splitting a set around a subset). For any sets X and Y, if X ⊂ Y, then Y = X ∪ (Y ∖ X).
Suppose that X ⊂ Y. We will show that Y = X ∪ (Y ∖ X) using Proposition 1 (double inclusion).
First, let us show that Y ⊂ X ∪ (Y ∖ X). Let y ∈ Y. By the law of excluded middle, either (i) y ∈ X or (ii) y ∉ X. Case (i): if y ∈ X, then y ∈ X ∪ (Y ∖ X) by the definition of union. Case (ii): if y ∉ X, then y ∈ Y ∖ X by the definition of relative complement; hence y ∈ X ∪ (Y ∖ X) by the definition of union.
Next we will show that X ∪ (Y ∖ X) ⊂ Y. Suppose that x ∈ X ∪ (Y ∖ X). There are two cases: either (i) x ∈ X or (ii) x ∈ Y ∖ X. Case (i): if x ∈ X, then since X ⊂ Y we have x ∈ Y. Case (ii): if x ∈ Y ∖ X, then by definition of relative complement, x ∈ Y.
In the second, we take all of X and only the part of Y which is new.
Proposition 42 (splitting a union into disjoint pieces). For any sets X and Y, X ∪ Y = X ∪ (Y ∖ X).
Exercise 17. Prove Proposition 42 (splitting a union into disjoint pieces).
In the third, Y alone is cut into the part outside X and the part inside it.
Proposition 43 (splitting a set by another set). For any sets X and Y, Y = (Y ∖ X) ∪ (X ∩ Y).
Exercise 18. Prove Proposition 43 (splitting a set by another set).
One last fact about disjointness, which we will want later.
Proposition 44 (a union of sets disjoint from Z is disjoint from Z). For any sets X, Y and Z, if X and Z are disjoint and Y and Z are disjoint, then X ∪ Y and Z are disjoint.
By Proposition 23 (intersection distributes over union), (X ∪ Y) ∩ Z = (X ∩ Z) ∪ (Y ∩ Z). As X, Z and Y, Z are both disjoint pairs, X ∩ Z = Y ∩ Z = ∅, hence (X ∪ Y) ∩ Z = ∅ ∪ ∅. By Proposition 19 (uniting with the empty set), ∅ ∪ ∅ = ∅, therefore (X ∪ Y) and Z are disjoint.