Cardinal Product Equinumerous to Ordinal Product

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let $\left|{ S }\right|$ denote the cardinal number of $S$.

Let $\cdot$ denote ordinal multiplication and let $\times$ denote the Cartesian product.


Then:

$S \times T \sim \left|{ S }\right| \cdot \left|{ T }\right|$


Proof

Suppose $f: S \to \left|{S}\right|$ is a bijection and $g: T \to \left|{T}\right|$ is a bijection.

Let $\cdot$ denote ordinal multiplication, while $\times$ shall denote the Cartesian product.


Define the function $F$ to be:

$\forall x \in S, y \in T: F \left({x, y}\right) = \left|{S}\right| \cdot g \left({y}\right) + f \left({x}\right)$


Suppose $F\left({x_1,y_1}\right) = F\left({x_2,y_2}\right)$.

\(\displaystyle \left\vert{ S }\right\vert \cdot g\left({y_1}\right) + f\left({x_1}\right)\) \(=\) \(\displaystyle \left\vert{ S }\right\vert \cdot g\left({y_2}\right) + f\left({x_2}\right)\)
\(\displaystyle \implies \ \ \) \(\displaystyle f\left({x_1}\right) , f\left({x_2}\right)\) \(\in\) \(\displaystyle \left\vert{ S }\right\vert\) definition of the mapping $f$
\(\displaystyle \implies \ \ \) \(\displaystyle f\left({x_1}\right) = f\left({x_2}\right)\) \(\land\) \(\displaystyle g\left({y_1}\right) = g\left({y_2}\right)\) by the Division Theorem for Ordinals
\(\displaystyle \implies \ \ \) \(\displaystyle x_1 = x_2\) \(\land\) \(\displaystyle y_1 = y_2\) by the fact that $f$ and $g$ are bijections.

It follows that $F: S \times T \to \left|{S}\right| \cdot \left|{T}\right|$ is a injection.

$\Box$


Furthermore, take any $z \in \left|{ S }\right| \cdot \left|{ T }\right|$.

By the Division Theorem for Ordinals, it follows that:

$z = \left|{ S }\right| \cdot a + b$ for some unique $a$ and $b \in \left|{ S }\right|$.

Moreover, $a \in \left|{ T }\right|$ since otherwise, this would contradict the fact that $z \in \left|{ S }\right| \cdot \left|{ T }\right|$.

Therefore, $a = f\left({x}\right)$ for some $x \in S$ and $b = g\left({y}\right)$ for some $y \in T$.

Thus, $F : S \times T \to \left|{ S }\right| \cdot \left|{ T }\right|$ is a surjection.

$\Box$


Therefore, $F : S \times T \to \left|{ S }\right| \cdot \left|{ T }\right|$ is a bijection by the definition of bijection.

By Condition for Set Equivalent to Cardinal Number, it follows that $S \times T \sim \left|{S}\right| \cdot \left|{T}\right|$.

$\blacksquare$