Are all n-ary operators simply compositions of binary operators?

Take for example $A \times B \cdot C$ = $(A \times B) \cdot C$ where $A, B, C$ are 3-component real vectors.

We can define a 3-nary operator $\times - \cdot$ that is a composition of the two common binary operators $\times$ and $\cdot$.

The same thing happens with most functions (operators) - the way we calculate them is by doing smaller binary problems and adding together.

Every time I try to come up with an $(n > 2)$-ary operator my mind automatically looks for binary operators.

So, the question is, do there exist operators (of some weird kind in some branch of math) that cannot be decomposed into 2-ary and 1-ary operators?

Thanks.

• The answers given seem to assume only a single composition of binary operators, but I believe Dan wants operators that cannot be decomposed into (chained) compositions of binary operators. I believe the answer is that all operators are such compositions. If the domain X has 2 elements, this is the claim that NAND (or NOR) is a universal gate. Mar 5, 2012 at 19:00

Yes, during the 1930's and 1940's Sierpinski researched compositions of operations ("clones") and proved that every $$n$$-ary operation on a set is a finite composition of binary operations on the set, see W. Sierpinski, Sur les fonctions de plusieurs variables, Fund. Math. 33 (1945), 169-173. See also see Jerzy Los's paper, excerpted below. A proof is also in Paul Cohn's Universal Algebra. For some recent work on related topics see Gratzer, A Survey of some Open Problems on $$p_n$$-Sequences and Free Spectra of Algebras and varieties.

A proof is especially simple for operations on a finite set $$\rm A.\,$$ Namely, if $$\rm\,|A| = n\,$$ then we may encode $$\rm A$$ by $$\rm\,\mathbb Z/n,\,$$ the ring of integers $$\!\rm \bmod n,\,$$ allowing us to employ Lagrange interpolation to represent any finitary operation as a finite composition of the binary operations $$\rm\, +,\ *\,,\,$$ and Kronecker delat $$\rm\, \delta(a,b) := 1\,\ if\,\ a=b\,\ else\,\ 0,\,$$ namely

$$\rm f(x_1,\ldots,x_n)\ =\!\!\!\!\!\!\! \sum_{(a_1,\ldots,a_n)\ \in\ A^n\!\!\!\!\!}\!\!\!\!\! f(a_1,\ldots,a_n) \prod_{i\ =\ 1}^n\ \delta(x_i,a_i)\qquad$$

When $$\rm\,|A|\,$$ is infinite one may instead proceed by employing pairing functions $$\rm\,A^2\to A\,.$$

Here is another point of view, which I learned from Richard Garner.

Suppose we have an algebraic theory $\mathbb{T}$ – so a fixed set of finitary operations and a set of equations that these satisfy. Let $\mathbb{T}\textbf{-Alg}$ be the category of all $\mathbb{T}$-algebras and their homomorphisms. We define a natural $n$-ary operation to be a family of functions $\theta_X : X^n \to X$, indexed by $\mathbb{T}$-algebras $X$, such that for all homomorphisms $f : X \to Y$, the operation $\theta$ commutes with $f$, in the sense that $$\theta \circ (f \times \cdots \times f) = f \circ \theta$$ where $f \times \cdots \times f : X^n \to Y^n$ is the function that applies $f$ to each component separately.

Now, it is a fact that any algebraic theory $\mathbb{T}$ admits a notion of ‘free $\mathbb{T}$-algebra on a set of generators’. Formally, this is defined as the functor $F : \textbf{Set} \to \mathbb{T}\textbf{-Alg}$ which is left adjoint to the forgetful functor $U : \mathbb{T}\textbf{-Alg} \to \textbf{Set}$; in simpler terms, the free $\mathbb{T}$-algebra on a set $S$ is the $\mathbb{T}$-algebra $F S$ together with a function $\eta_S : S \to F S$, called the ‘insertion of generators’, such that for all functions $f : S \to X$, where $X$ is a $\mathbb{T}$-algebra, there is a unique $\mathbb{T}$-algebra homomorphism $h : F S \to X$ such that $h \circ \eta_S = f$. In this general language, your question can be interpreted as follows: is every natural $n$-ary operation a composite of operations defined in $\mathbb{T}$?

It turns out the answer is yes! By some simple abstract nonsense involving the Yoneda lemma, it can be shown that there is a canonical bijection between the set of natural $n$-ary operations and the set of elements of $F \{ e_1, \ldots, e_n \}$. This means that every natural $n$-ary operation corresponds to some string of symbols formed by $e_1, \ldots, e_n$ and the operations of the theory $\mathbb{T}$. But this precisely means that the $n$-ary operation $\theta_X : X^n \to X$ can be written as a composite of the operations of $\mathbb{T}$ together with the canonical projection operators $\pi_j : X^n \to X^m$. For example, if we take $\mathbb{T}$ to be the theory of groups, and $\theta_X (x_1, \ldots, x_n) = x_1 {x_2}^{-1} x_3 \cdots {x_n}^{(-1)^n}$, then the operation $\theta$ corresponds to the word $e_1 {e_2}^{-1} e_3 \cdots {e_n}^{(-1)^n}$ in the free group generated by $\{ e_1, \ldots, e_n \}$, and this is clearly a composition of the group multiplication and the inversion.

Of course, there are algebraic theories $\mathbb{T}$ where there are no constants, unary or binary operations whatsoever. For instance, $\mathbb{T}$ could be the theory of heaps, which has a single ternary operation. In this context it makes no sense to ask whether that ternary operation can be rewritten as a binary operation of $\mathbb{T}$, because there simply aren't any binary operations in $\mathbb{T}$ at all. But it turns out that when we augment $\mathbb{T}$ with one constant (and no axioms!), $\mathbb{T}$ becomes the theory of groups, and we know that the theory of groups is can be presented using one constant, one unary operation, and one binary operation. So one might ask: does every algebraic theory $\mathbb{T}$ admit a presentation using only operations of arity at most $2$? Unfortunately, I do not know the answer to this.

• Nitpick: you can always construct a binary operator from a ternary one, e.g. $b(x,y) := t(x,x,y)$
– user14972
Mar 5, 2012 at 20:35
• Yes, that's obvious. But it's not obvious that you can recover a ternary operator from the set of binary operators derivable from it. Mar 5, 2012 at 20:46

There are two trivial senses in which the answer is "yes", you can always reduce it to binary functions.

One of them is the pairing operator -- the function that takes any two objects and returns the ordered pair containing them. So, for example, given any function $f$ of four variables, we can construct a new function $g$ (of 1 variable of type "ordered pair of ordered pairs of objects") by $$g( ((a,b), (c, d)) ) = f(a, b, c, d)$$

It might be instructive to see this restated in terms of an ordered-pair variable. If $x$ is an ordered pair, then the function $L(x)$ is the left coordinate, and $R(x)$ is the right coordinate. Then, $g$ is defined by $$g(x) = f(L(L(x)), R(L(x)), L(R(x)), R(R(x))$$

(with a lot of pain, one could write this explicitly as composition of functions, but it is painful. We use the above notations for a reason!)

Dually, there is the transpose operator. Again, if $f$ is a function of four variables, then I can define a new function $h$ that is a function of one variable, whose values are themselves functions of 3 variables, by $$h(a)(b, c, d) = f(a, b, c, d)$$

($h(a)$ is a function, so it makes sense to evaluate it, as above. The above defines $h(a)$ pointwise, and thus $h$ pointwise)

This can be iterated: you can have a function of one variable whose values are of type "Function of one variable whose values are of type {Function of two variables}", defined by: $$k(a)(b)(c,d) = f(a, b, c, d)$$

• It would be nice if all the functions were from XxX to X, rather than XxX to Y. Mar 5, 2012 at 19:01
• I like the second part of your answer involving a function that maps to a function. That seems to prove it for me. Mar 5, 2012 at 19:13
• @Jack: I agree. However, the algebra of functions is a nice thing to see explicitly. And I didn't feel the need to be so restrictive anyways, since his example was the triple product. (and I couldn't remember any theorems regarding operators from a set to itself anyways)
– user14972
Mar 5, 2012 at 20:39
• @Hurkyl Is the transpose operator related to the concept of currying? And even more abstractly, is there a relationship to the concepts of representable functors and adjunction in category theory? I should probably ask this as a separate question, although a yes/no answer would suffice for me for now. Aug 19, 2016 at 21:42
• @William: Yes, transpose means the same thing as currying/uncurrying here. I picked up the phrase "exponential transpose" from Sheaves in Geometry and Logic to mean going back and forth between maps $A \to C^B$ and maps $A \times B \to C$. (actually, I'm not sure if it used transpose to mean just one direction, or both)
– user14972
Aug 19, 2016 at 23:55

A slightly different context provides a nice example. Let $X=\{0,1\}$ and let $\mu:X\times X\times X\to X$ be the function such that $\mu(x,y,z)$ is the element of $X$ which appears more times in the argument. This function $\mu$ cannot be written as a composition of binary operators.

• This is also a composition of several binary operations, image search for "majority circuit" to see some pictures of the composition. Mar 5, 2012 at 19:03
• This is $\mu(x,y,z) = O(O(A(x,y), A(x,z)), A(y, z))$ where $A(x,y) = xy$ and $O(x,y) = x+y-xy$. That is, taking $X = \mathrm{Bool}$, we write it as $((x\land y)\lor (x\land z))\lor (y\land z)$.
– MJD
Mar 28, 2019 at 16:34