1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Considering that this 7-page paper (the first google result I got) is needed for the number of associative binary operators on a $5$-element set, I don't think there is a nice and simple general way (at least not a known one). Although since they clearly haven't checked all possible 3-element multiplications for all the 298,023,223,876,953,125 possible operations (at least I don't think they have, I haven't actually read the thing) you might be able to find some nice shortcuts. $\endgroup$ – Arthur Aug 3 '18 at 13:54
  • 2
    $\begingroup$ The result in that paper leads to OEIS sequence A023814, which contains the counts up to $9$-element set and a few links but no results. (Note that the counts up to $9$-element sets where shortly before that paper was published, so apparently that wasn't state of the art.) $\endgroup$ – joriki Aug 3 '18 at 14:02
1
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.