Characterization of Strictly Increasing Mapping on Woset

From ProofWiki
Jump to navigation Jump to search

Lemma

Let $J$ and $E$ be well-ordered sets.

Let $h: J \to E$ be a mapping.

Let $S_\alpha$ denote an initial segment determined by $\alpha$.


The following are equivalent:

$(1):\quad$ $h$ is strictly increasing and its image is either all of $E$ or an initial segment of $E$
$(2):\quad$ $\forall \alpha \in J: h\left({\alpha}\right) = \min \left({E\setminus h\left[{S_\alpha}\right]}\right)$, and $h[S_\alpha] = S_{h(\alpha)}$

where:

$h\left[{S_\alpha}\right]$ denotes the image of $S_\alpha$ under $h$
$\min$ denotes the smallest element of the set.


Proof

$(1)$ implies $(2)$

Suppose $h$ satisfies:

$h$ is strictly increasing and its image is either all of $E$ or an initial segment of $E$

Then for any $x,y \in J$:

\(\displaystyle x\) \(\prec\) \(\displaystyle y\)
\(\displaystyle \implies \ \ \) \(\displaystyle h(x)\) \(\prec\) \(\displaystyle h(y)\) Definition of strictly increasing
\(\displaystyle h[S_y]\) \(=\) \(\displaystyle \left\{ { h(x) \in E: \exists x \in J: h(x) \prec h(y) } \right\}\)
\(\displaystyle \) \(=\) \(\displaystyle S_{h(y)}\)
\(\displaystyle \min\left({E \setminus h\left[{S_y}\right] }\right)\) \(=\) \(\displaystyle \min\left({E \setminus S_{h(y)} }\right)\)
\(\displaystyle \) \(=\) \(\displaystyle h(y)\) Definition of smallest and of initial segment

$\Box$


$(2)$ implies $(1)$

Suppose $h$ satisfies:

$h(\alpha) = \min\left({E \setminus h\left[{S_\alpha}\right] }\right)$

By the Principle of Recursive Definition for Well-Ordered Sets, $h$ is thus uniquely determined.


Then:

\(\displaystyle h(y)\) \(=\) \(\displaystyle \min\left({E \setminus h\left[{S_y}\right] }\right)\)
\(\displaystyle h[S_y]\) \(=\) \(\displaystyle \left\{ { h(x) \in E: \exists x \in J: h(x) = \min\left({E \setminus h\left[{S_y }\right] }\right)} \right\}\)
\(\displaystyle \) \(=\) \(\displaystyle \left\{ { h(x) \in E: \exists x \in J: h(x) \prec h(y)} \right\}\)
\(\displaystyle \) \(=\) \(\displaystyle S_{h(y)}\) Definition of initial segment

Thus for every $x \in S_y$, we have that $h(x) \in S_{h(y)}$.

Therefore $h$ is an strictly increasing mapping.

Furthermore, the image set of $h$ is the union of initial segments in $E$.

By Union of Initial Segments is Initial Segment or All of Woset, $h[J]$ is an initial segment of $E$ or all of $E$.

$\blacksquare$

Sources