Does general commutativity require associativity?

357 Views Asked by At

There is a theorem that if an operation is associative on 3 elements from a set, it is associative on any number of them. This property is called general associativity.

Similarly, there's a theorem that commutativity implies general commutativity (any permutation on the elements produces the same result). However, its proof here assumes a semigroup, that is, associativity is assumed. So, does associativity have to be true in order for general commutativity to be true as well? If so, can some claim about (general) commutativity be made when associativity doesn't hold?

3

There are 3 best solutions below

2
On BEST ANSWER

If you want to make sense of 'general commutativity' of a binary operation $\star$ in absence of associativity, you should adopt a convention for how you associate the operation, otherwise (as Mike Earnest suggests in his answer) it is not possible to make sense of expressions such as $x \star y \star z$.

So suppose you adopt the convention that you associate to the left, so that, for instance, $x \star y \star z$ actually means $(x \star y) \star z$. Then the question is whether commutativity implies general commutativity in this sense, i.e. whether commutativity implies that $$x_1 \star x_2 \star \cdots \star x_n = x_{\sigma(1)} \star x_{\sigma(2)} \star \cdots \star x_{\sigma(n)}$$ for all $n \ge 1$ and all permutations $\sigma \in \Sigma_n$, with the convention of left-associativity.

Surprisingly the answer is 'no'. For example, consider the operation $\star$ on the set $X = \{ a, b \}$ defined by $$a \star a = b \qquad a \star b = b \star a = a \qquad b \star b = a$$ This operation is evidently commutative, however $$(a \star b) \star a = a \star a = b \quad \text{but} \quad (a \star a) \star b = b \star b = a$$ So we see that it is not 'generally commutative'.

And, as expected, $\star$ is not associative, since $a \star (a \star b) = a \star a = b$, but $(a \star a) \star b = b \star b = a$.

0
On

The theorem "commutativity $\implies$ general commutativity" only makes sense in the context of an associative operation. General commutativity, if I understand it correctly, is the statement that $$ x_1\circ x_2\circ \ldots \circ x_n=x_{\pi(1)}\circ x_{\pi(2)}\circ \ldots \circ x_{\pi(n)} $$ for all permutations $\pi$. However, in order for the expression $x_1\circ x_2\circ \ldots \circ x_n$ to be unambiguous, $\circ$ needs to be associative.

0
On

We can prove the converse. If you have commutivity but not necessarily general commutivity and we don't have associativity, then we don't have general commutivity.

I think general commutivity must mean $(ab)c = (bc)a = (ca)b = (ba)c = (ac)b =(cb)a$.

But as $xy = yx$ then $(ab)c = (bc)a = a(bc)$ so we have associativity. So we can't have general commutativity without associativity.