How many associative binary operations for a set of two elements?

Suppose we have a set $S=\{a,b\}.$ Obviously, the total number of binary operations on $S$ is the number of all the pairs such that $$*(a,b)=a \, \text{or} \, b,$$ which gives $ 2 \cdot 2 \cdot 2 \cdot 2=2^4$ possible ones. Is there a way to find which of these $16$ binary operations are associative without writing all the operation matrices and checking it by hand?

As YCord points out, we can restate the question as:

What are the semigroup structures $\ast$ on a set of two elements?

There are few enough operations on two elements that we can carry out the analysis manually without too much effort.

An efficient way to approach the problem is to split cases according to whether the elements of the set, say, $a, b$, are idempotent.

Case I: Both elements are idempotent If both elements are idempotent, so that $a^2 = a$ and $b^2 = b$, it remains to define $ab, ba$.

• If $ab = ba$, then by relabeling we can assume $ab = ba = a$. Then, under the relabeling $a \rightsquigarrow 0, b \rightsquigarrow 1$, $\ast$ is the logical operation $$\textsf{AND}.$$
• If $ab = a, ba = b$, the operation is $$\textsf{L} : (x, y) \mapsto x .$$
• If $ab = b, ba = a$, the operation is $$\textsf{R} : (x, y) \mapsto y .$$ (Checking directly shows that all of these operations are associative.)

Case II: Some element is not idempotent If there is an element that is not idempotent, by relabeling we may assume it is $b$, so that the elements of the set are are $b, b^2$. I'll leave the rest of this case as an exercise for the reader.

Allowing for relabeling $a \leftrightarrow b$, we see that $$\color{#df0000}{\boxed{\textrm{there are $8$ associative operations on a set of two elements}}} .$$ We record these operations below. The bijection exchanging $a \leftrightarrow b$ induces dualities among some of them, leaving $5$ operations up to isomorphism. For convenience in identifying them with familiar logical operators, as above we relabel the elements by $\{0, 1\}$.

• The constant operation $\textsf{0}$ is dual to the constant operation $\textsf{1} : (x, y) \mapsto 1$.
• The operation $\textsf{AND}$ is dual to $\textsf{OR}$.
• The operation $\textsf{XOR}$ is dual to $\textsf{XNOR}$.
• The operation $\textsf{L}$ is self-dual (dual to itself).
• The operation $\textsf{R}$ is self-dual.