Ordinal Multiplication is Associative

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $x, y, z$ be ordinals.

Let $\times$ denote ordinal multiplication.


Then:

$x \times \left({y \times z}\right) = \left({x \times y}\right) \times z$


Proof

The proof shall proceed by Transfinite Induction on $z$:


Basis for the Induction

Let $0$ denote the zero ordinal.

\(\displaystyle x \times \left({y \times 0}\right)\) \(=\) \(\displaystyle x \times 0\) Ordinal Multiplication by Zero
\(\displaystyle \) \(=\) \(\displaystyle 0\) Ordinal Multiplication by Zero
\(\displaystyle \) \(=\) \(\displaystyle \left({x \times y}\right) \times 0\) Ordinal Multiplication by Zero

This proves the basis for the induction.


Induction Step

\(\displaystyle x \times \left({y \times z}\right)\) \(=\) \(\displaystyle \left({x \times y}\right) \times z\) Inductive Hypothesis
\(\displaystyle \implies \ \ \) \(\displaystyle x \times \left({y \times z^+}\right)\) \(=\) \(\displaystyle x \times \left({\left({y \times z}\right) + y}\right)\) Definition of Ordinal Multiplication
\(\displaystyle \) \(=\) \(\displaystyle x \times \left({y \times z}\right) + \left({x \times y}\right)\) Ordinal Multiplication is Left Distributive
\(\displaystyle \) \(=\) \(\displaystyle \left({x \times y}\right) \times z + \left({x \times y}\right)\) Inductive Hypothesis
\(\displaystyle \) \(=\) \(\displaystyle \left({x \times y}\right) \times z^+\) Definition of Ordinal Multiplication

This proves the induction step.


Limit Case

The inductive hypothesis for the limit case states that:

$\forall w \in Z: x \times \left({y \times w}\right) = \left({x \times y}\right) \times w$

where $z$ is a limit ordinal.


The proof shall proceed by cases:


Case 1

If $y = 0$, then:

\(\displaystyle x \times \left({y \times z}\right)\) \(=\) \(\displaystyle x \times 0\) Ordinal Multiplication by Zero
\(\displaystyle \) \(=\) \(\displaystyle 0\) Ordinal Multiplication by Zero
\(\displaystyle \) \(=\) \(\displaystyle 0 \times z\) Ordinal Multiplication by Zero
\(\displaystyle \) \(=\) \(\displaystyle \left({x \times y}\right) \times z\) Ordinal Multiplication by Zero


Case 2

If $y \ne 0$, then $y \times z$ is a limit ordinal by Limit Ordinals Preserved Under Ordinal Multiplication.


It follows that:

\(\displaystyle x \times \left({y \times z}\right)\) \(=\) \(\displaystyle \bigcup_{u \mathop < \left({y \times z}\right)} x \times u\) Definition of Ordinal Multiplication
\(\displaystyle \left({x \times y}\right) \times z\) \(=\) \(\displaystyle \bigcup_{w \mathop < z} \left({x \times y}\right) \times w\) Definition of Ordinal Multiplication


If $u < \left({y \times z}\right)$, then $u < \left({y \times w}\right)$ for some $w \in z$ by Ordinal is Less than Ordinal times Limit.

\(\displaystyle x \times u\) \(\le\) \(\displaystyle x \times \left({y \times w}\right)\) Membership is Left Compatible with Ordinal Multiplication
\(\displaystyle \) \(=\) \(\displaystyle \left({x \times y}\right) \times w\) Inductive Hypothesis
\(\displaystyle \) \(\le\) \(\displaystyle \left({x \times y}\right) \times z\) Subset is Right Compatible with Ordinal Multiplication


Generalizing, the result follows for all $u \in \left({y \times z}\right)$.

Therefore by Supremum Inequality for Ordinals:

$x \times \left({y \times z}\right) \le \left({x \times y}\right) \times z$


Conversely, take any $w < z$.

\(\displaystyle \left({x \times y}\right) \times w\) \(=\) \(\displaystyle x \times \left({y \times w}\right)\) Inductive Hypothesis
\(\displaystyle \) \(\le\) \(\displaystyle x \times \left({y \times z}\right)\) Membership is Left Compatible with Ordinal Multiplication


It follows by Supremum Inequality for Ordinals that:

$\left({x \times y}\right) \times z \le x \times \left({y \times z}\right)$


By definition of set equality:

$x \times \left({y \times z}\right) = \left({x \times y}\right) \times z$


This proves the limit case.

$\blacksquare$


Sources