Division Theorem for Ordinals

From ProofWiki
Jump to: navigation, search

Theorem

Let $x$ and $y$ be ordinals.

Let $0$ denote the zero ordinal.

Suppose $y \ne 0$.


Then there exist unique ordinals $z$ and $w$ such that:

$x = \left({ y \times z }\right) + w$ and $w < y$.


Proof

Existence of $z$ and $w$

First, it must be proven that such $z$ and $w$ exist.


By Relation between Two Ordinals, it follows that:

$x < y$ or $y \le x$

The proof shall proceed by cases.


Case 1

If $x < y$, then set $z = 0$ and $w = x$.

Since $w = x$, then $w < y$. Furthermore:

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


Case 2

If $y \le x$, then set $z = \bigcup \left\{ v : \left({ y \times v }\right) \le x \right\}$.

Set $w$ equal to the unique $u$ such that $\left({ y \times z }\right) + u = x$.

By Ordinal Multiplication by One, it follows that $1 \le z$.


By Union of Ordinals is Least Upper Bound, it follows that $z$ is the least upper bound of $\left\{ v : \left({ y \times v }\right) \le x \right\}$.

Take any $u \in z$.

Then $u \in v$ for some $\left({ y \times v }\right) \le x$

But then, by Membership is Left Compatible with Ordinal Multiplication, it follows that $\left({ y \times u }\right) \le x$.

So $z$ is a transitive subset of $\operatorname{On}$ and therefore, it is an ordinal.


Since $z \ne 0$, then by the definition of limit ordinal, then $z = u^+$ for some $u$ or $z$ is a limit ordinal.


Suppose $z = u^+$.

Then $u < z$ and $y \times u \le x$.

Moreover, $u < v$ for some $y \times v \le x$.

This means that $v \not < z$ by No Ordinal Between Set and Successor.

By Ordinal Membership is Trichotomy, $z \le v$.

Therefore:

$y \times z \le x$


Suppose $z \in K_{II}$.

Note that $\forall u \in z: y \times u \le x$ so:

\(\displaystyle y \times z\) \(=\) \(\displaystyle \bigcup_{u \in z} \left({ y \times u }\right)\) definition of ordinal multiplication
\(\displaystyle \) \(\le\) \(\displaystyle \bigcup_{u \in z} x\) Indexed Union Subset
\(\displaystyle \) \(=\) \(\displaystyle x\) Union is Idempotent

In either case, $y \times z \le x$.


Moreover, suppose that $y \times z^+ \le x$.

Then $z$ is not an upper bound of the set $\left\{ v : \left({ y \times v }\right) \le x \right\}$, which is a contradiction.


So $\left({ y \times z }\right) + w = x$ for some $w \in y$ by Ordinal Subtraction when Possible is Unique.


Uniqueness of $z$ and $w$

Suppose that $\left({ y \times z_1 }\right) + w_1 = x$ for some $w_1 \in y$.

Suppose that $\left({ y \times z_2 }\right) + w_2 = x$ for some $w_2 \in y$.


Then for both $z = z_1$ and $z = z_2$, the following inequality is established:

\(\displaystyle y \times z\) \(\le\) \(\displaystyle x\) Ordinal is Less than Sum
\(\displaystyle \) \(<\) \(\displaystyle \left({ y \times z }\right) + y\) Membership is Left Compatible with Ordinal Addition
\(\displaystyle \) \(=\) \(\displaystyle y \times z^+\) Definition of Ordinal Multiplication


It follows that $y \times z_1 < y \times z_2^+$ and $y \times z_2 < y \times z_1^+$.

By Membership is Left Compatible with Ordinal Multiplication, $z_1 < z_2^+$ and $z_2 < z_1^+$.


\(\displaystyle z_1 < z_2^+\) \(\implies\) \(\displaystyle z_1 < z_2 \lor z_1 = z_2\) Definition of Successor Set
\(\displaystyle \) \(\implies\) \(\displaystyle z_1 \le z_2\)
\(\displaystyle z_2 < z_1^+\) \(\implies\) \(\displaystyle z_2 \le z_1\) Definition of Successor Set
\(\displaystyle \) \(\implies\) \(\displaystyle z_1 = z_2\) Definition of Set Equality


Therefore $z$ is unique.


Since $z$ is unique, then $w$ is unique by Ordinal Subtraction when Possible is Unique.

$\blacksquare$


Sources