A Couple of Binary Operators is All You Need

Recently I came across this thread by Laine Taffin Altman (@pthariensflame@treehouse.systems) on Mastodon. It's an interesting exercise in abstract algebra, which begins by defining a class of algebraic structures consisting of a set equipped with a ternary operator (following certain axioms, of course). If you have even a passing interest in abstract algebra I recommend following along with it. Spoiler alert: the structure described turns out to be another way of defining a ring, where the ternary operator a ⟪ b ⟫ c is equivalent to (a • c) + b.

This got me wondering: when can a ternary operator be broken down into a pair of binary operators? It turns out that the size of the set being operated on plays an important role. This article contains a terse version of the proof intended for those familiar with math jargon. The next article will be a simpler explanation for non-mathematicians.

The Proof

Let S be a set, and let f: S×S×S → S be a function on three variables such that S is closed under f. We'd like to find some functions g, h: S×S → S such that f(x, y, z) = g(h(x, y), z) for all x, y, z in S. Because S is closed under f, it must also be closed under g and h.

Case 1

Assume that there exists some injective function from S×S to S. Define h to be that function. Because h is an injection, it must have a left-inverse h⁻¹: S → S×S; intuitively, when no two inputs map to the same output, the image preserves all the information contained in its preimage. Define g(w, z) = f(h⁻¹(w), z) (where (h⁻¹(w), z) represents the triple whose first two components are those of h⁻¹(w) and whose third component is z). g(h(x, y), z) = f(h⁻¹(h(x, y)), z) = f(x, y, z).

Such an injection (and thus some suitable functions h and g) exists if S has a single element, or if S is infinite and well-orderable. In particular, such injections exist for any set that admits a bijection to either the naturals or the reals. If we take the axiom of choice, such injections exist for all infinite sets.

Case 2

Assume that S is finite and contains n elements. There are n^2 distinct ordered pairs of the form S×S; thus n^(n^2) distinct functions from S×S to S; thus n^(2•n^2) ways of choosing g and h. There are likewise n^(n^3) distinct functions from S×S×S to S that we can choose as our f. If n > 2, then the number of ways of choosing f is greater than the number of ways of choosing g, h, so by the reverse pigeonhole principle there must be at least one f that can't be expressed as g(h(x, y), z).

Case 3

The final case is when S has two elements. Consider the case when g(w, z) = z, that is, our function g throws away its first operand and gives us the second. No matter which of the 16 options we choose for h, the composed function g(h(x, y), z) will be the same. Out of the 256 ways of choosing g, h, there are therefore at most 241 distinct composed functions we can get, which is less than the 256 distinct choices of f. Again, by the reverse pigeonhole principle there must be at least one f that can't be expressed as g(h(x, y), z).

Q.E.D.

If S is finite and contains 2 or more elements, there exists some f(x, y, z) which can't be expressed as g(h(x, y), z). If there exists an injection S×S → S then such an f does not exist; this is the case for all infinite sets under the axiom of choice.

An Extension

The same argument can be made for algebraic structures with n-ary operators for any n > 2. As long as we have our injection h, we can nest it arbitrarily many times (h(x₁,x₂), h(h(x₁,x₂),x₃), h(h(h(x₁,x₂),x₃),x₄), ...) to get injections from Sⁿ⁻¹ to S, and g can then 'unpack' that information to get the original n-1-tuple that was input to the nested hs. Note that with the injection, two binary operators are enough to describe an operator with any number of operands!

I'm sure I'm not the first to have made this observation, but I think it provides a decent motivation for why abstract algebra tends to focus primarily on sets equipped with a couple of binary operators. As it turns out, a couple of binary operators is all you really need.