
# 8.2: How to Prove A⊆B


In this course (and more importantly, beyond it) you will encounter many circumstances where it is necessary to prove that one set is a subset of another. This section explains how to do this. The methods we discuss should improve your skills in both writing your own proofs and in comprehending the proofs that you read.

Recall (Definition 1.3) that if A and B are sets, then $$A \subseteq B$$ means that every element of A is also an element of B. In other words, it means if $$a \in A$$, then $$a \in B$$. Therefore to prove that $$A \subseteq B$$, we just need to prove that the conditional statement

"If $$a \in A$$, then $$a \in B$$"

is true. This can be proved directly, by assuming $$a \in A$$ and deducing $$a \in B$$. The contrapositive approach is another option: Assume $$a \notin B$$ and deduce $$a \notin A$$. Each of these two approaches is outlined below.

How to Prove $$A \subseteq B$$ (Direct approach)

Proof. Suppose $$a \in A$$.

$$\cdots$$

Therefore $$a \in B$$.

Thus $$a \in A$$ implies $$a \in B$$,

so it follows that $$A \subseteq B$$.

How to Prove $$A \subseteq B$$ (Contrapositive approach)

Proof. Suppose $$a \notin B$$.

$$\cdots$$

Therefore $$a \notin A$$.

Thus $$a \notin B$$ implies $$a \notin A$$,

so it follows that $$A \subseteq B$$.

In practice, the direct approach usually yields the most straightforward and easy proof, though occasionally the contrapositive is the most expedient. (You can even prove $$A \subseteq B$$ by contradiction: Assume $$(a \in A) \wedge (a \notin B)$$, and deduce a contradiction.) The remainder of this section consists of examples with occasional commentary. Unless stated otherwise, we will use the direct approach in all proofs; pay special attention to how the above outline for the direct approach is used.

Example 8.5

Prove that $$\{x \in \mathbb{Z} : 18|x\} \subseteq \{x \in \mathbb{Z} : 6|x\}$$.

Proof. Suppose $$a \in \{x \in \mathbb{Z} : 18|x\}$$.

This means that $$a \in \mathbb{Z}$$ and $$18|a$$.

By definition of divisibility, there is an integer c for which $$a = 18c$$.

Consequently $$a = 6(3c)$$, and from this we deduce that $$6|a$$.

Therefore a is one of the integers that 6 divides, so $$a \in \{x \in \mathbb{Z} : 6|x\}$$.

We’ve shown $$a \in \{x \in \mathbb{Z} : 18|x\}$$ implies $$a \in \{x \in \mathbb{Z} : 6|x\}$$, so it follows that $$\{x \in \mathbb{Z} : 18|x\} \subseteq \{x \in \mathbb{Z} : 6|x\}$$.

Example 8.6

Prove that $$\{x \in \mathbb{Z} : 2|x\} \cap \{x \in \mathbb{Z} : 9|x\} \subseteq \{x \in \mathbb{Z} : 6|x\}$$.

Proof. Suppose $$a \in \{x \in \mathbb{Z} : 2|x\} \cap \{x \in \mathbb{Z} : 9|x\}$$.

By definition of intersection, this means $$a \in \{x \in \mathbb{Z} : 2|x\}$$ and $$a \in \{x \in \mathbb{Z} : 9|x\}$$.

Since $$a \in \{x \in \mathbb{Z} : 2|x\}$$ we know $$2|a$$, so $$a = 2c$$ for some $$c \in \mathbb{Z}$$. Thus a is even.

Since $$a \in \{x \in \mathbb{Z} : 9|x\}$$ we know $$9|a$$, so $$a = 9d$$ for some $$d \in \mathbb{Z}$$.

As a is even, $$a = 9d$$ implies d is even. (Otherwise $$a = 9d$$ would be odd.)

Then $$d = 2e$$ for some integer e, and we have $$a = 9d = 9(2e) = 6(3e)$$.

From $$a = 6(3e)$$, we conclude $$6|a$$, and this means $$a \in \{x \in \mathbb{Z} : 6|x\}$$.

We have shown that $$a \in \{x \in \mathbb{Z}: 2|x\} \cap \{x \in \mathbb{Z} : 9|x\}$$ implies $$a \in \{x \in \mathbb{Z} : 6|x\}$$, so it follows that $$\{x \in \mathbb{Z} : 2|x\} \cap \{x \in \mathbb{Z} : 9|x\} \subseteq \{x \in \mathbb{Z} : 6|x\}$$.

Example 8.7

Show $$\{(x, y) \in \mathbb{Z} \times \mathbb{Z} : x \equiv y \pmod 6\} \subseteq \{(x, y) \in \mathbb{Z} \times \mathbb{Z} : x \equiv y \pmod 3\}$$.

Proof. Suppose $$(a, b) \in \{(x, y) \in \mathbb{Z} \times \mathbb{Z} : x \equiv y \pmod 6\}$$.

This means $$(a, b) \in \mathbb{Z} \times \mathbb{Z}$$ and $$a \equiv b \pmod 6\}$$.

Consequently $$6|(a-b)$$, so $$a-b = 6c$$ for some integer c.

It follows that $$a-b = 3(2c)$$, and this means $$3|(a-b)$$, so $$a \equiv b \pmod 3\}$$.

Thus $$(a, b) \in \{(x,y) \in \mathbb{Z} \times \mathbb{Z} : x \equiv y \pmod 3\}$$.

We’ve now seen that $$(a, b) \in \{(x, y) \in \mathbb{Z} \times \mathbb{Z} : x \equiv y \pmod 6\}$$ implies $$(a, b) \in \{(x, y) \in \mathbb{Z} \times \mathbb{Z} : x \equiv y \pmod 3\}$$, so it follows that $$\{(x, y) \in \mathbb{Z} \times \mathbb{Z} : x \equiv y \pmod 6\} \subseteq \{(x,y) \in \mathbb{Z} \times \mathbb{Z} : x \equiv y \pmod 3\}$$.

Some statements involving subsets are transparent enough that we often accept (and use) them without proof. For example, if A and B are any sets, then it’s very easy to confirm $$A \cap B \subseteq A$$. (Reason: Suppose $$x \in A \cap B$$. Then $$x \in A$$ and $$x \in B$$ by definition of intersection, so in particular $$x \in A$$. Thus $$x \in A \cap B$$ implies $$x \in A$$, so $$A \cap B \subseteq A$$.) Other statements of this nature include $$A \subseteq A \cup B$$ and $$A - B \subseteq A$$, as well as conditional statements such as $$(A \subseteq B) \wedge (B \subseteq C) \Rightarrow (A \subseteq C)$$ and $$(X \subseteq A) \Rightarrow (X \subseteq A \cup B)$$. Our point of view in this text is that we do not need to prove such obvious statements unless we are explicitly asked to do so in an exercise. (Still, you should do some quick mental proofs to convince yourself that the above statements are true. If you don’t see that $$A \cap B \subseteq A$$ is true but that $$A \subseteq A \cap B$$ is not necessarily true, then you need to spend more time on this topic.)

The next example will show that if A and B are sets, then $$\mathscr{P}(A) \cup \mathscr{P}(B) \subseteq \mathscr{P}(A \cup B)$$. Before beginning our proof, let’s look at an example to see if this statement really makes sense. Suppose $$A = \{1, 2\}$$ and $$B = \{2, 3\}$$. Then

$$\mathscr{P}(A) \cup \mathscr{P}(B) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\} \cup \{\emptyset, \{2\}, \{3\}, \{2, 3\}\}$$

$$= \{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{2,3\}\}$$.

Also $$\mathscr{P}(A \cup B) = \mathscr{P}(\{1,2,3\}) = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{2, 3\}, \{1, 3\}, \{1, 2, 3\}\}$$. Thus, even though $$\mathscr{P}(A) \cup \mathscr{P}(B) = \mathscr{P}(A \cup B)$$, it is true that $$\mathscr{P}(A) \cup \mathscr{P}(B) \subseteq \mathscr{P}(A \cup B)$$ for this particular A and B. Now let’s prove $$\mathscr{P}(A) \cup \mathscr{P}(B) \subseteq \mathscr{P}(A \cup B)$$ no matter what sets A and B are.

Example 8.8

Prove that if A and B are sets, then $$\mathscr{P}(A) \cup \mathscr{P}(B) \subseteq \mathscr{P}(A \cup B)$$.

Proof. Suppose $$X \in \mathscr{P}(A) \cup \mathscr{P}(B)$$.

By definition of union, this means $$X \in \mathscr{P}(A)$$ or $$X \in \mathscr{P}(B)$$.

Therefore $$X \subseteq A$$ or $$X \subseteq B$$ (by definition of power sets). We consider cases.

Case 1. Suppose $$X \subseteq A$$. Then $$X \subseteq A \cup B$$, and this means $$X \in \mathscr{P}(A \cup B)$$.

Case 2. Suppose $$X \subseteq B$$. Then $$X \subseteq A \cup B$$, and this means $$X \in \mathscr{P}(A \cup B)$$. (We do not need to consider the case where $$X \subseteq A$$ and $$X \subseteq B$$ because that is taken care of by either of cases 1 or 2.) The above cases show that $$X \in \mathscr{P}(A \cup B)$$.

Thus we've shown that $$X \in \mathscr{P}(A) \cup \mathscr{P}(B)$$ implies $$X \in \mathscr{P}(A \cup B)$$, and this completes the proof that $$\mathscr{P}(A) \cup \mathscr{P}(B) \subseteq \mathscr{P}(A \cup B)$$.

In our next example, we prove a conditional statement. Direct proof is used, and in the process we use our new technique for showing $$A \subseteq B$$.

Example 8.9

Suppose A and B are sets. If $$\mathscr{P}(A) \subseteq \mathscr{P}(B)$$, then $$A \subseteq B$$.

Proof. We use direct proof. $$\mathscr{P}(A) \subseteq \mathscr{P}(B)$$.

Based on this assumption, we must now show that $$A \subseteq B$$.

To show $$A \subseteq B$$, suppose that $$a \in A$$.

Then the one-element set $$\{a\}$$ is a subset of A, so $$\{a\} \in \mathscr{P}(A)$$.

But then, since $$\mathscr{P}(A) \subseteq \mathscr{P}(B)$$, it follows that $$\{a\} \in \mathscr{P}(B)$$.

This means that $$\{a\} \subseteq B$$, hence $$a \in B$$.

We've shown that $$a \in A$$ implies $$a \in B$$, so therefore $$A \subseteq B$$.