70
$\begingroup$

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?

$\endgroup$
64
$\begingroup$

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.

$\endgroup$
16
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ I am not sure whether you are using \mathopen{<}s\mathclose{>} $\mathopen{<}s\mathclose{>}$ on purpose. I guess $\langle s \rangle$ \langle s \rangle is used more often. $\endgroup$ – Martin Sleziak Jun 14 '16 at 19:10
  • $\begingroup$ I normally write it that way. $\endgroup$ – AnonymousC Jun 14 '16 at 19:12
  • $\begingroup$ I have changed it. $\endgroup$ – AnonymousC Jun 14 '16 at 19:14
  • 3
    $\begingroup$ Is that intended to be $a*b=ab+1$ on the last line? A typo? $\endgroup$ – David K Jun 14 '16 at 19:29
  • $\begingroup$ Yeah, good find. $\endgroup$ – AnonymousC Jun 14 '16 at 19:33
14
$\begingroup$

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 $

$\endgroup$
  • $\begingroup$ Your answer is correct, I guess just to be pedantic for the benefit of anyone who might be confused by your correct answer, in case one is only working with the concatenation of strings with one letter (unary alphabet) then commutativity is equivalent to associativity (since this monoid is isomorphic to the free monoid with one generator/natural numbers + 0) $\endgroup$ – Chill2Macht Apr 30 '17 at 8:36
  • 1
    $\begingroup$ @Chill2Macht: First of all, you don't mean "strings of one letter" (e.g. "a" or "x"); you mean "strings from an alphabet of length 1" (e.g. "a", "aa", "aaaaaaa"). Secondly, you don't mean "commutativity is equivalent to associativity"; you mean that "concatenation in such a restricted case happens to be equivalent to addition; that is, it is commutative." There is a whole family of languages closed under concat where concat happens to be commutative; e.g. the language described by the regular expression (cat)*. The language (a)* just happens to be the most boring one. :) $\endgroup$ – Quuxplusone Apr 30 '17 at 16:48
  • $\begingroup$ Yes, basically (strings of a one-letter alphabet) -- what does "addition" of strings from an alphabet of length 1 mean? Also I think I do mean that, in that restricted case, commutativity is equivalent to associativity, e.g. since 2+1 = 1+2 by commutativity, we have (1+1)+1=1+(1+1), i.e. associativity (admittedly I'm not sure if the example generalizes), and the OP gives the argument that associativity implies commutativity. $\endgroup$ – Chill2Macht Apr 30 '17 at 18:04
  • 1
    $\begingroup$ @Chill2Macht: The OP's example shows that addition of natural numbers is both commutative and associative; but it doesn't show anything about the logical relationship between those two properties in general. In your own example, the relationship between "a", "aa", "aaa", and concatenation-of-strings is isomorphic to the relationship between 1, 2, 3, and addition-of-natural-numbers; that's what I meant by "concatenation [in that case] is equivalent to addition". $\endgroup$ – Quuxplusone Apr 30 '17 at 19:43
  • $\begingroup$ You are right and that makes sense. I know it doesn't show anything about the logical relationship between the two properties in general; I am talking/asking about the logical relationship between the two properties in that restricted case, i.e. for the free semigroup generated by one element (obviously they aren't equivalent in general). $\endgroup$ – Chill2Macht May 1 '17 at 4:14
10
$\begingroup$

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, ...

$\endgroup$
  • $\begingroup$ It's not clear how "$ n\times n$ matrices over (most) rings" provides an example of a nonabelian group. (The set of nonsingular $2\times2$ matrices over a field does constitute a nonabelian group under multiplication, however.) $\endgroup$ – John Bentin Jun 15 '16 at 9:45
8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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$.

$\endgroup$
5
$\begingroup$

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.

$\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.