Cartesian Product of Subsets

Theorem

Let $A \subseteq S$ and $B \subseteq T$.

Then $A \times B \subseteq S \times T$.

In addition, if $A, B \ne \varnothing$, then $A \times B \subseteq S \times T \iff A \subseteq S \land B \subseteq T$.

Proof

• First we show that $A \subseteq S \land B \subseteq T \implies A \times B \subseteq S \times T$.

First, let $A = \varnothing$ or $B = \varnothing$.

Then from Cartesian Product Null, $A \times B = \varnothing \subseteq S \times T$, so the result holds.

Next, let $A, B \ne \varnothing$. Then from Cartesian Product Null, $A \times B \ne \varnothing$ and we can use the following argument:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\)	\(\displaystyle \left({x, y}\right) \in A \times B\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle x \in A, y \in B\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Cartesian Product
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle x \in S, y \in T\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Subset
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \left({x, y}\right) \in S \times T\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Cartesian Product

Thus $A \times B \subseteq S \times T$ as we were to prove.

• Now we show that if $A, B \ne \varnothing$, then $A \times B \subseteq S \times T \implies A \subseteq S \land B \subseteq T$.

So suppose that $A \times B \subseteq S \times T$.

First note that if $A = \varnothing$, then $A \times B = \varnothing \subseteq S \times T$, whatever $B$ is, so it is not necessarily the case that $B \subseteq T$.

Similarly if $B = \varnothing$; it is not necessarily the case that $A \subseteq S$.

So that explains the restriction $A, B \ne \varnothing$.

Now, as $A, B \ne \varnothing$, $\exists x \in A, y \in B$. Thus:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\)	\(\displaystyle x \in A, y \in B\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \left({x, y}\right) \in A \times B\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Cartesian Product
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \left({x, y}\right) \in S \times T\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Subset
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle x \in S, y \in T\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Cartesian Product

So when $A, B \ne \varnothing$, we have:

• $A \subseteq S \land B \subseteq T \implies A \times B \subseteq S \times T$
• $A \times B \subseteq S \times T \implies A \subseteq S \land B \subseteq T$

from which $A \times B \subseteq S \times T \iff A \subseteq S \land B \subseteq T$.

$\blacksquare$

Sources

• Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 6$: Ordered Pairs
• Seth Warner: Modern Algebra (1965)... (previous)... (next): Exercise $1.3$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 8.1$