8Subsets

A very important concept for dealing with sets is the concept of a subset. We say that X is a subset of Y when Y extends X. That is, every element of X is also an element of Y. Note that we do not require that Y contains more elements than X: if X and Y are identical, then every element of X is an element of Y, and so X is a subset of Y (that is, every set is a subset of itself):

Definition 3 (Subset). X ⊂ Y means that every element of X is an element of Y. We then say that X is a subset of Y.

Figure 1. A subset X of a set Y.

We write X ⊂ Y to denote that X is a subset of Y.¹ This is just because using symbols is often faster and easier than using English—but in principle, everything could be done in English.

It often helps to picture a subset as sitting inside its superset.

We will often want to show that two sets X and Y are identical. An extremely important proof strategy here is to show that X is a subset of Y and Y is also a subset of X. If we can show this, we have shown that the two sets are the same. Let me explain why; and this will also serve as the first proof in this primer.

Proposition 1 (double inclusion). For any sets X and Y, if X ⊂ Y and Y ⊂ X, then X = Y.

Let X and Y be any two sets, and suppose that X ⊂ Y and Y ⊂ X. In order to show that X = Y, we will show that they have exactly the same elements, and then apply the Axiom of Extensionality. So let x be any object. If it is an element of X, then since X ⊂ Y we can conclude that x is also an element of Y. Similarly, if x is an element of Y, then since Y ⊂ X we can conclude that x is also an element of X. Thus x is an element of X if and only if x is an element of Y.

Since x was chosen arbitrarily, this holds of any object whatsoever. In other words, any object whatsoever is either an element of both X and Y, or it is an element of neither; and this is what it means to say that X and Y have exactly the same elements. The Axiom of Extensionality then tells us that X and Y are identical.

Let me explain in more detail how that proof worked.

The statement we wanted to prove, Proposition 1 (double inclusion), is a universal statement that holds for any sets X and Y. (That is, it begins with a string of two universal quantifiers, which we rendered in English.) The way to prove a universal statement is to introduce X and Y as generic sets, assume nothing whatsoever about them, and then prove that the statement holds of X and Y. If we can do so without making any special assumptions about X and Y, then we have proved that that statement is true for any two sets whatsoever. After all, for any two sets S₁ and S₂, we could take whatever argument we made regarding X and Y and apply it directly to S₁ and S₂. (The reason we know we can do this is that we made no special assumptions about X and Y, so there is no reason why our argument should not apply to any two sets.)

This kind of logical inference, deriving a universal statement from what we can show of an arbitrarily chosen object about which we have made no special assumptions, is known as universal generalisation.

But what is the statement we wished to prove about the arbitrarily chosen sets X and Y? It is that, if these two sets are subsets of each other, then they are identical. This is a conditional statement. The way to prove a conditional statement is to assume the part in front—the antecedent—which in this case is that X ⊂ Y and Y ⊂ X. We then attempt to show the part at the end—the consequent—which in this case is that X = Y.

So, having chosen X and Y arbitrarily, what we did was to assume the antecedent, that X ⊂ Y and Y ⊂ X, and derive the consequent, that X = Y. Doing this completed the proof of the universal statement as a whole. And that is why the proof works.

I deliberately wrote this proof in a way that was longer and more detailed than we would usually require. This is because I wanted to go slowly and be clear about exactly how each piece of it worked. But normally we will want to write proofs more concisely. Here is an alternative, more concise proof of Proposition 1 (double inclusion):

Suppose that X ⊂ Y and Y ⊂ X. For any object x, since X ⊂ Y it holds that if x ∈ X, then x ∈ Y. Similarly, it holds that if x ∈ Y, then x ∈ X. Hence x ∈ X if and only if x ∈ Y, and therefore by the Axiom of Extensionality we have X = Y.

Now that you have seen how proofs like these work, give this one a try:

Proposition 2 (every set is a subset of itself). Every set is a subset of itself.

Exercise 1. Prove Proposition 2 (every set is a subset of itself).

Some authors use ⊂ only for proper subsets. X is a proper subset of Y when every element of X is an element of Y, but X and Y are not identical. Those authors write X ⊆ Y for a subset in the sense defined here. The symbol ⊆ always means a subset in this inclusive sense, so it is never ambiguous. ↩