Prove That A Is a Subset of C If A × B ⊆ B × C

The inclusion $A \times B \subseteq B \times C$ says that every ordered pair formed from an element of $A$ and an element of $B$ is also an ordered pair whose first entry is in $B$ and whose second entry is in $C$. The nonempty-set assumptions let us use those two coordinates to establish two ordinary subset relations.

What the product inclusion tells you

By definition,

$$A \times B = \{(a,b) : a \in A \text{ and } b \in B\}.$$

Under the standard definition of ordered pairs, $(x,y) \in B \times C$ means both $x \in B$ and $y \in C$. Thus, from the given inclusion, for every $a \in A$ and $b \in B$, we know that $a \in B$ and $b \in C$.

The key is to use nonemptiness to make each of these statements apply to all elements of a set. A fixed element of $B$ helps show $A \subseteq B$; a fixed element of $A$ helps show $B \subseteq C$.

Proof

Since $B$ is nonempty, choose an element $b_0 \in B$. Take any $a \in A$. Then $(a,b_0) \in A \times B$. The product inclusion gives $(a,b_0) \in B \times C$, so its first coordinate belongs to $B$. Therefore $a \in B$. Since this holds for every $a \in A$,

$$A \subseteq B.$$

Next, since $A$ is nonempty, choose an element $a_0 \in A$. Take any $b \in B$. Then $(a_0,b) \in A \times B$, and hence $(a_0,b) \in B \times C$. Its second coordinate must belong to $C$, so $b \in C$. This holds for every $b \in B$, giving

$$B \subseteq C.$$

Subset inclusion is transitive: if every element of $A$ is in $B$, and every element of $B$ is in $C$, then every element of $A$ is in $C$. Consequently,

$$A \subseteq C.$$

A concrete example

Let $A = \{1\}$, $B = \{1,2\}$, and $C = \{1,2\}$. Then

$$A \times B = \{(1,1),(1,2)\},$$

while $B \times C$ contains all four pairs $(1,1)$, $(1,2)$, $(2,1)$, and $(2,2)$. Thus $A \times B \subseteq B \times C$, and indeed $A \subseteq C$.

The coordinate argument explains why the inclusion works: the first entries contributed by $A$ must be in $B$, and the second entries contributed by $B$ must be in $C$. In this example, those facts are $A \subseteq B$ and $B \subseteq C$.

Common mistakes

• Reading the coordinates in the wrong order. Membership in $B \times C$ requires the first coordinate to lie in $B$ and the second to lie in $C$. It does not directly say that the first coordinate lies in $C$.
• Trying to conclude $A \subseteq C$ from just one pair. One pair only gives information about its two entries. To establish a subset statement, use an arbitrary element of the relevant set and a fixed element from the other nonempty set.
• Treating nonemptiness as unnecessary. If $B = \varnothing$, then $A \times B = \varnothing$, so the product inclusion holds regardless of whether $A \subseteq C$. For instance, $A=\{1\}$, $B=\varnothing$, and $C=\varnothing$ satisfy the product inclusion, but $A$ is not a subset of $C$.

Which assumptions matter?

The stated assumptions that $A$ and $B$ are nonempty make the proof work. The assumption that $C$ is nonempty is not needed: the inclusion itself forces $B \subseteq C$ when $A$ is nonempty. If $A$ were empty, the desired conclusion $A \subseteq C$ would already be true, regardless of $B$ or $C$.