Binary operations compatible with the usual order on the reals

Question

An officemate passes along the following natural-seeming question:

Say that a binary operation $\oplus$ is compatible with the usual order $\leq$ on $\mathbb{R}$ if for any $w, x, y, z$ in $\mathbb{R}$ we have $w \leq x$ and $y \leq z$ implies $w \oplus y \leq x \oplus z$. For example, $+$, $\max$ and $\min$ are compatible with $\leq$, as is $\times$ if we restrict to the positive reals. More generally, any operation of the form $a \oplus b = f(g(a) + h(b))$ is compatible with $\leq$ whenever $f$, $g$ and $h$ are increasing functions. (Well, "more generally" is a little bit of a lie, since max and min are actually limits of such expressions.)

Are there any other examples of such binary operations?

(Application of appropriate tags would be appreciated.)

Answer 1

A pretty big supply of such operations is obtained by defining $x\oplus y=\int_0^{e^x}\int_0^{e^y}f(s,t)dsdt$ for an arbitrary non-negative measurable function $f$. I haven't checked, but it seems very unlikely that all such functions would decompose in the way you talk about. (If you want the operation to be commutative, then make $f$ symmetric.)

Answer 2

This is just to translate what Gerhard wrote to "visual language". Assume that your operation is a smooth function with positive derivative in each variable (anything like that will work). Now, the level curves are just any disjoint smooth lines going from top left to bottom right on the plane. The outer $f$ can do nothing with them. Thus, the question really is if every such family $L_j$ of lines (say, discrete, to avoid the discussion of how they may come close to each other) can be realized as level sets of $f(a)+g(b)$. If you fix $a$ and decide what the level of $L_j$ is $T_j$, then you'll know that at the points $x_j(a)$ where $(a,x_j(a))\in L_j$, one should have $h(x_j(a))+g(a)=T_j$. Now, the points $x_j(a)$ run to the left as $a$ goes up and the way they do it is restricted only by the order-preservation property. Thus, the question is whether it is possible for the runners $x_j(a)$ on a track that cannot pass each other to find an increasing $h(x)$ that depends only on the position $x$ on the track such that all $h(x_{j+1}(a))-h(x_j(a))$ stay constant. Now put two checkpoints on the track anywhere and tell the runners to run in such a way that when $x_j$ is at one checkpoint, $x_{j+1}$ is at the other, but otherwise they can go as they wish (Canada boundary crossing would be like that if the bridge toll collection gates cooperated with the customs). Then we see that all constants must be the same. But now the runners $1$ and $2$ can choose to pass the interval $[0,1]$ so that they are on different sides of it at some moment, and runners $3,4,5$ may choose to almost meet inside that interval (that is, if it is free of the gates, of course). That shows that the common difference is at least $h(1)-h(0)$ and at most half of it simultaneously whence $h$ is constant, which is impossible because then $g(a)$ takes many values at once.

I tried to present it the way I saw it. I hope, to translate into the formal language won't be a problem. :)

Answer 3

R with the standard (total) order and the functions min and max corresponding to that order form a lattice (in the sense of universal algebra). Also, given the functions min and max, the order on R can be recovered. The square RxR of this algebra gives another lattice whose associated (partial) order is your $R^2$. You can generalize the construction above: if f,g, and h are increasing functions on certain ranges, and B is a binary function which preserves the order on the right part of RxR, then so will f(B(g(a),h(b)) preserve the order. (Essentially f has to capture the range of B, which has to capture the range of g and h in a certain way.) So you can replace + by min and other order-preserving operations.

I do not know, but I do believe, that the above construction does not capture all operations if you limit B to range over a finite set of binary operations. I am confident, however, that a practicing order theorist or universal algebraist can give you a better, if not decisive, answer. If you want to do some more research, consider clone theory and sets of operations which preserve a given relation.

To the contrary, there is also a memory of a result of Kolmogorov which is something like every continuous function over R in some number (three) of variables can be rewritten using just addition and functions of one variable. There may be other conditions on this result which relate to your question.

(To partially counter Mark Sapir's opinion, I offer a result of Kolmogorov and Arnold. Forgive the lack of accents. Every continuous function (on the reals) in three variables can be written as a sum of 6 unary functions, each of which has as arguments a sum of three other unary functions, one for each of the three variables. This suggests that any continuous order preserving function of two variables can be written with a term composed of at most 17 addition operations and at most 24 unary functions. One can probably do better (e.g. representing t(x,y,0) in this form and incorporating the constants into some of the unary functions, one brings the count down to 11 additions and 18 unary functions), but at least it suggests that many order-preserving binary functions are not too far removed from addition. If it can be shown that every binary order-preserving functions is of the form f(B(-,-)), where B is continuous and order preserving, then you will have all such operations generated by addition and unary functions, contrary to my belief above that you need infinitely many such binary operations.)

Gerhard "Ask Me About System Design" Paseman, 2010.12.15

Answer 4

Rather than simply give a counterexample, I will try to explain a rationale for an emphatic "no."

So consider an operation $a\oplus b = f(g(a)+h(b))$ of your form. Now viewed as function of two variables, $a\oplus b$ will have its various level sets. Observe that changing, say, one strictly increasing $f$ for another does not change the set of level sets (one needs to say something a bit more complicated for weakly increasing $f$).

Thus, from the point of view of the geometry of the level sets, we don't lose much by taking $f={\rm id}$, the identity function. But the level sets of $g(a)+h(b)$ have very special structure: roughly from three of them you can calculate a fourth (I don't need continuity, but for simplicity I'll tacitly assume "nice" in whatever way I need) as follows:

Suppose $L \lt M,N$. I'll use the $L$,$M$ and $N$-level sets to locate points on the $M+N-L$-level set. Given $(a,b)$ such that $g(a)+h(b)=L$, find b' so that $g(a)+h(b')=M$ and a' such that $g(a')+h(b)=N$. Then $(a',b')$ sits on the desired level set. Now one can easily engineer binary operations compatible with the usual order that don't have level sets that behave this way. Indeed one may interpret the desired condition on the operation as a rather weak condition on the geometry of the level sets themselves, namely that given a point on a level set, the level set does not pass into the quadrant to the right and above the point.

Answer 5

Consider an operation on the positive quadrant such that $a \oplus b=ab$ on and above the positive branch of $ab=1$ but $1 \oplus \frac{1}{4}\ne\frac{1}{2} \oplus \frac{1}{2}$. Then one can find increasing functions $f,g$ with $a \oplus b=f(g(a)+g(b))$ (say $\exp(\ln{a}+\ln{b})$) on and above the positive branch of $ab=1$ but this will force $g(1)+g(\frac{1}{4})=2g(1/2)$. (It seems easy that there is such an operation and that we can assume $g=h$).

Proof: $f$ and $g$ will have to be strictly increasing. From $g(1)+g(4)=2g(2),g(\frac{1}{2})+g(4)=g(1)+g(2),g(\frac{1}{4})+g(4)=2g(1)$ and $g(\frac{1}{2})+g(2)=2g(1)$ it follows that $g(\frac{1}{4})=3g(1)-2g(2)$ and $g(\frac{1}{2})=2g(1)-g(2)$.