Equivalent algebraic theory with at most binary operations

Question

Given an arbitrary (one-sorted) algebraic/equational theory $\mathbb{T}$, is it possible to devise an equivalent (one-sorted) algebraic theory $\mathbb{S}$ such that the signature of $\mathbb{S}$ contains function symbols of at most arity two? By 'equivalent', I mean that they have equivalent categories of set-based models.

Answer 1

As we talked about in the comments this doesn't quite answer the original question, because I use a stronger version of equivalence, equivalent over $\mathbf{Set}$, which says that there is an equivalence that commutes with the forgetful functors to $\mathbf{Set}$. I then show that there is a ternary theory $\mathbb{T}$ which is not equivalent over $\mathbf{Set}$ to any binary theory $\mathbb{S}$.

Write $U$ for the forgetful functor from $\mathbb{T}$-algebras to $\mathbf{Set}$. If $X$ is a set, then the free $\mathbb{T}$-algebra on $X$ is a $\mathbb{T}$-algebra $A$ together with a map $\eta : X \to U A$ which is initial with this property. That is, for any $\mathbb{T}$-algebra $B$ and map $f : X \to UB$ there is a unique homomorphism $\theta : A \to B$ such that $f = U(\theta) \circ \eta$. Note that if $\mathbb{T}$-algebras and $\mathbb{S}$-algebras are equivalent over $\mathbf{Set}$ then there is a natural bijection between the corresponding free algebras.

Let $\mathbb{T}$ be the theory with a single ternary operator $m(x, y, z)$ together with the axioms

1. $m(x, x, y) = x$
2. $m(x, y, x) = x$
3. $m(y, x, x) = x$

I'll characterise the free algebras on the sets with $0$, $1$, $2$ and $3$ elements and show that they can't be the same for any binary theory.

First, the free algebra on $0$ is empty if and only if the theory has no constant symbols. So in this case it is empty.

The cases for $1$ and $2$ are similar, so I'll just show $2$. Note that the set $2$ already admits exactly one $\mathbb{T}$-algebra structure. If we are given three elements $x, y, z$ of $2$ then two of them must be the same by the pigeonhole principle. Say for example $z = x$. Then we are forced to take $m(x, y, z)$ to be $x$ by the axioms. If we take this as the definition of $m$, then it does satisfy the axioms, so we get an algebra structure. Now, if $B$ is a $\mathbb{T}$-algebra structure and $f : 2 \to U B$ is any function, note that $f$ has to be an algebra homomorphism. We need to show that for all $x, y, z$ in $2$, $f(m(x, y, z)) = m(f(x), f(y), f(z))$. Again by the pigeonhole principle, two have to be the same, and say for example $x = z$. Then $f(m(x, y, z)) = f(x)$ and $f(x) = f(z)$, so $m(f(x), f(y), f(z)) = f(x)$. It follows that in fact the algebra we gave on $2$ is the free algebra on $2$.

For $3$, we don't need to know exactly what the free algebra looks like, but only that unlike $2$ and $1$, it is not just the set with $3$ elements. We use the lemma below:

Lemma Suppose $X$ is a set with $n$ elements. Suppose that the underlying set of the free algebra $A$ also has $n$ elements and $\eta : X \to U A$ is a bijection. Then for any $n$-ary operator symbol $f(z_1, \ldots, z_n)$ there is some $k$ such that for any algebra $B$, and any $b_1,\ldots,b_n$ in $B$, $f(b_1,\ldots,b_n) = b_k$.

Proof By transferring the algebra structure on $U A$ to $X$ via the bijection, we may assume without loss of generality that $U A = X$ and $\eta$ is the identity on $X$. Write the elements of $X$ as $x_1,\ldots,x_n$. Then for some $k$ we have $f(x_1,\ldots,x_n) = x_k$ (because $f(x_1,\ldots,x_n)$ can only be an element of $X$). Now given any algebra $B$ and $b_1,\ldots,b_n$, we have a function $g : X \to B$ sending $x_i$ to $b_i$. This function extends to a homomorphism on the free algebra on $X$. But since the free algebra is $X$ itself and $\eta$ is the identity, this says that $f$ must already be a homomorphism itself. Hence $f(b_1,\ldots,b_n) = f(g(x_1),\ldots,g(x_n)) = g(f(x_1,\ldots,x_n)) = g(x_k) = b_k$.

We can now deduce that the free $\mathbb{T}$ algebra on $3$ is not just $3$ itself. Because e.g. there are three different algebra structures on $3=\{0, 1, 2\}$, where we can take $m(0,1,2)$ to be either $0$, $1$ or $2$.

Now let $\mathbb{S}$ be a binary theory with the same free algebras as $\mathbb{T}$. Since the free algebra on the empty set is empty, we know $\mathbb{S}$ has no constant symbols. We know that the free algebras on $1$ and $2$ are just algebra structures on $1$ and $2$ themselves respectively, and $\eta$ is an isomorphism. Hence by the lemma, for any unary operator $u(x)$ we have $u(x) = x$ in any model, and for any binary operator $f(x, y)$ we either have $f(x, y) = x$ in every model or $f(x, y) = y$ in every model. In either case we have at most one way to assign each unary symbol and each binary symbol on any set, and they are preserved by any function. Since $\mathbb{S}$ is binary, there aren't any more operator symbols, and so for any set there is at most one way to assign an $\mathbb{S}$-algebra structure and any function preserves the structure. But this contradicts for example the non triviality of the free algebra on $3$, and so there can be no such theory $\mathbb{S}$.