Mapping reflects Preordering

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ and $T$ be sets.

Let $f: S \to T$ be a mapping.

Let ${\precsim} \subseteq T \times T$ be a preordering on $T$.


Let $\mathcal R$ be the relation defined on $S$ by the rule:

$x \mathrel {\mathcal R} y \iff \map f x \precsim \map f y$

Then $\mathcal R$ is a preordering on $S$.


Proof

Reflexivity

\(\displaystyle x\) \(\in\) \(\displaystyle S\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map f x\) \(\in\) \(\displaystyle T\) Definition of $f$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map f x\) \(\precsim\) \(\displaystyle \map f x\) as $\precsim$ is a preordering on $T$
\(\displaystyle \leadsto \ \ \) \(\displaystyle x\) \(\mathcal R\) \(\displaystyle x\) by definition of $\mathcal R$

Thus $\mathcal R$ is reflexive.

$\Box$


Transitivity

\(\displaystyle x\) \(\mathcal R\) \(\displaystyle y\)
\(\, \displaystyle \land \, \) \(\displaystyle y\) \(\mathcal R\) \(\displaystyle z\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map f x\) \(\precsim\) \(\displaystyle \map f y\)
\(\, \displaystyle \land \, \) \(\displaystyle \map f y\) \(\precsim\) \(\displaystyle \map f z\) by definition of $\mathcal R$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map f x\) \(\precsim\) \(\displaystyle \map f z\) as $\precsim$ is a preordering on $T$
\(\displaystyle \leadsto \ \ \) \(\displaystyle x\) \(\mathcal R\) \(\displaystyle z\) by definition of $\mathcal R$

Thus $\mathcal R$ is transitive.

$\Box$


So, by definition, $\mathcal R$ is a preordering.

$\blacksquare$


Sources