Mapping on Integers is Homomorphism between Max or Min Operation iff Decreasing

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\Z$ denote the set of integers.

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



Let $\vee$ and $\wedge$ be the operations 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 a homomorphism either from $\struct {\Z, \vee}$ to $\struct {\Z, \wedge}$ or from $\struct {\Z, \wedge}$ to $\struct {\Z, \vee}$

if and only if:

$f$ is a decreasing mapping.


Proof

Necessary Condition

Let $f$ be a decreasing mapping.

Let $x, y \in \Z$ such that $x \le y$.

By definition of a decreasing mapping, we have $\map f x \ge \map f y$.

Therefore:

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

Hence:

$f$ is a homomorphism from $\struct {\Z, \vee}$ to $\struct {\Z, \wedge}$

and also:

$f$ is a homomorphism from $\struct {\Z, \wedge}$ to $\struct {\Z, \vee}$

As Conjunction implies Disjunction, $f$ is a homomorphism from $\struct {\Z, \vee}$ to $\struct {\Z, \wedge}$ or from $\struct {\Z, \wedge}$ to $\struct {\Z, \vee}$.

$\Box$


Sufficient Condition

Suppose $f$ is a homomorphism from $\struct {\Z, \wedge}$ to $\struct {\Z, \vee}$.

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

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

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

Then we have:

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

and thus:

$\map f x \ge \map f y$

Hence $f$ is a decreasing mapping.


Now suppose $f$ is a homomorphism from $\struct {\Z, \vee}$ to $\struct {\Z, \wedge}$.

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

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

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

Then we have:

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

and thus:

$\map f x \ge \map f y$

Hence $f$ is a decreasing mapping.


Therefore if $f$ is a homomorphism either from $\struct {\Z, \vee}$ to $\struct {\Z, \wedge}$ or from $\struct {\Z, \wedge}$ to $\struct {\Z, \vee}$, $f$ is a decreasing mapping.

$\blacksquare$


Sources