Definition 8 (Intersection). X ∩ Y = {x : x ∈ X and x ∈ Y}.
12Intersections
Given two sets X and Y, their intersection is the set containing those objects which belong to both of them. We write it X ∩ Y. In the inclusion criterion notation from above:
For example, {7, 8, 9} ∩ {8, 9, 10} = {8, 9}.
It often helps to draw a picture. The two circles stand for X and Y, and their intersection is the shaded region where the circles overlap.
The first thing to notice is that taking an intersection only ever makes a set smaller, or leaves it as it was.
Proposition 8 (an intersection is a subset of each set). For any sets X and Y, X ∩ Y ⊂ X and X ∩ Y ⊂ Y.
Let x be an arbitrary element of X ∩ Y. By the definition of intersection, x ∈ X and x ∈ Y. Hence every element of X ∩ Y is an element of both X and Y.
Intersection also respects the subset relation: making one of the two sets bigger cannot make the intersection smaller.
In Figure 4 the doubly shaded region is X ∩ Z, and it sits inside Y ∩ Z.
Proposition 9 (intersection respects inclusion). For any sets X, Y and Z, if X ⊂ Y, then X ∩ Z ⊂ Y ∩ Z.
Suppose x ∈ X ∩ Z. Then x ∈ X and x ∈ Z. Since X ⊂ Y, we also have x ∈ Y. Hence x ∈ Y ∩ Z.
Intersection also behaves in some ways like the multiplication or addition of numbers. The order does not matter, and neither does the bracketing. (These properties are generally known as commutativity and associativity respectively.)
The first of these is our first chance to use the method of inclusion criteria.
Proposition 10 (intersection commutes). For any sets X and Y, X ∩ Y = Y ∩ X.
The inclusion criterion for X ∩ Y is x ∈ X and x ∈ Y. The inclusion criterion for Y ∩ X is x ∈ Y and x ∈ X. These two criteria are logically equivalent, since a claim of the form “P and Q” holds in exactly the cases in which “Q and P” holds. That is, logical conjunction commutes.
Notice that the fact we leaned on there is a fact about logic, and not a fact about sets. The reason X ∩ Y and Y ∩ X are the same set is that intersection is defined using “and”, and conjunction commutes. The fact about sets is closely tied to the fact about logic, but it is the fact about logic which is prior.
We now have two general techniques for showing that two sets are identical, so let me set them side by side. The first method is to show that each set is a subset of the other, applying Proposition 1 (double inclusion). The second is to write down the inclusion criterion for each set and observe that the two criteria are equivalent.
From now on we will help ourselves to any fact about classical logic we need, without stopping to justify it. Proving such facts is the business of a logic course, not of this primer. You should feel free to do the same in your own proofs.
Proposition 11 (intersection is associative). For any sets X, Y and Z, (X ∩ Y) ∩ Z = X ∩ (Y ∩ Z).
Write S1 for the first set and S2 for the second set. The inclusion criterion for S1 is x ∈ (X ∩ Y) and x ∈ Z. The inclusion criterion for S2 is x ∈ X and x ∈ (Y ∩ Z). Applying the inclusion criteria for X ∩ Y and for Y ∩ Z, the inclusion criterion for S1 becomes (x ∈ X and x ∈ Y) and x ∈ Z, while the inclusion criterion for S2 becomes x ∈ X and (x ∈ Y and x ∈ Z). These two inclusion criteria are logically equivalent.
Because of this last proposition we can simply write X ∩ Y ∩ Z, with no brackets and no ambiguity about what is meant. We can also ignore the difference between X ∩ Y and Y ∩ X: the two are defined differently, but we have just proved that they must always contain exactly the same elements.
Two smaller facts are worth recording.
Proposition 12 (intersecting a set with itself). For any set X, X ∩ X = X.
The inclusion criterion for X ∩ X is x ∈ X and x ∈ X, which is logically equivalent to x ∈ X (the inclusion criterion for X).
Proposition 13 (intersecting with the empty set). For any set X, X ∩ ∅ = ∅.
If x ∈ X ∩ ∅ then x ∈ X and x ∈ ∅. But that is impossible, because ∅ contains no elements. Therefore there is no element of X ∩ ∅, and so X ∩ ∅ is equal to ∅ by Proposition 5 (the empty set is unique).
Finally, intersection gives us another way of saying that one set is a subset of another.
Proposition 14 (inclusion via intersection). For any sets X and Y, X ⊂ Y if and only if X ∩ Y = X.
We show both directions of the biconditional.
(i) Left to right direction: suppose that X ⊂ Y. We want to show that X ∩ Y = X. We have X ∩ Y ⊂ X by Proposition 8 (an intersection is a subset of each set). Now let x be an arbitrary element of X; since X ⊂ Y we have x ∈ Y, and hence x ∈ X ∩ Y. Since x was chosen arbitrarily, we can conclude X ⊂ X ∩ Y. Putting these two subset claims together by Proposition 1 (double inclusion), we can conclude that X ∩ Y = X.
(ii) Right to left direction: suppose that X ∩ Y = X. We want to show that X ⊂ Y. Proposition 8 (an intersection is a subset of each set) implies that X ∩ Y ⊂ Y, and since X ∩ Y = X we can conclude that X ⊂ Y, as required.
That last proposition is our first biconditional: a claim of the form “P if and only if Q”. To prove a biconditional we have to prove two things: that if P then Q, and that if Q then P. Each half is a conditional, so each half is proved in the way described above, by assuming the antecedent and deriving the consequent.