Cartesian Product of Subsets

From ProofWiki
Jump to: navigation, search

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 \varnothing$, 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 B$


Proof

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

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

Then from Cartesian Product is Empty iff Factor is Empty:

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

so the result holds.


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

Then from Cartesian Product is Empty iff Factor is Empty:

$A \times S \ne \varnothing$

and we can use the following argument:

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


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


Now we show that if $A, S \ne \varnothing$, 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 = \varnothing$, then $A \times S = \varnothing \subseteq B \times T$, whatever $S$ is, so it is not necessarily the case that $S \subseteq T$.

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

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


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

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


So when $A, S \ne \varnothing$, 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$


Sources