Surjection on Total Ordering reflects Preordering

From ProofWiki
Jump to navigation Jump to search

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$

if and only if:

$\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