Basis Representation Theorem for Ordinals

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $x$ and $y$ be ordinals.

Let $x > 1$ and $y > 0$.


Then there exist unique finite sequences of ordinals:

$\left\langle{a_i}\right\rangle, \ \left\langle{b_i}\right\rangle$

both of unique length $n$ such that:

$(1): \quad \left\langle{a_i}\right\rangle$ is a strictly decreasing sequence for $1 \le i \le n$
$(2): \quad 0 < b_i < x$ for all $1 \le i \le n$
$(3): \quad \displaystyle y = \sum_{i \mathop = 1}^n x^{a_i} b_i$


Proof

The proof shall proceed by Transfinite Induction (Strong Induction) on $y$.


The inductive hypothesis states that for all $v < y$, there exist unique finite sequences of ordinals:

$\left\langle{c_i}\right\rangle, \ \left\langle{d_i}\right\rangle$

both of unique length $n$ such that:

$(1): \quad \left\langle{c_i}\right\rangle$ is strictly decreasing sequence for $1 \le i \le n$
$(2): \quad 0 < d_i < x$ for all $1 \le i \le n$.
$(3): \quad \displaystyle v = \sum_{i \mathop = 1}^n x^{c_i} d_i$


Since $x > 1$, it follows by Unique Ordinal Exponentiation Inequality that:

$x^z \le y < x^{z+1}$

for some unique $z$.


By the Division Theorem for Ordinals:

$y = x^z w + v$ and $v < x^z$

for some unique $z$, $w$, and $v$.


Thus:

\(\displaystyle v\) \(<\) \(\displaystyle x^z\) by Division Theorem for Ordinals, as shown above
\(\displaystyle \) \(\le\) \(\displaystyle y\) by Unique Ordinal Exponentiation Inequality, as shown above

So $v < y$.

If $v = 0$, then the statement is proven.


If $v \ne 0$, then we may apply the inductive hypothesis.

By the inductive hypothesis,

$\displaystyle v = \sum_{i \mathop = 1}^n x^{c_i} d_i$


Therefore, $\displaystyle y = x^z w + \sum_{i \mathop = 1}^n x^{c_i} d_i$

$\Box$


Set:

$a_1 = z$
$a_{i + 1} = c_i$ for $1 \le i \le n$
$b_1 = w$
$b_{i + 1} = d_i$ for $1 \le i \le n$


Since $w \ne 0$ and $d_i \ne 0$, it follows that $b_i \ne 0$ for all $1 \le i \le n+1$.

$\Box$


Moreover, since $z > c_1$ and $\left\langle{c_i}\right\rangle$ is strictly decreasing, it follows that also $\left\langle{a_i}\right\rangle$ is strictly decreasing.

$\Box$


The equation for the first lemma can be rewritten:

$\displaystyle y = x^{a_1} b_1 + \sum_{i \mathop = 1}^n x^{a_{i + 1} } b_{i + 1}$

By General Associative Law for Ordinal Sum, it follows that:

$\displaystyle y = \sum_{i \mathop = 1}^{n + 1} x^{a_i} b_i$

Thus, existence is proven.

$\Box$


Furthermore, since $z$ and $\left\langle{c_i}\right\rangle$ are unique, and $w$ and $\left\langle{a_i}\right\rangle$ are unique, then $\left\langle{a_i}\right\rangle$ and $\left\langle{b_i}\right\rangle$ are unique.

$\blacksquare$


Also see


Sources