19
$\begingroup$

I'm wondering if it is possible to axiomatize associativity using a set of equations in only two variables.

Suppose we have a signature consisting of one binary operation $\cdot$. Is it possible to find a set $\Sigma$ of equations containing only variables $x$ and $y$, such that the equational theory generated by axioms $\Sigma$ is equal to the equational theory generated by axiom $(x\cdot y)\cdot z = x\cdot (y\cdot z)$?

Or in other words, such that the variety defined by equations $\Sigma$ is equal to the variety defined by equation $(x\cdot y)\cdot z = x\cdot (y\cdot z)$?

EDIT: We can take as $\Sigma$ the set of all equations in variables $x$ and $y$ that are entailed by equation $(x\cdot y)\cdot z = x\cdot (y\cdot z)$. For example $(x\cdot y)\cdot x = x\cdot (y\cdot x)$ is one of the many equations contained in $\Sigma$. The question is whether $\Sigma$ in turn entails $(x\cdot y)\cdot z = x\cdot (y\cdot z)$.

EDIT2: As per Milo Brandt's comment, for any three terms $p(x,y)$, $q(x,y)$, $r(x,y)$ containing at most variables $x, y$, equation $p\cdot (q\cdot r)=(p\cdot q)\cdot r$ is in $\Sigma$. Thus, for any algebra $A$ in the variety defined by equations $\Sigma$, every subalgebra of $A$ generated by two elements is associative. So, in a sense, $A$ is "locally associative".

$\endgroup$
  • $\begingroup$ This property is equivalent to alternativity by Artin's theorem. $\endgroup$ – pregunton Dec 24 '19 at 8:35
  • $\begingroup$ @pregunton Doesn't Artin's theorem only apply to algebras over rings? (The proofs I could find after a quick Google search all use additive structure as well as multiplicative structure.) $\endgroup$ – Alex Kruckman Dec 24 '19 at 14:33
  • $\begingroup$ @AlexKruckman You're right, sorry, I misread the question. $\endgroup$ – pregunton Dec 24 '19 at 16:50
33
$\begingroup$

To answer the question negatively, it suffices to find an algebra $(A, \cdot)$ such that each subalgebra generated by two elements is associative, but such that $A$ itself is non-associative.

Let $A=\{a,b,c\}$, and let $\cdot$ be defined by $$ab=ba=bb=b\\ bc=cb=cc=c\\ ca=ac=aa=a.$$

Every subset of $A$ of size $2$ is the domain of a subalgebra, isomorphic to $(\{0,1\},\max)$, which is associative. But $A$ is not associative, since $(ab)c = bc = c$, but $a(bc) = ac = a$.

| cite | improve this answer | |
$\endgroup$
9
$\begingroup$

No, this is not possible - and, rather luckily, while it seems like this question could potentially be very hard, this particular instance works out okay.

First, let $F:\mathbf{Set}\rightarrow\mathbf{Magma}$ be the free magma functor. Let $S=\{a,b,c\}$ be a set of three elements and consider $FS$. Let's define an equivalence relation $\sim$ on $FS$ generated by the following relations:

  1. If $p\sim p'$ and $q \sim q'$ then $pq\sim p'q'$.

  2. For any $x,y\in FS$ and any $p,q,r\in \langle x,y\rangle$ we have $p(qr)\sim (pq)r$.

The first condition ensures that we can define multiplication on the quotient $FS/\sim$ and the second condition ensures that every equation in two variables that follows from associativity holds in $FS/\sim$ - or, equivalently, that for every two elements $x,y\in FS/\sim$ there is a map from the free semigroup on two elements to $FS/\sim$ taking the generators to $x$ and $y$ respectively. Note that $\langle x,y\rangle$ refers to generation in $FS$ not in $FS/\sim$.

However, we can prove that $a(bc)\not\sim (ab)c$ without too much trouble because there's just not really any relation we can usefully apply to it. The particularly nice thing about $FS$ is that every element is either a generator, or can uniquely be written as a product of two others.

First, $a$ and $b$ and $c$ are not of the form $pq$, so none of the generating relations apply to them - so their equivalence classes are singletons. Similarly, $ab$ and $bc$ have singletons as equivalence classes because they are products of elements whose equivalence classes are singletons - so (1) applies, but doesn't generate any equivalences. They are not of the form necessary to apply (2).

Finally, let's show that the equivalence class of $a(bc)$ is a singleton. The first rule applies, but doesn't generate any relations because $a$ and $bc$ both have singleton equivalence classes. The second rule only references $a(bc)$ if $p=a$ and $q=b$ and $r=c$ - however, there is no set of two generators that generates all of $\{a,b,c\}$ in $FS$. Thus $a(bc)$ is a singleton - and in particular $a(bc) \not\sim (ab)c$ so $FS/\sim$ is not associative, yet satisfies every two element equation following from associativity.

This reasoning probably extends to answer similar questions of this form, but it seems pretty hard to write down exactly what that generalization would be.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ +1, nice analysis. But there's something I don't quite understand: how do you know that point 2 encompasses all 2-variable consequences of associativity? That is, there is conceivably some other equation in two variables that's true in all associative algebras, but which does not follow from the equations of the form described in point 2. $\endgroup$ – Alex Kruckman Dec 23 '19 at 23:53
  • 3
    $\begingroup$ Ah, nevermind: to check that an equation in two variables holds, it suffices to show it holds in all 2-generated subalgebras. Your equations imply all 2-generated subalgebras are associative. So any 2-variable consequence of associativity also follows from your equations. $\endgroup$ – Alex Kruckman Dec 24 '19 at 0:11

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.