Ordinal Multiplication via Cantor Normal Form/Limit Base

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $x$ and $y$ be ordinals.

Let $x$ be a limit ordinal.

Let $y > 0$.

Let $\left\langle{a_i}\right\rangle$ be a sequence of ordinals that is strictly decreasing on $1 \le i \le n$.

Let $\left\langle{b_i}\right\rangle$ be a sequence of finite ordinals.


Then:

$\displaystyle \sum_{i \mathop = 1}^n \left({x^{a_i} b_i}\right) \times x^y = x^{a_1 \mathop + y}$



Proof

The proof shall proceed by finite induction on $n$:

For all $n \in \N_{\le 0}$, let $P \left({n}\right)$ be the proposition:

$\displaystyle \sum_{i \mathop = 1}^n \left({ x^{a_i} b_i}\right) \times x^y = x^{a_1 \mathop + y}$


Since $x$ is a limit ordinal, it follows that $x^y$ is a limit ordinal by Limit Ordinals Closed under Ordinal Exponentiation.


Basis for the Induction

$P \left({1}\right)$ is the statement:

$\displaystyle \sum_{i \mathop = 1}^1 \left({x^{a_i} b_i}\right) \times x^y = x^{a_1 \mathop + y}$


\(\displaystyle \sum_{i \mathop = 1}^1 \left({ x^{a_i} b_i }\right) \times x^y\) \(=\) \(\displaystyle \left({ x^{a_i} \times b_i }\right) \times x^y\) Definition of Ordinal Sum
\(\displaystyle \) \(=\) \(\displaystyle x^{a_i} \times \left({ b_i \times x^y }\right)\) Ordinal Multiplication is Associative
\(\displaystyle \) \(=\) \(\displaystyle x^{a_i} \times x^y\) Finite Ordinal Times Ordinal
\(\displaystyle \) \(=\) \(\displaystyle x^{a_i \mathop + y}\) Ordinal Sum of Powers

This is our basis for the induction.

$\Box$


Induction Hypothesis

Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 1$, then it logically follows that $P \left({k+1}\right)$ is true.


So this is our induction hypothesis:

$\displaystyle \sum_{i \mathop = 1}^k \left({ x^{a_i} b_i }\right) \times x^y = x^{a_1 + y}$


Then we need to show:

$\displaystyle \sum_{i \mathop = 1}^{k \mathop + 1} \left({ x^{a_i} b_i }\right) \times x^y = x^{a_1 \mathop + y}$


Induction Step

This is our induction step:

By Upper Bound of Ordinal Sum, it follows that:

$\displaystyle \sum_{i \mathop = 1}^n \left({ x^{a_{i \mathop + 1} } b_{i \mathop + 1} }\right) < x^{a_1}$


By Membership is Left Compatible with Ordinal Multiplication:

\(\displaystyle x^{a_1} b_1\) \(\le\) \(\displaystyle x^{a_1} b_1 + \sum_{i \mathop = 1}^k \left({ x^{a_{i \mathop + 1} } b_{i \mathop + 1} }\right)\) Ordinal is Less than Sum
\(\displaystyle \) \(\le\) \(\displaystyle x^{a_1} b_1 + x^{a_1}\) Membership is Left Compatible with Ordinal Addition
\(\displaystyle \implies \ \ \) \(\displaystyle x^{a_1} \times b_1 \times x^y\) \(\le\) \(\displaystyle \sum_{i \mathop = 1}^{k \mathop + 1} \left({ x^{a_i} b_i}\right) \times x^y\) Subset is Right Compatible with Ordinal Multiplication and General Associative Law for Ordinal Sum
\(\displaystyle \) \(\le\) \(\displaystyle x^{a_1} \times \left({ b_1 + 1 }\right) \times x^y\) Subset is Right Compatible with Ordinal Multiplication


But:

\(\displaystyle x^{a_1} \times b_1 \times x^y\) \(=\) \(\displaystyle x^{a_1} \times x^y\) Finite Ordinal Times Ordinal
\(\displaystyle \) \(=\) \(\displaystyle x^{a_1 \mathop + y}\) Ordinal Sum of Powers
\(\displaystyle x^{a_1} \times \left({ b_1 + 1 }\right) \times x^y\) \(=\) \(\displaystyle x^{a_1} \times x^y\) Finite Ordinal Times Ordinal
\(\displaystyle \) \(=\) \(\displaystyle x^{a_1 \mathop + y}\) Ordinal Sum of Powers


Therefore:

\(\displaystyle x^{a_1 \mathop + y}\) \(\le\) \(\displaystyle \sum_{i \mathop = 1}^n \left({ x^{a_i} b_i }\right) \times x^y\) Substitutivity of Class Equality
\(\displaystyle \) \(\le\) \(\displaystyle x^{a_1 \mathop + y}\) Substitutivity of Class Equality
\(\displaystyle \implies \ \ \) \(\displaystyle \sum_{i \mathop = 1}^n \left({ x^{a_i} b_i }\right) \times x^y\) \(=\) \(\displaystyle x^{a_1 \mathop + y}\) Definition of Set Equality

$\blacksquare$


Also see


Sources