Cartesian Product is Empty iff Factor is Empty

From ProofWiki
Jump to navigation Jump to search

Theorem

$S \times T = \O \iff S = \O \lor T = \O$


Thus:

$S \times \O = \O = \O \times T$


Family of Sets

Let $I$ be an indexing set.

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

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

Then:

$S = \O$ if and only if $S_i = \O$ for some $i \in I$


Proof

\(\displaystyle S \times T\) \(\ne\) \(\displaystyle \O\)
\(\displaystyle \leadstoandfrom \ \ \) \(\displaystyle \exists \tuple {s, t}\) \(\in\) \(\displaystyle S \times T\) Definition of Empty Set
\(\displaystyle \leadstoandfrom \ \ \) \(\displaystyle \exists s \in S\) \(\land\) \(\displaystyle \exists t \in T\) Definition of Cartesian Product
\(\displaystyle \leadstoandfrom \ \ \) \(\displaystyle S \ne \O\) \(\land\) \(\displaystyle T \ne \O\) Definition of Empty Set
\(\displaystyle \leadstoandfrom \ \ \) \(\displaystyle \neg \leftparen {S = \O}\) \(\lor\) \(\displaystyle \rightparen {T = \O}\) De Morgan's Laws: Conjunction of Negations


So by the Rule of Transposition:

$S = \O \lor T = \O \iff S \times T = \O$

$\blacksquare$


Sources