Cardinality of Union not greater than Product

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\FF$ be a set of sets.

Let:

$\size \FF \le \mathbf m$

where

$\size \FF$ denotes the cardinality of $\FF$
$\mathbf m$ is cardinal number (possibly infinite).

Let:

$\forall A \in \FF: \size A \le \mathbf n$

where

$\mathbf n$ is cardinal number (possibly infinite).

Then:

$\ds \size {\bigcup \FF} \le \size {\mathbf m \times \mathbf n} = \mathbf m \mathbf n$


Proof

$\FF = \O$ or $\FF = \set \O$ or $\O \ne \FF \ne \set \O$.

In case when $\FF = \O$ or $\FF = \set \O$:

\(\ds \size {\bigcup \FF}\) \(=\) \(\ds \size \O\) Union of Empty Set, Union of Singleton
\(\ds \) \(\le\) \(\ds \size {\mathbf m \times \mathbf n}\) Subset implies Cardinal Inequality because Empty Set is Subset of All Sets

In case when $\O \ne \FF \ne \{\O\}$:

by Surjection iff Cardinal Inequality there exists a surjection $f: \mathbf m \to \FF$ as $\size {\mathbf m} = \mathbf m$ by Cardinal of Cardinal Equal to Cardinal.

$\FF$ contains non empty set $A_0$.

$\size {A_0} > \mathbf 0$.

By assumption:

$\size {A_0} \le \mathbf n$.

Then:

$\mathbf 0 < \mathbf n$.

Hence:

$\size {\set 0} = \mathbf 1 \le \mathbf n$.

Define a family $\family {B_A}_{A \mathop \in \FF}$:

$B_A = \begin{cases} A & A \ne \O \\ \set 0 & A = \O \end {cases}$

By Surjection iff Cardinal Inequality define a family $\family {g_A}_{A \mathop \in \FF}$ of surjections:

$\forall A \in \FF: g_A: \mathbf n \to B_A$ is a surjection.

Define a mapping $h:\mathbf m \times \mathbf n \to \ds \bigcup_{A \mathop \in \FF} B_A$:

$\forall \alpha \in \mathbf m: \forall \beta \in \mathbf n: \map h {\alpha, \beta} = \map {g_{\map f \alpha} } \beta$

We will show by definition that $h$ is a surjection.

Let $x \in \ds \bigcup_{A \mathop \in \FF} B_A$.

Then by definition of union:

$\exists A \in \FF: x \in B_A$.

By definition of surjection:

$\exists \alpha \in \mathbf m: \map f \alpha = A$.

By definition of surjection:

$\exists \beta \in \mathbf n: \map {g_A} \beta = x$

So:

$\map h {\alpha, \beta} = \map {g_{\map f \alpha} } \beta = x$

This ends the proof of surjection.

Hence by Surjection iff Cardinal Inequality:

$\ds \size {\bigcup_{A \mathop \in \FF} B_A} \le \size {\mathbf m \times \mathbf n}$

By definition of subset:

$\forall A \in \FF: A \subseteq B_A$.

Then by Set Union Preserves Subsets:

$\ds \bigcup \FF \subseteq \bigcup_{A \mathop \in \FF} B_A$.

Hence by Subset implies Cardinal Inequality:

$\ds \size {\bigcup \FF} \le \ds \size {\bigcup_{A \mathop \in \FF} B_A}$

Thus the result:

$\size {\bigcup \FF} \le \size {\mathbf m \times \mathbf n}$

Thus by definition of product of cardinals:

$\size {\mathbf m \times \mathbf n} = \mathbf m \mathbf n$

$\blacksquare$


Sources