3

Is $f(x,y)=\max(x,y)$ with $x,y\in\mathbb{Z}$ the only binary operation on the set of integers that satisfies following properties?

  • $f(x,f(y,z))=f(f(x,y),z)$ (associativity)
  • $f(x,y)=f(y,x)$ (commutativity)
  • $f(x,x)=x$ (idempotency)
  • $f(x,y)\geq x$

If not, which other properties are needed to get the max function as the only solution?

otmar
  • 344

1 Answers1

2

The function

$$f(x,y) = \begin{cases} 2 & \{x, y\} = \{0, 1\} \\ \max(x,y) & \text{otherwise} \end{cases}$$

satisfies all 4 properties. The only one that is not immediate is associativity, which can be checked case by case. Any counterexample must involve the first case of the definition of $f$, so either (1) $\{y, z\} = \{0, 1\}$, or (2) $\{x, y\} = \{0, 1\}$, or (3) $x=0, f(y,z) = 1$, or (4) $x=1, f(y,z)=0$, or (5) $f(x,y)=0, z=1$, or (6) $f(x,y)=1, z=0$.

In (1), say $y=0, z=1$. Then the LHS is $f(x, 2)=\max(x,2)$ and the RHS is $f((f(x, 0), 1)$. If $x=1$ this is $f(2, 1)= 2 = \max(x, 2)$. If $x > 1$ this is $f(x, 1) = \max(x, 1) = \max(x, 2)$. If $x < 1$ this is $f(0, 1) = 2 = \max(x, 2)$. The case $y=1, z=0$ is similar.

In (3), the LHS is 2 and we have $\max(y, z)= 1$. If $y=1, z \leq 1$ the RHS is $f(f(0, 1), z) = f(2, z) = \max(2, z) = 2$. If $y\leq 1, z = 1$ then the RHS is $f(f(0, y), 1)$. If $y<1$ then this is $f(0, 1)=2$. If $y=1$ this is $f(2, 1) = 2$.

In (4), the LHS is $f(1, 0) = 2$ and we have $\max(y,z)=0$. If $y=0, z\leq 0$ then the RHS is $f(f(1, 0), z) = f(2, z) = 2$. If $y\leq 0, z=0$ then the RHS is $f(f(1, y), 0)$. If $y=0$ then this is $f(2, 0)=2$, and if $y<0$ then this is $f(1, 0) = 2$.

Other cases are similar.

Matthew Towers
  • 10,854