Sets and Mathematical Proofs: A Primer

14Interactions between Unions and Intersections

So far we have taken union and intersection one at a time. When they are combined, each distributes over the other.

This is the first result which is genuinely hard to see just by reading the symbols, so here it is as a picture. On the left, we have shaded Y ∪ Z and then kept only the part inside X. On the right, we have shaded X ∩ Y and X ∩ Z separately. The two shaded regions are the same, and that is what the proposition says.

Proposition 23 (intersection distributes over union). For any sets X, Y and Z, X ∩ (Y ∪ Z) = (X ∩ Y) ∪ (X ∩ Z).

XYZ
XYZ
Figure 10. Proposition 23 (intersection distributes over union): X ∩ (Y ∪ Z) on the left, (X ∩ Y) ∪ (X ∩ Z) on the right.

We will show that (i) X ∩ (Y ∪ Z) ⊂ (X ∩ Y) ∪ (X ∩ Z), and then that (ii) (X ∩ Y) ∪ (X ∩ Z) ⊂ X ∩ (Y ∪ Z). This is sufficient, by Proposition 1 (double inclusion).

(i): Suppose that x ∈ X ∩ (Y ∪ Z). Then, by the definitions of intersection and of union, we have x ∈ X AND either (a) x ∈ Y or (b) x ∈ Z.

In case (a), we have x ∈ X and x ∈ Y. Hence x ∈ X ∩ Y, and then by Proposition 15 (each set is a subset of the union), x ∈ (X ∩ Y) ∪ (X ∩ Z).

In case (b), we have x ∈ X and x ∈ Z. Hence x ∈ X ∩ Z, and then by Proposition 15 (each set is a subset of the union), x ∈ (X ∩ Y) ∪ (X ∩ Z).

Either way, x ∈ (X ∩ Y) ∪ (X ∩ Z), so we can conclude that X ∩ (Y ∪ Z) ⊂ (X ∩ Y) ∪ (X ∩ Z).

(ii): Suppose that x ∈ (X ∩ Y) ∪ (X ∩ Z). By the definition of union, either (a) x ∈ X ∩ Y or (b) x ∈ X ∩ Z.

In case (a), by the definition of intersection we have x ∈ X and x ∈ Y. Since x ∈ Y, we have x ∈ Y ∪ Z by Proposition 15 (each set is a subset of the union). We thus have x ∈ X and x ∈ Y ∪ Z, and by the definition of intersection this implies that x ∈ X ∩ (Y ∪ Z).

In case (b), by the definition of intersection we have x ∈ X and x ∈ Z, and since Proposition 15 (each set is a subset of the union) also implies that x ∈ Y ∪ Z, the rest of the proof is the same as in case (a).

Either way, we have x ∈ X ∩ (Y ∪ Z), and it follows that (X ∩ Y) ∪ (X ∩ Z) ⊂ X ∩ (Y ∪ Z), as required.

The next proposition is the same as the last, with union and intersection swapped over.

Figure 11 does for it what Figure 10 did for the last one.

The next pair of identities are worth thinking about informally first. X ∩ Y is already part of X, so throwing it back in with X adds nothing new. And X ∪ Y contains the whole of X, so cutting it down to the part lying in X leaves X untouched. In Figure 12, the whole of X is shaded, and X ∩ Y is the doubly shaded part of it. Since that part is already inside X, putting it back in adds nothing.

Proposition 26 (absorption for intersection). For any sets X and Y, X ∩ (X ∪ Y) = X.