properties of certain monotone functions

In the definitions of some partially ordered algebraic systems such as po-groups and po-rings, the multiplication is set to be compatible with the partial ordering on the universe in the following sense:

$$ab\le ac\mathit{\hspace{1em}}\text{iff}\mathit{\hspace{1em}}b\le c\mathit{\hspace{1em}\hspace{1em}}\text{ and }\mathit{\hspace{1em}\hspace{1em}}ab\le cb\mathit{\hspace{1em}}\text{iff}\mathit{\hspace{1em}}a\le c$$

This is no coincidence. In fact, these “definitions” are actually consequences of properties concerning monotone functions satisfying certain algebraic rules, which is the focus of this entry.

Recall that an $n$-ary function $f$ on a set $A$ is said to be monotone if it is monotone in each of its variables. In other words, for every $i=1,2,\mathrm{\dots },n$, the function $f(a_1,\mathrm{\dots },a_{i-1},x,a_{i+1},\mathrm{\dots },a_n)$ is monotone in $x$, where each of the $a_j$ is a fixed but arbitrary element of $A$. We use the notation $\uparrow ,\downarrow ,\updownarrow$ to denote the monotonicity of each variable in $f$. For example, $(\uparrow ,\uparrow ,\uparrow )$ denotes a ternary isotone function, whereas $(\downarrow ,\updownarrow )$ denotes a binary function which is antitone with respect to its first variable, and both isotone/antitone with respect to the second.

Proposition 1.

Let $f$ be an $n$-ary commutative monotone operation on a set $A$. Then $f$ is either isotone or antitone.

Proof.

Suppose $f$ is isotone (or antitone) in its first variable. Since $f(x,a_1,\mathrm{\dots },a_{n-1})=f(a_1,x,\mathrm{\dots },a_{n-1})=\mathrm{\cdots }=f(a_1,\mathrm{\dots },a_{n-1},x)$, $f$ is isotone (or antitone) in each of its remaining variables. ∎

Proposition 2.

Let $f$ be an $n$-ary monotone operation on a set $A$ with an identity element $e\mathrm{\in }A$. In other words, $f\mathit{}\mathrm{(}x\mathrm{,}e\mathrm{,}\mathrm{\dots }\mathrm{,}e\mathrm{)}\mathrm{=}f\mathit{}\mathrm{(}e\mathrm{,}x\mathrm{,}\mathrm{\dots }\mathrm{,}e\mathrm{)}\mathrm{=}\mathrm{\cdots }\mathrm{=}f\mathit{}\mathrm{(}e\mathrm{,}e\mathrm{,}\mathrm{\dots }\mathrm{,}x\mathrm{)}\mathrm{=}x$. Then $f$ is either strictly isotone or strictly antitone.

Proof.

The proof is the same as the one before. Furthermore, if $f$ is isotone and , then , so the strict ordering is preserved. The same holds true if $f$ is antitone. ∎

Proposition 3.

Let $f$ be a binary monotone operation on a set $A$ such that it is isotone (antitone) with respect to its first variable. Suppose $g$ is a unary operation on $A$ such that $f\mathit{}\mathrm{(}x\mathrm{,}g\mathit{}\mathrm{(}x\mathrm{)}\mathrm{)}$ is a fixed element of $A$. Then $g$ is antitone (isotone).

Proposition 4.

Let $f$ be an $n$-ary associative monotone operation on a set $A$. Then

• $f$ is isotone if $n$ is even

• $f$ is either isotone, or is $(\underset{m}{\underbrace{\uparrow ,\mathrm{\dots },\uparrow }},\downarrow ,\underset{m}{\underbrace{\uparrow ,\mathrm{\dots },\uparrow }})$, if $n$ is odd, say $n=2m+1$.

Proof.

Suppose first that $n=2m$, $i\le m$, and $g(x)=f(a_1,\mathrm{\dots },a_{i-1},x,\mathrm{\dots },a_{m+1},\mathrm{\dots },a_{2m})$ is antitone. Then $g(g(x))$ is isotone. By the associativity of $f$, $g(g(x))$ is

$f(a_1,\mathrm{\dots },a_{i-1},f(a_1,\mathrm{\dots },a_{i-1},x,a_{i+1},\mathrm{\dots },a_m,\mathrm{\dots },a_{2m}),\mathrm{\dots },a_{m+1},\mathrm{\dots },a_{2m})$

$=$ $f(a_1,\mathrm{\dots },a_{i-1},a_1,\mathrm{\dots },a_{i-1},x,a_{i+1},\mathrm{\dots },f(a_{2m-i+1},\mathrm{\dots },a_{2m},a_{i+1},\mathrm{\dots },a_{m+1},\mathrm{\dots },a_{2m})).$

In the second expression, the position of $x$ is , therefore implying that $g(g(x))$ is antitone, which is a contradiction! Therefore, $g(x)$ is isotone. Now, if $i>m$, and $h(x)=f(b_1,\mathrm{\dots },b_m,\mathrm{\dots },b_{i-1},x,b_{i+1},\mathrm{\dots },b_{2m})$ is antitone, then $h(h(x))$ is isotone. But

$f(b_1,\mathrm{\dots },b_m,\mathrm{\dots },b_{i-1},f(b_1,\mathrm{\dots },b_m,\mathrm{\dots },b_{i-1},x,b_{i+1},\mathrm{\dots },b_{2m}),b_{i+1},\mathrm{\dots },b_{2m})$

$=$ $f(f(b_1,\mathrm{\dots },b_m,\mathrm{\dots },b_{i-1},b_1,\mathrm{\dots },b_{2m-i+1}),\mathrm{\dots },b_{i-1},x,b_{i+1},\mathrm{\dots },b_{2m},b_{i+1},\mathrm{\dots },b_{2m})),$

and the position of $x$ is the second expression is $(i-1)-(2m-i+1)+2=2i-2m>1$, therefore implying that $h(h(x))$ is antitone, again a contradiction. As a result, $f$ is isotone for all $i=1,\mathrm{\dots },n$.

The argument above also works when $n$ is odd, say $n=2m+1$ and $i\ne m+1$. Finally, since $f$ is monotone, it is monotone with respect to the $i$-th variable when $i=m+1$, so $f$ is one of the following three forms:

$$(\underset{2m+1}{\underbrace{\uparrow ,\mathrm{\dots },\uparrow }}),(\underset{m}{\underbrace{\uparrow ,\mathrm{\dots },\uparrow }},\updownarrow ,\underset{m}{\underbrace{\uparrow ,\mathrm{\dots },\uparrow }}),(\underset{m}{\underbrace{\uparrow ,\mathrm{\dots },\uparrow }},\downarrow ,\underset{m}{\underbrace{\uparrow ,\mathrm{\dots },\uparrow }}),$$

the first two of which imply that $f$ is isotone. ∎

An example of an associative function that is, say $(\uparrow ,\downarrow ,\uparrow )$, is given by

$$f:{\mathbb{Z}}^3\to \mathbb{Z}\mathit{\hspace{1em}\hspace{1em}}\text{where}\mathit{\hspace{1em}\hspace{1em}}f(x,y,z)=x-y+z.$$

$f$ is associative since $f(f(r,s,t),u,v)=f(r,f(s,t,u),v)=f(r,s,f(t,u,v))=r-s+t-u+v$.

Title	properties of certain monotone functions
Canonical name	PropertiesOfCertainMonotoneFunctions
Date of creation	2013-03-22 19:03:31
Last modified on	2013-03-22 19:03:31
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	9
Author	CWoo (3771)
Entry type	Result
Classification	msc 06F99
Classification	msc 08C99
Classification	msc 08A99