# Ordinal Multiplication is Associative

## Theorem

Let $x, y, z$ be ordinals.

Let $\times$ denote ordinal multiplication.

Then:

$x \times \paren {y \times z} = \paren {x \times y} \times z$

## Proof

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

### Basis for the Induction

Let $0$ denote the zero ordinal.

 $\ds x \times \paren {y \times 0}$ $=$ $\ds x \times 0$ Ordinal Multiplication by Zero $\ds$ $=$ $\ds 0$ Ordinal Multiplication by Zero $\ds$ $=$ $\ds \paren {x \times y} \times 0$ Ordinal Multiplication by Zero

This proves the basis for the induction.

### Induction Step

 $\ds x \times \paren {y \times z}$ $=$ $\ds \paren {x \times y} \times z$ Inductive Hypothesis $\ds \leadsto \ \$ $\ds x \times \paren {y \times z^+}$ $=$ $\ds x \times \paren {\paren {y \times z} + y}$ Definition of Ordinal Multiplication $\ds$ $=$ $\ds x \times \paren {y \times z} + \paren {x \times y}$ Ordinal Multiplication is Left Distributive $\ds$ $=$ $\ds \paren {x \times y} \times z + \paren {x \times y}$ Inductive Hypothesis $\ds$ $=$ $\ds \paren {x \times y} \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 \paren {y \times w} = \paren {x \times y} \times w$

where $z$ is a limit ordinal.

The proof shall proceed by cases:

### Case 1

If $y = 0$, then:

 $\ds x \times \paren {y \times z}$ $=$ $\ds x \times 0$ Ordinal Multiplication by Zero $\ds$ $=$ $\ds 0$ Ordinal Multiplication by Zero $\ds$ $=$ $\ds 0 \times z$ Ordinal Multiplication by Zero $\ds$ $=$ $\ds \paren {x \times y} \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:

 $\ds x \times \paren {y \times z}$ $=$ $\ds \bigcup_{u \mathop < \paren {y \times z} } x \times u$ Definition of Ordinal Multiplication $\ds \paren {x \times y} \times z$ $=$ $\ds \bigcup_{w \mathop < z} \paren {x \times y} \times w$ Definition of Ordinal Multiplication

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

 $\ds x \times u$ $\le$ $\ds x \times \paren {y \times w}$ Membership is Left Compatible with Ordinal Multiplication $\ds$ $=$ $\ds \paren {x \times y} \times w$ Inductive Hypothesis $\ds$ $\le$ $\ds \paren {x \times y} \times z$ Subset is Right Compatible with Ordinal Multiplication

Generalizing, the result follows for all $u \in \paren {y \times z}$.

Therefore by Supremum Inequality for Ordinals:

$x \times \paren {y \times z} \le \paren {x \times y} \times z$

Conversely, take any $w < z$.

 $\ds \paren {x \times y} \times w$ $=$ $\ds x \times \paren {y \times w}$ Inductive Hypothesis $\ds$ $\le$ $\ds x \times \paren {y \times z}$ Membership is Left Compatible with Ordinal Multiplication

It follows by Supremum Inequality for Ordinals that:

$\paren {x \times y} \times z \le x \times \paren {y \times z}$

By definition of set equality:

$x \times \paren {y \times z} = \paren {x \times y} \times z$

This proves the limit case.

$\blacksquare$