Condition for Cartesian Product Equivalent to Associated Cardinal Number

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ and $T$ be nonempty sets.

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


Then:

$S \times T \sim \left|{S \times T}\right| \iff S \sim \left|{S}\right| \land T \sim \left|{T}\right|$

where $S \times T$ denotes the cartesian product of $S$ and $T$.


Proof

Necessary Condition

If $S \times T \sim \left|{S \times T}\right|$, then there is a mapping $f$ such that:

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


Since $f$ is a bijection, it follows that:

$S$ is equivalent to the image of $S \times \left\{{x}\right\}$ under $f$ where $x \in T$.


This, in turn, is a subset of the ordinal $\left|{S \times T}\right|$.

$\left|{S \times T}\right|$ is an ordinal by Cardinal Number is Ordinal.


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

Similarly, $T \sim \left|{T}\right|$.

$\Box$


Sufficient Condition

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)$


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

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

$\blacksquare$


Sources