Cartesian Product of Subsets

From ProofWiki
Revision as of 19:50, 15 February 2011 by Prime.mover (talk | contribs)
Jump to navigation Jump to search

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:

\(\ds \) \(\) \(\ds \left({x, y}\right) \in A \times B\)
\(\ds \) \(\implies\) \(\ds x \in A, y \in B\) Definition of Cartesian Product
\(\ds \) \(\implies\) \(\ds x \in S, y \in T\) Definition of Subset
\(\ds \) \(\implies\) \(\ds \left({x, y}\right) \in S \times T\) 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:

\(\ds \) \(\) \(\ds x \in A, y \in B\)
\(\ds \) \(\implies\) \(\ds \left({x, y}\right) \in A \times B\) Definition of Cartesian Product
\(\ds \) \(\implies\) \(\ds \left({x, y}\right) \in S \times T\) Definition of Subset
\(\ds \) \(\implies\) \(\ds x \in S, y \in T\) 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

Retrieved from "https://proofwiki.org/w/index.php?title=Cartesian_Product_of_Subsets&oldid=45868"