Does associativity imply commutativity?

Question

I used to think that commutativity and associativity are two distinct properties. But recently, I started thinking of something which has troubled this idea: $$(1+1)+1 = 1+ (1+1)\implies 2+1=1+2$$ Here using associativity of addition operation, we've shown commutativity.

In general, $$\underbrace{(1+1+\dots+1)}_{a \, 1\text{'s }}\ \ + \ \ \underbrace{(1+1+\dots+1)}_{b \, 1\text{'s }}=\underbrace{(1+1+\dots+1)}_{b \, 1\text{'s }}\ \ + \ \ \underbrace{(1+1+\dots+1)}_{a \, 1\text{'s }} \\ \implies a+b=b+a$$ For any natural $a,b$. Hence using only associativity we prove commutativity. That this can be done, is disturbing me too much. Is this really correct? If yes, then are associativity and commutativity closely related? Or is it because of some other property of natural numbers? If yes, then can it be done for other structures as well?

Answer 1

Well done - you've essentially rediscovered free objects. In particular, what you've observed is that in the semigroup freely generated by one element (call it $1$), addition happens to be commutative.

In other words: you've essentially explained why addition in $\mathbb{Z}_{\geq 1}$ is commutative.

But, I wouldn't say that associativity implies commutativity in general. For instance, multiplication of $2 \times 2$ matrices provides a fundamental example of an associative operation that isn't commutative. Furthermore, the non-equivalence of associativity and commutativity is clear even if we stick to free algebras:

• in the semigroup freely generated by two elements (call them $A$ and $B$), commutativity fails in a big way. For example, $A + B \neq B+A$ in this context.

• in the commutative magma freely generated by one element (call it $1$), associativity fails in a big way. For example $(1+1)+(1+1) \neq ((1+1)+1)+1$ in this context.

Free algebras are pretty tricky, so don't feel discouraged if you don't 'get' them right away - nobody ever does. It can take a year or two before the idea truly 'sinks in,' and almost discovering them yourself will only help a little in this regard.

You may find this question helpful to get you started.

Answer 2

Clever observation. This is called a cyclic group (or the generalized version, free object). $ G $ is said to be cyclic, if there is some set $ s $, called the "generating element", such that

$$ G = \langle s \rangle = \{ n \in \mathbb{Z} : s^n \} = \{e, s, s^2, s^3, \ldots s^{-1}, s^{-2}, s^{-3}, \ldots \} $$

That is, all elements can be "generated" from a single element.

In this case $ s = 1 $, but let's forget that for a moment, and consider the general case:

1. Are cyclic objects always abelian?

2. Are all groups cyclic?

To 1., the answer is relatively simple: Yes. To verify this, we simply observe that $$ s^n s^m = \underbrace{sss\ldots s}_{n + m} = s^{n + m} = s^{m + n} = s^m s^n $$

Thus $ ab = ba $ in $ G $.

Now, for 2., the easiest way to prove that not all algebraic objects are cyclic, is to construct an object that isn't cyclic nor abelian. The simplest example is the group, $ G $, of bijective functions, $ \mathbb{R} \to \mathbb{R} $, under composition.

You can easily see that it is associative, at the same time it is relatively easy to verify that this is in fact not abelian (I will let you do that). Therefore it cannot be cyclic.

Another (more funky) way we can see that it is not cyclic is by Cantor's diagonal argument: Define $ \mathbb{R} $ as $ \{ f \in G : f(0) \} $. If $ G $ was cyclic, we would be able to enumerate the real numbers, by $ \mathbb{R} = \{ n \in \mathbb{Z} : s^n(0) \} $, which is not possible, as shown by the diagonal argument.

A bonus: Often people mistakenly believe that commutativity implies associativity, but that's in fact not true! Consider $ a * b = ab + 1 $. This is obviously commutative, but it isn't associative.

Answer 3

using only associativity we prove commutativity

Well, not really. You also used your knowledge that any natural number (but not zero or negative numbers!) can be expressed as a sum of 1s. And you didn't prove "commutativity" in general; you proved "commutativity of addition (of natural numbers)", which you already knew to be true anyway.

A simple example of an operation that is associative but not commutative is "addition of strings" as defined in most programming languages — that is, string concatenation. Concatenation is associative:

("abc" + "def") + "ghi" = "abcdefghi"
"abc" + ("def" + "ghi") = "abcdefghi"

However, obviously, it's not commutative:

"abc" + "def" = "abcdef"
"def" + "abc" = "defabc"

And vice versa: an example of an operation that is commutative but not associative is $x\star y = xy+1$.

$ (1 \star 2) = 3 \\ (2 \star 1) = 3 \\ \text{but} \\ (1 \star 2) \star 3 = 3 \star 3 = 10 \\ 1 \star (2 \star 3) = 1 \star 7 = 8 $

Answer 4

If you have a group where every element is a power/multiple of a single element, then the group will be cyclic and hence Abelian. It looks like this is what you are doing. Recall that a group $G$ is called cyclic if $$ G = \{g^n : n\in \mathbb{Z}\}. $$ Then indeed you have that any two elements $h$ and $k$ can be written $h = g^n$ and $k = g^m$ for integers $n$ and $m$. Then $hk = g^ng^m = g^{n+m} = g^{m+n} = g^mg^n = kh$.

Note, specifically, that the integers (under addition) is a cyclic group.

But, no, associativity does not imply commutativity. There are many examples. Take any non-Abelian group: $n\times n$ matrices over (most) rings, permutation groups, ...

Answer 5

A standard example of associative non-commutative structure are square matrices $M_{n\times n}(\Bbb C)$ with respect to a usual matrix product.

One can easily build commutative non-associative structures, like the "rock-paper-scissors", where the binary operation yields the winner: $$(p,p)\to p,\quad (p,r)\to p,\quad (p,s)\to s,\quad etc.$$

Hence these properties are not related in general, yet, for natural numbers, as other members of the community said, you are in luck.

Answer 6

The easiest counter-example that I can think of is function composition. We know that $f \circ(g \circ h) = (f \circ g) \circ h$ but it is not necessarily true that $f \circ g = g \circ f$.

As someone else pointed out, if that was true, then there wouldn't be any non abelian groups.

Answer 7

Consider an $\operatorname L$ operator defined as 'take the left': $$a \operatorname L b = a$$ For any three $a,b,c$: $$(a \operatorname L b) \operatorname L c = a \operatorname L c = a = a \operatorname L b = a \operatorname L (b \operatorname L c)$$ but $$a \operatorname L b = a \ne b = b \operatorname L a$$ unless $a=b$.