Surjection on Total Ordering reflects Preordering
Theorem
Let $\struct {S, \preccurlyeq}$ be a totally ordered set.
Let $f: S \to T$ be a mapping to an arbitrary set $T$.
Let $\RR$ be a relation on $T$ defined such that:
- $\RR: = \set {\tuple {\map f x, \map f y}: x \preccurlyeq y}$
That is, $a$ is related to $b$ in $T$ if and only if they have preimages $x$ and $y$ under $f$ such that $x$ precedes $y$.
Then:
- $f$ is a surjection onto set $T$
- $\RR$ is a preordering on $T$
Proof
Sufficient Condition
Let $f: S \to T$ be a surjection.
By definition, a preordering is a relation which is both transitive and reflexive.
From Mapping on Total Ordering reflects Transitivity, $\RR$ is a transitive relation.
It remains to be shown that $\RR$ is a reflexive relation.
Let $a \in T$.
Because $f$ is a surjection, it follows that:
- $\exists x \in S: a = \map f x$
Because $\preccurlyeq$ is a total ordering on $S$, it follows that:
- $x \preccurlyeq x$
Hence by definition of $\RR$:
- $\map f x \mathrel \RR \map f x$
That is:
- $a \mathrel \RR a$
As $a$ was arbitrary, it follows that $\RR$ is reflexive.
Hence it follows that $\RR$ is a preordering.
$\blacksquare$
Necessary Condition
Let $\RR$ be a preordering on $T$.
Then $\RR$ is a relation which is both transitive and reflexive.
Let $a \in T$.
As $\RR$ is reflexive, it follows that:
- $\forall a \in T: a \mathrel \RR a$
That is:
- $\forall a \in T: \exists x \in S: \map f x \mathrel \RR \map f x$
where $a = \map f x$
That means:
- $\forall a \in T: \exists x \in S: a = \map f x$
That is:
- $f$ is a surjection.
$\blacksquare$
Sources
- 1996: Winfried Just and Martin Weese: Discovering Modern Set Theory. I: The Basics ... (previous) ... (next): Part $1$: Not Entirely Naive Set Theory: Chapter $2$: Partial Order Relations: Exercise $41 \ \text {(b)}$