# Mapping on Integers is Endomorphism of Max or Min Operation iff Increasing

## Theorem

Let $\Z$ denote the set of integers.

Let $f: \Z \to \Z$ be a mapping on $\Z$.

Let $\vee$ and $\wedge$ be the max operation and min operation on $\Z$ defined as:

 $\ds \forall x, y \in \Z: \,$ $\ds x \vee y$ $=$ $\ds \max \set {x, y}$ $\ds x \wedge y$ $=$ $\ds \min \set {x, y}$

Then:

$f$ is an endomorphism of $\struct {\Z, \vee}$ or $\struct {\Z, \wedge}$
$f$ is an increasing mapping.

## Proof

### Necessary Condition

Suppose $f$ is an increasing mapping.

Let $x, y \in \Z$ and suppose $x \le y$.

By definition of an increasing mapping, we have $\map f x \le \map f y$.

Therefore:

$\map f x \vee \map f y = \map f y = \map f {x \vee y}$
$\map f x \wedge \map f y = \map f x = \map f {x \wedge y}$

Hence $f$ is an endomorphism of $\struct {\Z, \vee}$ and $\struct {\Z, \wedge}$.

As Conjunction implies Disjunction, $f$ is an endomorphism of $\struct {\Z, \vee}$ or $\struct {\Z, \wedge}$.

$\Box$

### Sufficient Condition

Suppose $f$ is an endomorphism of $\struct {\Z, \vee}$.

Then for any $x, y \in \Z$, we have:

$\map f x \vee \map f y = \map f {x \vee y}$

Without loss of generality suppose $x \le y$.

Then we have:

$\map f y = \map f {x \vee y} = \map f x \vee \map f y$

and thus:

$\map f x \le \map f y$

Hence $f$ is an increasing mapping.

Now suppose $f$ is an endomorphism of $\struct {\Z, \wedge}$.

Then for any $x, y \in \Z$, we have:

$\map f x \wedge \map f y = \map f {x \wedge y}$

Without loss of generality suppose $x \le y$.

Then we have:

$\map f x = \map f {x \wedge y} = \map f x \wedge \map f y$

and thus:

$\map f x \le \map f y$

Hence $f$ is an increasing mapping.

Therefore if $f$ is an endomorphism of either $\struct {\Z, \vee}$ or $\struct {\Z, \wedge}$, $f$ is an increasing mapping.

$\blacksquare$