Associative mean

Let $(L, <)$ be any linear order. Fix an arbitrary well-order $\sqsubset$ on $L$. For any $a\le b$ define $m(a,b)=m(b,a):= $ the $\sqsubset$-least element in the interval $[a,b]$.

Then $m$ is associative and commutative. (But rather uninteresting from the point of view of the relation $ < $.)

Notation: Write $\langle x,y\rangle:=\{ z: x\le z\le y \text{ or } y\le z \le x\}$.

Proof of associativity: Let $a,b,c$ be arbitrary, and let $d$ be the $\sqsubset$-least element in the interval $J:=[\min(a,b,c),\max(a,b,c)]$. I claim that $m(m(a,b),c)=d$. As $m$ is commutative, and $\min$ and $\max$ are commutative and associative, this also implies $m(a,m(b,c))=d$.

  • Case 1: $d\in \langle a,b\rangle$. Then $m(a,b)=d$ (as $\langle a,b\rangle \subseteq J$), and $m(m(a,b),c)=m(d,c)=d$, as also $\langle d,c\rangle \subseteq J$.
  • Case 2: $d\notin \langle a,b\rangle$. Wlog $a\le b$. We must have $c\notin [a,b]$, wlog $b< c$. So $d\in [b,c]$.
    Let $d':=m(a,b)$, then $d\sqsubset d'$, and $m(m(a,b),c) = m(d',c) = d$, as $d\in [b,c]\subseteq [d',c] = \langle d',c\rangle \subseteq J$.

QED.

(Edit:) It is also easy to see that $m$ is monotone. But in general not continuous.


Yes there are more such functions, even if we require them to be symmetric, monotonic and continuous. For example pick any $C$ and take

$m_C(a,b)=\min(a,b)$ if $a,b\ge C$,

$m_C(a,b)=\max(a,b)$ if $a,b\le C$,

$m_C(a,b)=C$ otherwise.

The following are easily verified: $m_{-\infty}=\min$, $m_{+\infty}=\max$, $m_A(m_B,m_C)=m_{m_A(B,C)}$, $f^{−1}(m_C(f(a),f(b)))=m_{f^{−1}(C)}(a,b)$ if $f:\mathbb{R}\rightarrow \mathbb{R}$ is invertible.

UPDATE.

Slightly Stronger Claim. If $m$ is monotonic, continuous and weakly associative (that is $m(a,m(a, b))=m(a,b)=m(m(a,b), b)$), then there are $U,L\in \mathbb{R}\cup \{\pm \infty\}$ such that $m=m_U$ if $a\le b$ and $m=m_L$ if $a\ge b$. Consequently $m$ is also fully associative. $m$ is symmetric iff $U=L$.

Lemma. Working in the upper-left half plane $a\le b$, pick $M\in \mathbb{R}$. Then either $(-\infty,M]\times \{M\}\subseteq m^{-1}(M)$ or $\{M\}\times [M,+\infty)\subseteq m^{-1}(M)$.

Proof.

Assume $(-\infty,M]\times \{M\}\nsubseteq m^{-1}(M)$. This implies $\exists x\lt M$ such that $m(x,M) < M$.

$m(x,M)\ne M \implies m(x,N)\ne M$ for $N>M$, otherwise weak associativity would imply $m(x,M)=m(x,m(x,N))=m(x,N)=M$.

$m(x,M) < M$, $m(x,N)\ne M$ and continuity $\implies m(x,N)\lt M$ for all $N>M$.

$m(x,N)\lt M$, $m(M,N)\ge M$ and continuity $\implies$ $\exists x_N \in (x,M]$ such that $m(x_N,N)=M$.

Weak associativity $\implies m(M,N)=m(m(x_N,N),N)=m(x_N,N)=M$ for all $N\gt M$.

This proves that $\{M\}\times [M,+\infty)\subseteq m^{-1}(M)$ $\square$

Proof of Claim. Again working in the upper-left half plane, define

$S=\{M\in \mathbb{R} \mid (-\infty,M]\times \{M\}\subseteq m^{-1}(M)\}$ and $T=\{M\in \mathbb{R} \mid \{M\}\times [M,+\infty)\subseteq m^{-1}(M)\}$.

By the lemma $S\cup T=\mathbb{R}$. Also $x\in S$ and $y\in T$ $\implies x\le y$ because otherwise $m^{-1}(x)\cap m^{-1}(y)\ne \emptyset$. All this implies that one of these 3 cases holds:

1) $S=\mathbb{R}$ and $T=\emptyset$,

2) $S=\emptyset$ and $T=\mathbb{R}$,

3) $\exists ! U\in \mathbb{R}$ such that $S=(-\infty,U]$ and $T= [U,+\infty)$, with $U$ contained in both sets by continuity. In this case monotonicity (only used here!) forces $m^{-1}(U)=(-\infty,U]\times [U,+\infty)$.

Clearly the 3 cases correspond to $m=m_{+\infty}$, $m=m_{-\infty}$ and $m=m_U$.

Similarly one can prove that $m=m_L$ in the lower-right half plane $a\ge b$. It's then a tedious but trivial exercise to show that $m$ is fully associative (and continuous, monotonic) for all pairs $U,L$ $\square$

graph

Graph of $m$ for some $U<L$.

LAST. Two interesting fully associative counterexamples:

$m(a,b)=\min(\text{sign}(a),\text{sign}(b))\times \min(|a|,|b|)$ is continuous non-monotonic!

$m(a,b)=\min(a,b)$ if $a+b<0$, $m(a,b)=\max(a,b)$ if $a+b\ge 0$ is monotonic discontinuous.


Let us, indeed, describe "monotone, continuous, associative means" on $[0,1]^2$. I'll just write $a*b$ instead of $m(a,b)$ to make long expressions easier to comprehend. Let $c=0*1,d=1*0$. Then, for every $x\le c\le y$, we have $c\le c*y=(0*1)*y=0*(1*y)\le 0*y\le 0*1=c$ and, thereby, $c=0*y\le x*y\le c*y=c$, i.e., $x\le c\le y$ implies $x*y=c$. Let now $a$ be any number with $q=0*a<a$. Repeating the same argument on $[0,a]$ instead of $[0,1]$, we see that for every $x\le q\le y$, we have $x*y=q$. Thus the function $y\mapsto 0*y$ is identically $q$ on $(q,a)$. If we have $a'>a$ such that $q'=0*a'>q$ at all, then, by continuity we can find such $a'$ with $q'<a$. But then $0*y$ should be simultaneously $q$ and $q'$ on $(q',a)$, which is impossible. Thus, if $q=0*a<a$, then $q=0*a'$ for all $a'\ge a$, i.e., $y\mapsto 0*y=y$ up to a certain point $y_0$ and then constant $y_0$, i.e., $0*y=\min(y,y_0)$. But then this constant must be $0*1=c$. Similarly we can conclude that $x*1=\max(x,c)$. Thus, if $x\le y$, then $$ x\le x*y\le x*1=\max(x,c), \min(y,c)= 0*y\le x*y\le y $$ But for $x\le y$ on one side of $c$ one of these double inequalities is a tight squeeze, so if $x\le y\le c$, then $x*y=y$, if $c\le x\le y$, then $x*y=x$, and we have already seen that if $x\le c\le y$, then $x*y=c$. Thus we have the full description of $x*y$ for $x\le y$. The case $x\ge y$ is treated in the same way using $d$.