How many associative binary operations are there on a 2 element set?

Question

We can easily find commutative binary operations on a 2 element set from the truth table (if ab=ba then the operation is commutative, thus there are 8 commutative binary operations in a 2 element set).

Is there a similar method or algorithm to find how many and what are the associative binary operations in a 2 element set?

If there isn't a way to quickly check, we would need to test all 8 possible inputs independently (if not commutative) and only 4 (if commutative) - which is still a lot for a 2 element set - 96 total (16 operations, 8 are commutative, so 8*4+8*8=96).

A generalization to an n-element set be very helpful.

Answer 1

You do not need to check every single possibility. For your set use $\{+1, -1\}$.

• Suppose $B$ is commutative, i.e. $B(a,b)=B(b,a)$ for all $a,b\in \{\pm1\}$, and associative . Then if we put $B(a,a)=x_a$ and $B(a,-a)=B(-a,a)=y$ (note the latter is independent of $a$). The triple $x_{\pm1},y$ is enough to completely determine $B$. The only non-trivial associativity equation in this case yields $$ \begin{aligned} B(x_y,-y)&=B(B(y,y), -y)=B(y,B(y,-y))=B(y,y)=x_y\\ B(x_{-y},y)&=B(B(-y,-y), y)=B(-y,B(-y,y))=B(-y,y)=y \end{aligned} $$ The possible solutions are (1) $x_y=-x_{-y}=y$, (2) $x_y=x_{-y}=y$, (3) $x_y=x_{-y}=-y$. And these are the only possibilities. So programatically, if $B(1,-1)=B(-1,1)$, simply calculate $x_{+1}, x_{-1}, y$ and check if $x_y=y$ (case 1 and 2 together), or else if $x_y=x_{-y}$.

• Suppose $B$ is NOT commutative but associative. Then $B(a,-a)=-B(-a,a)$. Define $x_a=B(a,a)$ and $y=B(1,-1)$. Now associativity gives $$ B(x_a,a)=B(B(a,a),a)=B(a,B(a,a))=B(a,x_a) $$ meaning $a,x_a$ commute. This in turn means, $x_a=a$ necessarily.

Before we continue, note that the equalities $$ \begin{aligned} y&=B(1,y)=-B(-1,-y)=B(y,-1)=-B(-y,1)\\ 1&=B(y,1)=B(1,-y)=-B(-y,-1)=-B(-1,y) \end{aligned} $$ are tautologically true no matter what $y$ is. Writting the most general associativity equality $$ B(B(a,b),c)=B(a, B(b,c)) $$ assuming not all $a,b,c$ are the same, we have the following possibilities, $a=b=-c$, $a=-b=c$ and $-a=b=c$. This leads to three associativity relation $$ \begin{aligned} &(\mathrm{sgn}\: a)y=B(a,-a)=B(B(a,a),-a)=B(a, B(a,-a))=B(a,(\mathrm{sgn}\: a)y)\\ &B((\mathrm{sgn}\: a)y,a)=B(B(a,-a),a)=B(a, B(-a,a))=B(a, -(\mathrm{sgn}\: a)y)\\ &B(-(\mathrm{sgn}\: a)y,a)=B(B(-a,a),a)=B(-a,B(a,a))=B(-a,a)=-(\mathrm{sgn}\: a)y \end{aligned} $$ all of which are tautologically true. This means we are completely free to choose $y$ as we please. So programatically, if $y=B(1,-1)\neq B(-1,1)$, then simply check if $B(1,1)=1$ and $B(-1,-1)$, because that's the only possibility.

Assuming I have not done any stupid mistakes (which I'm quite afraid might have happened), you should be able to rule whether a binary relation $B$ is associative or not with like four if-clauses. I'm too lazy to actually count how many binary relations I just created, but it's quite straightforward to do that now.

Answer 2

The comments show what there might be for the $n$-element set. As for the $2$-element set, we can enumerate all possible binary operations (realizing that Hamed's answer shows we don't necessarily have to do this), and then check which ones are associative. Assume we are writing $a\star b = f(a,b),$ where $\star$ is the binary operation and $f$ we will designate as a number from $1$ to $16,$ and we're going to use the $2$-element set $\{T, F\},$ so that we can pull in expressions from boolean logic. So we create the following tables: $$ \begin{array}{|cc|cccccccc|}\hline a &b &1 &2 &3 &4 &5 &6 &7 &8 \\ \hline T &T &F &F &F &F &F &F &F &F\\ \hline T &F &F &F &F &F &T &T &T &T \\ \hline F &T &F &F &T &T &F &F &T &T \\ \hline F &F &F &T &F &T &F &T &F &T \\ \hline \text{Expr:} & &F &\lnot(a\lor b) & &\lnot\,a & &\lnot\,b &a\otimes b &\lnot (a\land b) \\ \hline \text{Assoc.?} & &T &F &F &F &F &F &T &F\\ \hline \end{array} $$ $$ \begin{array}{|cc|cccccccc|}\hline a &b &9 &10 &11 &12 &13 &14 &15 &16 \\ \hline T &T &T &T &T &T &T &T &T &T \\ \hline T &F &F &F &F &F &T &T &T &T \\ \hline F &T &F &F &T &T &F &F &T &T \\ \hline F &F &F &T &F &T &F &T &F &T \\ \hline \text{Expr:} & &a\land b &a \iff b &b &a\implies b &a &b\implies a &a\lor b &T \\ \hline \text{Assoc.?} & &T &T &T &F &T &F &T &T \\ \hline \end{array} $$

Here is some Python code used to test each option:

def f(a: bool, b: bool) -> bool:
    return a or b 

def test_assoc() -> bool:
    values = [True, False]
    associative = True
    for a in values:
        for b in values:
            for c in values:
                test = (f(f(a, b), c) == f(a, f(b, c)))
                associative = associative and test
    return associative

You just change the definition of f to match which function you're testing, and run the test_assoc function again.

There are definitely some surprises in these results.