# Associativity of binary operations on a two-element underlying set (is there a pattern?)

The overall problem is to establish, which binary operations on a two-element set $$A=\{a, b\}$$ are commutative and associative. There are 16 of them altogether, obviously, analogous to operations on Booleans: $$\begin{array}{c|c|c|c|c|c|c} & x & y & O_1 & O_2 & ... & O_{16} \\\hline P_1 & a & a & a & a & ... & b \\\hline P_2 & a & b & a & a & ... & b \\\hline P_3 & b & a & a & a & ... & b \\\hline P_4 & b & b & a & b & ... & b \\\hline comm. & & & + & + & ... & + \\\hline assoc. & & & + & + & ... & + \\\hline \end{array}$$

The case of commutativity is simple, it is enough to check if $$a*b=b*a$$, so to check that $$P_2$$ and $$P_3$$ are both the same. It also yields a perfect symmetry:

$$+ + - - - - + + + + - - - - + +$$

But the associativity is not that straightforward in terms of the algorithm and does not seem to produce any pattern. There is no well-ordering property of A, so it seems the induction does not lend itself to it.

I did not come up with any simple approach to prove associativity, so I have composed a simple Python code to exhaust all the combinations:

a = "a"
b = "b"
A = (a, b)

for i in range(16):
Ops = {
(a, a): b if (i//8)%2 else a,
(a, b): b if (i//4)%2 else a,
(b, a): b if (i//2)%2 else a,
(b, b): b if i%2     else a
}

# test associativity: x * (y * z) = (x * y) * z
assoc = True;
for x in A:
for y in A:
for z in A:
yz   = Ops[(y, z)]
x_yz = Ops[(x, yz)]

xy   = Ops[(x, y)]
xy_z = Ops[(xy, z)]
if x_yz != xy_z:
assoc = False

print(i, Ops.values(), assoc)

It produces the following output:

$$+ + - + - + + + - + - - - - - +$$

There seems to be no pattern here. But the ratio of associative operations is 50%, just as of the commutative ones.

I have perused several useful answers related to this topic, namely:

Showing associativity

Number of associative binary operations

Ratio of associative binary operations

What I understood is that there is no simple proof (algorithm) for checking associativity, especially if we take a larger underlying set. (Or is there?)

Secondly, the ratio of associative operations will decrease with the growth of the underlying set.

Associativity is somehow related to idempotence, i.e. operations, where $$a*a=a$$ and $$b*b=b$$. Namely, associativity occurs more readily, where idempotence holds.

My questions are:

1. Is there a non-obvious pattern in the incidence of associative operations?

2. Is there an inductive or other style of proof for associativity when the underlying set growth beyond a binary set? (not just a brute-force approach I did)

The number of associative binary operations on an $$n$$-set is the A023814 OEIS sequence. There is no known closed formula for it.
Your question is also related to the number of two-element semigroups. First, finite semigroups always contain an idempotent (an element $$e$$ such that $$ee = e$$). So let's suppose that $$a$$ is idempotent. If $$b$$ is not idempotent, then $$b^2 \not= b$$ and hence $$b^2 = a$$. One possibility is that $$ba = ab = a$$, so that $$a$$ is actually a zero. The other possibility is $$ba = ab = b$$, which corresponds to the cyclic group of order $$2$$.
Suppose now that $$a$$ and $$b$$ are both idempotent. Then there are three other semigroups of this kind. The first one is the monoid $$\{1,0\}$$ under the usual multiplication of integers. The second one is defined by $$aa = ab = a$$ and $$ba = bb = b$$. The third one is $$aa = ba = a$$ and $$ab = bb = b$$.
So altogether, you have $$5$$ possible two-element semigroup. You get $$8$$ operations, because you are not classifying operations up to isomorphisms.
• Meanwhile, am I correct to understand that operation isomorphism is when $a$ is interchanged with $b$ simultaneously in operands and in the results? Like $x \land y$ will yield $a$ in case $x=y=a$, (implying $a$ is "true") and $b$ in other cases. Or, isomorphically, if we consider $b$ is "true" then $x \land y$ will yield $b$ in case $x=y=b$ and $a$ in other cases? Commented Apr 22, 2021 at 9:50
• Yes, switching $a$ and $b$ leads to isomorphic semigroups. Commented Apr 22, 2021 at 12:22