Skip to main content

# 8.3: How to Prove A=B


In proofs it is often necessary to show that two sets are equal. There is a standard way of doing this. Suppose we want to show $$A = B$$. If we show $$A \subseteq B$$, then every element of A is also in B, but there is still a possibility that B could have some elements that are not in A, so we can’t conclude $$A = B$$. But if in addition we also show $$B \subseteq A$$, then B can’t contain anything that is not in A, so $$A = B$$. This is the standard procedure for proving $$A = B$$: Prove both $$A \subseteq B$$ and $$B \subseteq A$$.

How to Prove $$A = B$$

Proof.

[Prove that $$A \subseteq B$$.]

[Prove that $$B \subseteq A$$.]

Therefore, since $$A \subseteq B$$ and $$B \subseteq A$$, it follows that $$A = B$$.

Example 8.10

Prove that $$\{n \in \mathbb{Z} : 35|n\} = \{n \in \mathbb{Z} : 5|n\} \cap \{n \in \mathbb{Z} : 7|n\}$$.

Proof. First we show $$\{n \in \mathbb{Z} : 35|n\} \subseteq \{n \in \mathbb{Z} : 5|n\} \cap \{n \in \mathbb{Z} : 7|n\}$$. Suppose $$a \in \{n \in \mathbb{Z} : 35|n\}$$. This means $$35|a$$, so $$a = 35c$$ for some $$c \in \mathbb{Z}$$. Thus $$a = 5(7c)$$ and $$a = 7(5c)$$. From $$a = 5(7c)$$ it follows that $$5|a$$, so $$a \in \{n \in \mathbb{Z} : 5|n\}$$. From $$a = 7(5c)$$ it follows that $$7|a$$, which means $$a \in \{n \in \mathbb{Z} : 7|n\}$$. As a belongs to both $$\{n \in \mathbb{Z} : 5|n\}$$ and $$\{n \in \mathbb{Z} : 7|n\}$$, we get $$a \in \{n \in \mathbb{Z} : 5|n\} \cap \{n \in \mathbb{Z} : 7|n\}$$. Thus we've shown that $$\{n \in \mathbb{Z} : 35|n\} \subseteq \{n \in \mathbb{Z} : 5|n\} \cap \{n \in \mathbb{Z} : 7|n\}$$.

Next we show $$\{n \in \mathbb{Z} : 5|n\} \cap \{n \in \mathbb{Z} : 7|n\} \subseteq \{n \in \mathbb{Z} : 35|n\}$$. Suppose that $$a \in \{n \in \mathbb{Z} : 5|n\} \cap \{n \in \mathbb{Z} : 7|n\}$$. By definition of intersection, this means that $$a \in \{n \in \mathbb{Z} : 5|n\}$$ and $$a \in \{n \in \mathbb{Z} : 7|n\}$$. Therefore it follows that $$5|a$$ and $$7|a$$. By definition of divisibility, there are integers c and d with $$a = 5c$$ and $$a = 7d$$. Then a has both 5 and 7 as prime factors, so the prime factorization of a must include factors of 5 and 7. Hence $$5 \cdot 7 = 35$$ divides a, so $$a \in \{n \in \mathbb{Z} : 35|n\}$$. We’ve now shown that $$\{n \in \mathbb{Z} : 5|n\} \cap \{n \in \mathbb{Z} : 7|n\} \subseteq \{n \in \mathbb{Z} : 35|n\}$$.

At this point we’ve shown that $$\{n \in \mathbb{Z} : 35|n\} \subseteq \{n \in \mathbb{Z} : 5|n\} \cap \{n \in \mathbb{Z} : 7|n\}$$ and $$\{n \in \mathbb{Z} : 5|n\} \cap \{n \in \mathbb{Z} : 7|n\} \subseteq \{n \in \mathbb{Z} : 35|n\}$$, so we’ve proved $$\{n \in \mathbb{Z} : 35|n\} = \{n \in \mathbb{Z} : 5|n\} \cap \{n \in \mathbb{Z} : 7|n\}$$.

You know from algebra that if $$c \ne 0$$ and $$ac = bc$$, then $$a = b$$. Thenext example shows that an analogous statement holds for sets A, B and C. The example asks us to prove a conditional statement. We will prove it with direct proof. In carrying out the process of direct proof, we will have to use the new techniques from this section.

Example 8.11

Suppose A, B, and C are sets, and $$C \ne \emptyset$$. Prove that if $$A \times C = B \times C$$, then $$A = B$$.

Proof. Suppose $$A \times C = B \times C$$. We must now show $$A = B$$.

First we will show $$A \subseteq B$$. Suppose $$a \in A$$. Since $$C \ne \emptyset$$, there exists an element $$c \in C$$. Thus, since $$a \in A$$ and $$c \in C$$, we have $$(a, c) \in A \times C$$, by definition of the Cartesian product. But then, since $$A \times C = B \times C$$, it follows that $$(a, c) \in B \times C$$. But $$(a, c) \in B \times C$$ means $$a \in B$$, by definition of the Cartesian product. We have shown $$a \in A$$ implies $$a \in B$$, so $$A \subseteq B$$.

Next we show $$B \subseteq A$$. We use the same argument as above, with the roles of A and B reversed. Suppose $$a \in B$$. Since $$C \ne \emptyset$$, there exists an element $$c \in C$$. Thus, since $$a \in B$$ and $$c \in C$$, we have $$(a, c) \in B \times C$$. But then, since $$B \times C = A \times C$$, we have $$(a, c) \in A \times C$$. It follows that $$a \in A$$. We have shown $$a \in B$$ implies $$a \in A$$, so $$B \subseteq A$$.

The previous two paragraphs have shown $$A \subseteq B$$ and $$B \subseteq A$$, so $$A = B$$. In summary, we have shown that if $$A \times C = B \times C$$, then $$A = B$$. This completes the proof.

Now we’ll look at another way that set operations are similar to operations on numbers. From algebra you are familiar with the distributive property $$a \cdot (b+c) = a \cdot b+a \cdot c$$. Replace the numbers a,b,c with sets A, B, C, and replace $$\cdot$$ with $$\times$$ and + with $$\cap$$. We get $$A \times (B \cap C) = (A \times B) \cap (A \times C)$$. This statement turns out to be true, as we now prove.

Example 8.12

Given sets A, B and C, prove $$A \times (B \cap C) = (A \times B) \cap (A \times C)$$.

Proof. First we will show that $$A \times (B \cap C) \subseteq (A \times B) \cap (A \times C)$$.

Suppose $$(a, b) \in A \times (B \cap C)$$.

By definition of the Cartesian product, this means $$a \in A$$ and $$b \in B \cap C$$. By definition of intersection, it follows that $$b \in B$$ and $$b \in C$$.

Thus, since $$a \in A$$ and $$b \in B$$, it follows that $$(a, b) \in A \times B$$ (by definition of $$\times$$). Also, since $$a \in A$$ and $$b \in C$$, it follows that $$(a, b) \in A \times C$$ (by definition of $$\times$$). Now we have $$(a, b) \in A \times B$$ and $$(a, b) \in A \times C$$, so $$(a, b) \in (A \times B) \cap (A \times C)$$. We’ve shown that $$(a, b) \in A \times (B \cap C)$$ implies $$(a, b) \in (A \times B) \cap (A \times C)$$ so we have $$A \times (B \cap C) \subseteq (A \times B) \cap (A \times C)$$.
Next we will show that $$A \times (B \cap C) \subseteq (A \times B) \cap (A \times C)$$.

Suppose $$(a, b) \in (A \times B) \cap (A \times C)$$.

By definition of intersection, this means $$(a, b) \in A \times B$$ and $$(a, b) \in A \times C$$.

By definition of the Cartesian product, $$(a, b) \in A \times B$$ means $$a \in A$$ and $$b \in B$$. By definition of the Cartesian product, $$(a, b) \in A\ times C$$ means $$a \in A$$ and $$b \in C$$. We now have $$b \in B$$ and $$b \in C$$, so $$b \in B \cap C$$, by definition of intersection. Thus we’ve deduced that $$a \in A$$ and $$b \in B \cap C$$, so $$(a, b) \in A \times (B \cap C)$$.

In summary, we’ve shown that $$(a, b) \in (A \times B) \cap (A \times C)$$ implies $$(a, b) \in A \times (B \cap C)$$ so we have $$(A \times B) \cap (A \times C) \subseteq A \times (B \cap C)$$.

The previous two paragraphs show that $$A \times (B \cap C) \subseteq (A \times B) \cap (A \times C)$$ and $$(A \times B) \cap (A \times C) \subseteq A \times (B \cap C)$$., so it follows that $$A \times (B \cap C) = (A \times B) \cap (A \times C)$$.

Occasionally you can prove two sets are equal by working out a series of equalities leading from one set to the other. This like showing two algebraic expressions are equal by manipulating one until you obtain the other. We illustrate this in the following example, which gives an alternate solution to the previous example. This approach is sometimes not applicable (or awkward), but when it works it can shorten a proof dramatically.

A quick note before beginning the example. Notice that any statement P is logically equivalent to $$P \wedge P$$. (Write out a truth table if you are in doubt.) At one point in the following example we will replace the expression $$x \in A$$ with the logically equivalent statement $$(x \in A) \wedge (x \in A)$$.

Example 8.13

Given sets A, B, and C, prove $$A \times (B \cap C) = (A \times B) \cap (A \times C)$$.

Proof. Just observe the following sequence of equalities.

$$A \times (B \cap C) = \{(x, y) : (x \in A) \wedge (y \in B \cap C)\}$$

$$= \{(x, y) : (x \in A) \wedge (y \in B) \wedge (y \in C)\}$$

$$= \{(x, y) : (x \in A) \wedge (x \in A) \wedge (y \in B) \wedge (y \in C)\}$$

$$= \{(x, y) : ((x \in A) \wedge (y \in B)) \wedge ((x \in A) \wedge (y \in C))\}$$

$$= \{(x, y) : (x \in A) \wedge (y \in B)\} \cap \{(x, y) : (x \in A) \wedge (y \in C)\}$$

$$= (A \times B) \cap (A \times C)$$

This completes the proof.

The equation $$A \times (B \cap C) = (A \times B) \cap (A \times C)$$ just obtained is a fundamental law that you may actually use fairly often as you continue with mathematics. Some similar equations are listed below. Each of these can be proved with this section’s techniques, and the exercises will ask that you do so.

$$$\left. \begin{array}{c} {\overline{A \cap B} = \overline{A} \cup \overline{B}}\\ {\overline{A \cup B} = \overline{A} \cap \overline{B}} \nonumber \end{array} \right\} \text{DeMorgan’s laws for sets}$$$

$$$\left. \begin{array}{c} {A \cap (B \cup C) = (A \cap B) \cup (A \cap C)}\\ {A \cup (B \cap C) = (A \cup B) \cap (A \cup C)}\\ {A \times (B \cup C) = (A \times B) \cup (A \times C)}\\ {A \times (B \cap C) = (A \times B) \cap (A \times C)} \nonumber \end{array} \right\} \text{Distributive laws for sets}$$$

It is very good practice to prove these equations. Depending on your learning style, it is probably not necessary to commit them to memory. But don’t forget them entirely. They may be useful later in your mathematical work. If so, you can look them up or re-derive them on the spot. If you go on to study mathematics deeply, you will at some point realize that you’ve internalized them without even being cognizant of it.