Ordinal Multiplication is Left Distributive

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $x$, $y$, and $z$ be ordinals.

Let $\times$ denote ordinal multiplication.

Let $+$ denote ordinal addition.


Then:

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


Proof

The proof shall proceed by Transfinite Induction, as follows:


Basis for the Induction

Let $0$ denote the ordinal zero.

\(\displaystyle x \times \left({ y + 0 }\right)\) \(=\) \(\displaystyle x \times y\) Definition of Ordinal Addition
\(\displaystyle \) \(=\) \(\displaystyle \left({ x \times y }\right) + 0\) Definition of Ordinal Addition
\(\displaystyle \) \(=\) \(\displaystyle \left({ x \times y }\right) + \left({ x \times 0 }\right)\) Definition of Ordinal Multiplication

This proves the basis for the induction.


Induction Step

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

This proves the induction step.


Limit Case

The inductive hypothesis for the limit case states that:

$x \times \left({ y + w }\right) = \left({ x \times y }\right) + \left({ x \times w }\right)$ for all $w \in z$ and $z$ is a limit ordinal.


The proof shall proceed by cases:


Case 1

Suppose $x = 0$.

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


Case 2

Suppose that $x \ne 0$.

Since $w$ is a limit ordinal, $y + w$ and $x \times w$ are limit ordinals by Limit Ordinals Preserved Under Ordinal Addition and Limit Ordinals Preserved Under Ordinal Multiplication.

\(\displaystyle x \times \left({ y + z }\right)\) \(=\) \(\displaystyle \bigcup_{w \mathop \in \left({ y + z }\right)} \left({ x \times w }\right)\) Definition of Ordinal Multiplication
\(\displaystyle \left({ x \times y }\right) + \left({ x \times z }\right)\) \(=\) \(\displaystyle \bigcup_{v \mathop \in \left({ x \times z }\right)} \left({ x \times y }\right) + v\) Definition of Ordinal Addition


Take any $w \in \left({ y + z }\right)$.

It follows that $w \in y \lor \left({ y \subseteq w \land w \in \left({ y + z }\right) }\right)$ by Relation between Two Ordinals and Transitive Set is Proper Subset of Ordinal iff Element of Ordinal.

Thus, $\left({ w \in y \lor w = \left({ y + u }\right) }\right)$ for some $u \in z$ by Ordinal Subtraction when Possible is Unique.


If $w < y$, then:

\(\displaystyle \left({ x \times w }\right)\) \(\in\) \(\displaystyle \left({ x \times y }\right)\) Membership is Left Compatible with Ordinal Multiplication
\(\displaystyle \) \(\subseteq\) \(\displaystyle \left({ x \times y }\right) + v\) Ordinal is Less than Sum


If $w = \left({ y + u }\right)$, then:

\(\displaystyle x \times w\) \(=\) \(\displaystyle x \times \left({ y + u }\right)\) definition of $w$
\(\displaystyle \) \(=\) \(\displaystyle \left({ x \times y }\right) + \left({ x \times u }\right)\) Inductive Hypothesis
\(\displaystyle \left({ x \times u }\right)\) \(\in\) \(\displaystyle \left({ x \times z }\right)\) Membership is Left Compatible with Ordinal Multiplication
\(\displaystyle \) \(=\) \(\displaystyle \left({ x \times y }\right) + v\) setting $v$ to $x \times u$

By Supremum Inequality for Ordinals:

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


Conversely, if $v \in \left({ x \times z }\right)$, then:

\(\displaystyle \exists w \in z: \ \ \) \(\displaystyle v\) \(\in\) \(\displaystyle \left({ x \times w }\right)\) Ordinal is Less than Ordinal times Limit
\(\displaystyle \implies \ \ \) \(\displaystyle \left({ x \times y }\right) + v\) \(=\) \(\displaystyle \left({ x \times y }\right) + \left({ x \times w }\right)\) Substitutivity of Class Equality
\(\displaystyle \) \(=\) \(\displaystyle x \times \left({ y + w }\right)\) Inductive Hypothesis

By Supremum Inequality for Ordinals:

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


By definition of set equality:

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

This proves the limit case.

$\blacksquare$


Sources