4
$\begingroup$

Question: Consider the binary operation on the free commutative magma generated by one element. Is this binary operation also associative?

Note: I do not mean the free magma (1)(2) generated by one element -- I mean the quotient of this object by the appropriate equivalence relation inducing commutativity.

Background: This question is meant as a sort of "converse" to this question. In the answers and discussion surrounding that question, it was established that the associativity of addition of $\mathbb{N}$ implies the commutativity of the addition of $\mathbb{N}$ (see also here, here, or here). More generally, it was established that the binary operations of both the free semigroup and of the free monoid generated by one element are commutative. (Obviously these are isomorphic to $\mathbb{N}$, depending on whether one doesn't or does include $0$ as a natural number.)

In particular, I am well aware that, in general, neither does associativity imply commutativity nor does commutativity imply associativity. Neither general implication is the nature of my question.

As far as I understand, it is also possible to prove that addition on the natural numbers is commutative without appealing to associativity (1)(2). However, it can also be proven by appealing to associativity. So I would be interested to know if there is a proof of associativity of addition on the natural numbers which appeals to commutativity of addition (assuming that commutativity can be proven independently of associativity).

$\endgroup$
7
  • 1
    $\begingroup$ I am not sure how relevant the part about commutativity of addition is since that is specifically for the natural numbers, rather than for the free magma generated by one element (which is not commutative). My guess would be that the commutative version is not associative, since that would make it isomorphic to the naturals, but rather it should be possible to describe it by having a unique representative of each equivalence class with the parentheses in some "minimal" configuration. $\endgroup$ Commented May 2, 2017 at 9:04
  • $\begingroup$ @TobiasKildetoft The last part makes sense, I agree. Just to be clear/for the record though, I am not talking about the free magma generated by one element, I am talking about the free commutative magma generated by one element. (It's the same sort of thing how a free abelian group isn't actually a free group, I think. I don't know how else to phrase it more clearly.) $\endgroup$ Commented May 2, 2017 at 10:04
  • 1
    $\begingroup$ Hmm, not being that familiar with magmas in general. Is the free commutative magma the same as the free magma modulo all commutation relations? $\endgroup$ Commented May 2, 2017 at 10:21
  • 1
    $\begingroup$ In general, one can have commutativity but $(aa)(aa) \ne ((aa)a)a$. For example, consider the magma whose elements are the symbols $a, aa, (aa)a = a(aa), (aa)(aa), ((aa)a)a = a((aa)a)$, agreeing that a product of five or more $a$'s is equal to $a$. Then this magma is commutative but not associative. If the free commutative magma were associative, so would this one be, since it is a quotient of it. $\endgroup$
    – user49640
    Commented May 3, 2017 at 8:29
  • 1
    $\begingroup$ Another proof with the same counterexample. If you represent elements of the free magma by finite trees, the length of the longest branch is invariant under commutations. Now the tree $((aa)a)a$ has a branch of length 3, but $(aa)(aa)$ has only branches of length 2. $\endgroup$
    – J.-E. Pin
    Commented May 3, 2017 at 11:34

1 Answer 1

3
$\begingroup$

In general, one can have commutativity but $(aa)(aa)\ne((aa)a)a$. For example, consider the magma whose elements are the symbols $a,aa,(aa)a=a(aa),(aa)(aa),((aa)a)a=a((aa)a)$, $b$ agreeing that a product of $b$ and anything or of five or more $a$'s is equal to $b$. Then this magma is commutative but not associative. If the free commutative magma were associative, so would this one be, since it is a quotient of it.

$\endgroup$
2
  • $\begingroup$ If the product of five or more $a$'s is equal to $a$, then $a = (a((aa)(aa)) ) = (a(a((aa)(aa))))$ whence $(aa) = (a(a((aa)(aa)))) = a$. I think you should simply assume instead that all products of length $\geqslant 5$ are equal (but not to $a$). $\endgroup$
    – J.-E. Pin
    Commented May 4, 2017 at 8:56
  • $\begingroup$ @J.-E.Pin Thanks for the correction. That was careless of me. $\endgroup$
    – user49640
    Commented May 4, 2017 at 21:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .