Necessary and sufficient condition for a binary operation to be associative and commutative?

Question

I'm implementing a type conversion routine for a programming language. Under arithmetic context, there can be 4 types: null, signed-int, unsigned-int, floating-point which we'll denote as N, S, U, D for now. For numerical robustness, I decided to make null convert to NaN in floating point should there be such operands.

And here's the type conversion table:

\ N S U D
 +-------
N|N N N D
S|N S U D
U|N U U D
D|D D D D

In my runtime, there's a procedure for determining the type from the type of 2 operands, and that'll need to be applied to a list of more than 2 operands, so this procedure need to be associative and commutative on all operands.

My question is: how do I determine if a binary operation (such as my procedure for determining the type) over a finitely countable (by human standard) set is associative and commutative? I could write a program to enumerate 4ドル^3$ cases to see if my procedure is A&C, but is there other "trick" that's faster?

• Gerry Myerson: Commutative is easy – you just look at your table, and see that it is symmetric. Associative is harder.

Answer 1

Your example table is also idempotent. If that is your typical use case, an easily visualized way of checking that an operation is associative, commutative, and idempotent, i.e., a semilattice, is to write down the Hasse diagram of the intended equivalent poset ($x\le y\iff x=xy$), and check that the operation actually gives the meet of any two elements in this poset. In your case, this seems to be just the linear order

S
|
U
|
N
|
D

Answer 2

Not exactly a "trick", but a way to brutal-force find out whether a table represents an associative binary operator.

In Python: first map N->0, S->1, U->2, and D->3: t = ['0003', '0123', '0223', '3333']

Then a lambda expression: m = lambda a, b: int(t[a][b])

Finally evaluate the expression:

all([ m(i,m(j,k)) == m(m(i,j),k) for i in range(4) for j in range(4) for k in range(4) ])

Which showed True in my console.