Cardinal of Union Less than Cardinal of Cartesian Product

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ and $T$ be sets that are equivalent to their cardinal numbers.

Let $\card S$ denote the cardinal number of $S$.

Let $\card S > 1$ and $\card T > 1$.


Then:

$\card {S \cup T} \le \card {S \times T}$


Proof

Let $x_1$ and $x_2$ be distinct elements of $S$.

Let $y_1$ and $y_2$ be distinct elements of $T$.


Define the mapping $f : S \times T \to S \cup T$ as follows:

$\map f {x, y} = \begin {cases} y &: x = x_1 \\ x_1 &: x = x_2 \land y = y_1 \\ x &: \text {otherwise} \end {cases}$


If $x \in S$, then we have that either $x = x_1$ or $x \ne x_1$.

If $x \ne x_1$, then $\map f {x, y_2} = x$ by the definition of $f$.

If $x = x_1$, then $\map f {x_2, y_1} = x_1$ by the definition of $f$.


If $y \in S$, then we have that:

$\map f {x_1, y} = y$ by the definition of $f$.


Therefore, it follows that $f : S \times T \to S \cup T$ is a surjection.

Thus by Surjection iff Cardinal Inequality:

$\card {S \cup T} \le \card {S \times T}$

$\blacksquare$


Sources