Ternary operation. Does it exist?

Question

Everybody knows unitary operations. They are obviously exist. For example, an operation of factorial (n!). Everybody also knows binary operations: summation, multiplication, exponent, etc. We could imagine a ternary operation. It could be some function that takes three numbers and results with another number: the sum of three numbers, or the sum of the first number with the second number raised to the power of third... But all ternary operations I am able to imagine can be represented as the composition of binary ones. So I found myself thinking about existing of a ternary operation that cannot be represented as a composition of binaries. Unfortunately I haven't found any so far. Does anybody know anything about such odd things?

Answer 1

If $X$ is an infinite set and $f:X\times X\times X\to X$ is any ternary operation on $X$, we can always find $g, h:X\times X\to X$ such that $$ f(x,y,z) = g(x,h(y,z)) $$ The slick proof of this uses the axiom of choice to construct $h$ such that it is a bijection $X\times X\to X$, and then the above equation can serve as a definition of $g$ if we read it right to left.

---

It is not quite as nice when $X$ is finite. For example if $X=\{0,1\}$, then the majority function (whose out is the one of $0$ or $1$ that appears two or three times among the inputs) cannot be represented in this way.

But if we allow duplication of the inputs, we can always represent it in the form $$ f(x,y,z) = k_1(g_1(x,h_1(y,z)), k_2(\cdots, k_{n-1}(g_{n-1}(x,h_{n-1}(y,z)), g_n(x,h_n(y,z)))\cdots))$$ for some finite $n$ and appropriate binary functions $k_i$, $g_i$, $h_i$.

(Namely, each pair of $g_i$ and $h_i$ can encode at least one line in a tabulation of $f$, and the $k$s can discard the results of the $g_i,h_i$ combos that don't "fire". In fact all of the $k_i$s can be chosen to be equal).

---

We can also do with fewer different binary functions at the cost of more complex expressions: For $X=\{0,1,\ldots,m-1\}$, define $$ x\mathop\downarrow y = \begin{cases} x-1 & \text{if }x=y\ne 0 \\ m-1 & \text{if }x=y=0 \\ 0 & \text{otherwise} \end{cases} $$ Then any function whatsoever $f(x_1,x_2,\ldots, x_n)$ from $X^n$ to $X$ can be represented as an expression built only from binary $\downarrow$s and the variables $x_1$ through $x_n$.

(In the case $m=2$, $\downarrow$ becomes the Boolean NOR operator).