# Cartesian Product of Subsets

## Theorem

Let $A, B, S, T$ be sets such that $A \subseteq B$ and $S \subseteq T$.

Then:

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

In addition, if $A, S \ne \O$, then:

$A \times S \subseteq B \times T \iff A \subseteq B \land S \subseteq T$

### Corollary 1

Let $A, B, S$ be sets such that $A \subseteq B$.

Then:

$A \times S \subseteq B \times S$

### Corollary 2

Let $A, S, T$ be sets such that $S \subseteq T$.

Then:

$A \times S \subseteq A \times T$

### Corollary 3

Let $A, B, C$ be sets such that $B \ne \O$.

Let $A \times B \subseteq C \times C$.

Then:

$A \subseteq C$

### Family of Subsets

Let $\family {S_i}_{i \mathop \in I}$ be a family of sets where $I$ is an arbitrary index set.

Let $S = \ds \prod_{i \mathop \in I} S_i$ be the Cartesian product of $\family {S_i}_{i \mathop \in I}$.

Let $\family {T_i}_{i \mathop \in I}$ be a family of sets.

Let $T = \ds \prod_{i \mathop \in I} T_i$ be the Cartesian product of $\family {T_i}_{i \mathop \in I}$.

Then:

$\paren {\forall i \in I: T_i \subseteq S_i} \implies T \subseteq S$.

#### Nonempty Subsets

Let $T_i \ne \O$ for all $i \in I$.

Then:

$T \subseteq S \iff \forall i \in I: T_i \subseteq S_i$.

## Proof

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

First, let $A = \O$ or $S = \O$.

$A \times S = \O \subseteq B \times T$

so the result holds.

Next, let $A, S \ne \O$.

$A \times S \ne \O$

and we can use the following argument:

 $\ds$  $\ds \tuple {x, y} \in A \times S$ $\ds$ $\leadsto$ $\ds x \in A, y \in S$ Definition of Cartesian Product $\ds$ $\leadsto$ $\ds x \in B, y \in T$ Definition of Subset $\ds$ $\leadsto$ $\ds \tuple {x, y} \in B \times T$ Definition of Cartesian Product

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

Now we show that if $A, S \ne \O$, then:

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

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

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

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

So that explains the restriction $A, S \ne \O$.

Now, as $A, S \ne \O$, $\exists x \in A, y \in S$.

Thus:

 $\ds$  $\ds x \in A, y \in S$ $\ds$ $\leadsto$ $\ds \tuple {x, y} \in A \times S$ Definition of Cartesian Product $\ds$ $\leadsto$ $\ds \tuple {x, y} \in B \times T$ Definition of Subset $\ds$ $\leadsto$ $\ds x \in B, y \in T$ Definition of Cartesian Product

So when $A, S \ne \O$, we have:

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

from which:

$A \times S \subseteq B \times T \iff A \subseteq B \land S \subseteq T$

$\blacksquare$