Are there any functions that can't be expressed in terms of binary operations?

Solution 1:

Let $X$ be any infinite set and $f:X^n\to X$ be an $n$-ary operation for some $n>2$. Let $g:X\times X\to X$ be any bijection, and let $h:X^{n-1}\to X$ be given by $h(x_1,x_2,\dots,x_{n-1})=f(y_0,y_1,x_2,\dots,x_{n-1})$ where $y_0,y_1\in X$ are the unique elements such that $g(y_0,y_1)=x_1$. We then have $$f(x_0,x_1,\dots,x_{n-1})=h(g(x_0,x_1),x_2,\dots,x_{n-1}).$$ That is, $f$ is a composition of one binary operation and one $(n-1)$-ary operation. By induction on $n$, this shows that any $n$-ary operation on $X$ can be written as a composition of $n-1$ binary operations (and in fact, all but the last of these binary operations can be chosen to be some fixed bijection $X\times X\to X$).

Note that clearly you can't use fewer than $n-1$ binary operations, since in any expression formed by composing $k$ binary operations, you have only $k+1$ different inputs. So if you had fewer than $n-1$ operations, one of the variables would need to not appear as an input at all, and so the $n$-ary operation could not depend on that variable.

If you impose additional restrictions on what kinds of operations you're allowed to use, this question can become much more subtle, and is generally known as (variations on) Hilbert's thirteenth problem. For instance, in the case $X=\mathbb{R}$, if you require all the operations to be continuous, then it is a theorem of Arnold and Kolmogorov that every operation can be written as a composition of binary operations (or in fact, a composition of addition and unary operations). If you require the operations to be smooth instead, then for every $n$ there are $n$-ary operations on $\mathbb{R}$ which are not compositions of operations of lower arity (see https://mathoverflow.net/questions/195380/are-all-smooth-functions-composites-of-0-1-and-2-ary-functions).