Non-Finite Cardinal is equal to Cardinal Product

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\omega$ denote the minimal infinite successor set.

Let $x$ be an ordinal such that $x \ge \omega$.


Then:

$\left|{x}\right| = \left|{ x\times x}\right|$

where $\times$ denotes the Cartesian product.


Corollary

Let $S$ be a set that is equinumerous to its cardinal number.

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

Let:

$\left|{S}\right| \ge \omega$

where $\omega$ denotes the minimal infinite successor set.


Then:

$\left|{S \times S}\right| = \left|{S}\right|$

Proof

The proof shall proceed by Transfinite Induction on $x$.


Let:

$\forall y \in x: y < \omega \lor \left|{ y }\right| = \left|{ y \times y }\right|$

There are two cases:


Case 1: $\left|{ y }\right| = \left|{ x }\right|$ for some $y \in x$

If this is so, then:

\(\displaystyle \left\vert{ x }\right\vert\) \(=\) \(\displaystyle \left\vert{ y }\right\vert\)
\(\displaystyle \) \(=\) \(\displaystyle \left\vert{ y \times y }\right\vert\) Inductive hypothesis
\(\displaystyle \) \(=\) \(\displaystyle \left\vert{ x \times x }\right\vert\)

$\Box$


Case 2: $\left|{ y }\right| < \left|{ x }\right|$ for all $y \in x$

We have that either:

$y < \omega$

or:

$\left|{ y }\right| = \left|{ y + 1 }\right|$

In either case, we have that:

$\left|{y + 1}\right < \left|{x}\right|$

and therefore:

$y + 1 \in x$

Therefore, $x$ is a limit ordinal.


Let $R_0$ denote the canonical order of $\operatorname{On}^2$.

Let $J_0$ be defined as the unique order isomorphism between $\operatorname{On}^2$ and $\operatorname{On}$ as defined in canonical order.


It follows that:

$J_0 \left({x \times x}\right) = \bigcup_{y \mathop \in x} \bigcup_{z \mathop \in x} J_0 \left({y, z}\right)$


But moreover:

\(\displaystyle J_0 \left({ y,z }\right)\) \(=\) \(\displaystyle \in^{-1} \left({ J_0 \left({ y,z }\right)}\right)\) Definition of Preimage
\(\displaystyle \) \(=\) \(\displaystyle J_0 \left({ R_0^{-1} \left({ y,z }\right) }\right)\) as $J_0$ forms an Order Isomorphism.


Since $J_0$ is a bijection:

\(\displaystyle \left\vert{J_0 \left({y, z}\right) }\right\vert\) \(=\) \(\displaystyle \left\vert{J_0 \left({R_0^{-1} \left({y, z}\right) }\right) }\right\vert\) Equality shown above
\(\displaystyle \) \(=\) \(\displaystyle \left\vert{ R_0^{-1} \left({y, z}\right) }\right\vert\) Image of Bijection Cardinal Equality


Take $\max \left({y, z}\right)$.

\(\displaystyle \left({a, b}\right)\) \(\in\) \(\displaystyle R_0^{-1} \left({y, z}\right)\) hypothesis
\(\displaystyle \iff \ \ \) \(\displaystyle \left({a, b}\right)\) \(R_0\) \(\displaystyle \left({y, z}\right)\) Definition of Image
\(\displaystyle \iff \ \ \) \(\displaystyle a, b\) \(\le\) \(\displaystyle \max \left({y, z}\right)\) Definition of Canonical Order
\(\displaystyle \iff \ \ \) \(\displaystyle a, b\) \(\in\) \(\displaystyle \max \left({y, z}\right) + 1\) Definition of Successor


It follows that:

\(\displaystyle \left\vert{R_0^{-1} \left({y, z}\right) }\right\vert\) \(\le\) \(\displaystyle \left\vert{\max \left({y, z}\right) + 1 \times \max \left({y, z}\right) + 1}\right\vert\)
\(\displaystyle \) \(=\) \(\displaystyle \left\vert{\max \left({y, z}\right) + 1}\right\vert\) Inductive hypothesis
\(\displaystyle \) \(<\) \(\displaystyle \left\vert{x}\right\vert\) Hypothesis for the case

Therefore:

$\left\vert{ R_0^{-1} \left({y, z}\right) }\right\vert < \left|{ x }\right|$

Thus by Cardinal Inequality implies Ordinal Inequality:

$\forall y, z \in x: J_0 \left({y, z}\right) < \left|{x}\right|$


It follows by Supremum Inequality for Ordinals that:

$J_0 \left({x \times x}\right) \subseteq \left|{x}\right|$

Hence:

\(\displaystyle \left\vert{x \times x}\right\vert\) \(=\) \(\displaystyle \left\vert{J_0 \left({x \times x}\right) }\right\vert\) Image of Bijection Cardinal Equality
\(\displaystyle \) \(\le\) \(\displaystyle \left\vert{x}\right\vert\) Subset of Ordinal implies Cardinal Inequality

But also by Set Less than Cardinal Product:

$\left|{x}\right| \le \left|{x \times x}\right|$


Thus:

$\left|{x}\right| = \left|{x \times x}\right|$

$\blacksquare$


Sources