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

Question

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)

Answer 1

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.