Subset is Right Compatible with Ordinal Multiplication

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $x, y, z$ be ordinals.


Then:

$x \le y \implies \left({x \cdot z}\right) \le \left({y \cdot z}\right)$


Proof

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


Basis for the Induction

By definition of ordinal multiplication:

$\left({x \cdot 0}\right) = 0$

so the statement simply reduces to:

$0 \le 0$

This proves the basis for the induction.


Induction Step

\(\displaystyle x\) \(\le\) \(\displaystyle y\)
\(\displaystyle \implies \ \ \) \(\displaystyle \left({x \cdot z}\right)\) \(\le\) \(\displaystyle \left({y \cdot z}\right)\) Inductive Hypothesis
\(\displaystyle \implies \ \ \) \(\displaystyle \left({\left({x \cdot z}\right) + x}\right)\) \(\le\) \(\displaystyle \left({\left({y \cdot z}\right) + y}\right)\) Membership is Left Compatible with Ordinal Addition and Subset is Right Compatible with Ordinal Addition
\(\displaystyle \implies \ \ \) \(\displaystyle \left({x \cdot z^+}\right)\) \(\le\) \(\displaystyle \left({y \cdot z^+}\right)\) Definition of Ordinal Multiplication

This proves the induction step.


Limit Case

\(\displaystyle x\) \(\le\) \(\displaystyle y\)
\(\displaystyle \implies \ \ \) \(\, \displaystyle \forall w \in z: \, \) \(\displaystyle \left({x \cdot w}\right)\) \(\le\) \(\displaystyle \left({y \cdot w}\right)\) Inductive Hypothesis
\(\displaystyle \implies \ \ \) \(\displaystyle \bigcup_{w \mathop \in z} \left({x \cdot w}\right)\) \(\le\) \(\displaystyle \bigcup_{w \mathop \in z} \left({y \cdot w}\right)\) Indexed Union Subset
\(\displaystyle \implies \ \ \) \(\displaystyle \left({x \cdot z}\right)\) \(\le\) \(\displaystyle \left({y \cdot z}\right)\) Definition of Ordinal Multiplication

This proves the limit case.

$\blacksquare$


Also see


Sources