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

Question

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.

Answer 1

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\,.$

Answer 2

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.

Answer 3

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)$$

Answer 4

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.