Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In constructing a good pedagogical non-example of a group, it would be pleasing to have an example that satisfies all of the properties of being a group except that there is precisely one counterexample to the associative property (especially since this is difficult to read off of a "multiplication table"). Jumping to a set with five elements and constructs a table like

$$ \begin{array}{c | c c c c c} & a & b & c & d & e\\\hline a & a & b & c & d & e \\ b & b & a & d & e & c \\ c & c & e & a & b & d \\ d & d & c & e & a & b \\ e & e & d & b & c & a \end{array}$$

Unfortunately, with this table, many associations that aren't obviously valid fail. I wonder if it is possible to show that the ideal non-example I describe above does not exist. I also wonder if there are examples of tables of small magmas where a "surprisingly large" number of associations are valid (other than group tables!)

share|improve this question

3 Answers 3

up vote 2 down vote accepted

I have posted an argument that there is no such magma before. It contained a mistake, however, so I had to delete it. The following argument is a revised and upgraded version of the previous one and should now hopefully show that there is indeed no such magma. (Satisfying the stricter conditions.)

Suppose that $G$ is an almost-group in your sense: we have an identity, all inverses, but precisely one association fails. In symbols: for precisely one triple $(a,b,c)$ of elements of $G$ we have that $(ab)c\neq a(bc)$. We shall see that this leads to a contradiction.

First I shall prove some lemmas.

Lemma 1. The identity element of $G$ is unique.

Proof. Suppose $e$ and $f$ are identity elements. Then $e = ef = f$, and we are done. $\square$

So, from this point on, $e$ will denote the identity.

Lemma 2. Suppose $d$ is an inverse of $b$, i.e. $bd=db=e$. Then either $d\neq a$ or $d\neq c$.

Proof. Otherwise we would have $a = d = c$, which would imply $(ab)c = (db)c = ec = c = a = ae = a(bd) = a(bc)$, which would contradict our assumption. $\square$

The lemma we have just proved, will allow us to split the various parts of the proof into two cases.

Lemma 3. Every element $x\in G$ has a unique inverse.

Proof. Let $y$ and $z$ be two inverses of $x$, i.e. $xy = yx = e$ and $xz=zx=e$. We shall examine two cases. First case: let $x\neq b$. Then $y(xy)=y(xz)$ and since $x\neq b$, this product associates, so $(yx)y=(yx)z$, which means $y = ey = ez = z$. Second case: let $x = b$. In this case, by lemma 2, either $y\neq a$ in which case $y(xy)=y(xz)$ (which is true by the assumptions of our lemma) will associate on both sides, again yielding $y = z$, or else $y \neq c$ in which case $(yx)y=(zx)y$ will associate on both sides and yield once again $y = z$. $\square$

So, from this point on, we will write $x^{-1}$ for the unique inverse of $x$.

Lemma 4. In $G$ the following implications hold:

  1. if $x\in G$ and $x^2 =x$, then $x=e$,
  2. if $b^{-1}\neq a$ and $xy=xz$, then $y=z$,
  3. if $b^{-1}\neq c$ and $yx=zx$, then $y=z$,
  4. if $x\in G$, then $(x^{-1})^{-1}=x$.

Proof. In all of these proofs we will use the fact that $(a,b,c)$ is the unique triple that does not associate:

  1. We shall again argue by cases: first, if $x\neq b$, we can just multiply by $x^{-1}$, which gives us $x^{-1}(xx)=x^{-1}x$. Here the first product associates, because $x\neq b$, giving us $(x^{-1}x)x=x^{-1}x$, which clearly says that $x=e$. If, on the other hand, $x = b$, we have $b^2=b$. If $b^{-1}\neq a$, this gives $b^{-1}(bb)=b^{-1}b$ and thus by associativity in this case: $b = e$. If $b^{-1} \neq c$, we instead examine $(bb)b^{-1}=bb^{-1}$, which again associates and gives us $b=e$.
  2. If $x\neq b$, the following equalities hold: $y = (x^{-1}x)y = x^{-1}(xy)= x^{-1}(xz) = (x^{-1}x)z = z$. If $x=b$, the same equalities hold, but this time for a different reason: $b^{-1}\neq a$.
  3. This can be proved completely symmetrically.
  4. This one is left as an exercise to the reader, and is again proved by examining the usual cases in pretty much the same way as before.

This concludes the proof. $\square$

Lemma 5. Suppose $(aa)c\neq a(ac)$ and $ac=a$. Then $aa\neq e$.

Proof. Suppose $aa=e$. Then by $(\dagger)$ from the paragraph below, $cc\neq c$, so $cc=(aa)(cc)=a(a(cc))=a((ac)c)=a(ac)=aa=e$. This further implies that $ca\neq e$, because that would imply $a=(ca)a=c(aa)=c$. Further still, $ca\neq c$, because this would imply $a=e$. (Multiply by $c^{-1}$ on the left.) Also, $ca\neq a$, since then $\lbrace e, a, b\rbrace$ would be a commutative submagma of $G$, which would imply $(aa)c=c(aa)=(ca)a=a(ca)=a(ac)$. So we may write $x=ca$, where $x\notin\lbrace e,a,b\rbrace$. We can calculate using the associations we have by our assumptions that this (if consistent at all; in fact it forces all sorts of contradictions) forces the following multiplication table for these elements:

$$\begin{array}{c | c c c c} & e & a & c & x\\\hline e & e & a & c & x \\ a & a & e & a & e \\ c & c & x & e & a \\ x & x & c & x & c \end{array}$$

But this would imply for example $(xx)x=a$ and $x(xx)=x$, a contradiction, since $(a,b,c)$ was supposed to be the only triple that does not associate. $\square$

Now, we shall derive a contradiction. In the following $|A|$ will denote the cardinality of the set $A$. Note that we can always assume that $e\notin\lbrace a,b,c\rbrace$, since otherwise the triple $(a,b,c)$ would associate, contrary to our assumptions. This knowledge together with the first point of lemma 4, tells us that $$aa\neq a, bb\neq b \text{ and } cc\neq c\qquad (\dagger)$$ which will be very useful in the following proofs.

Proposition 1. $|\lbrace a,b,c\rbrace|\neq 1$

Proof. Suppose $|\lbrace a,b,c\rbrace| = 1$. Then we have $a(aa)\neq(aa)a$. We can assume that $aa\neq a$ and $aa\neq e$, since otherwise $a(aa)=(aa)a$, contradicting our basic assumption. So, $aa=x\notin\lbrace e,a\rbrace$. Calculations thus show: $(ax)a^{-1}= a(xa^{-1})=a((aa)a^{-1})=a(a(aa^{-1}))=aa=x$. The third equality here is justified by $a^{-1}\neq a$, since $aa\neq e$. The others are easily seen. But this implies: $xa=((ax)a^{-1})a=(ax)(a^{-1}a)=ax$. The second inequality is again a consequence of $a\neq a^{-1}$. But since $x=aa$ by definition, $xa=ax$ contradicts our assumption. $\square$

Proposition 2. $|\lbrace a,b,c\rbrace|\neq 2$

Proof. Suppose $|\lbrace a,b,c\rbrace| = 2$. Then precisely one of the following holds: $a=b$, $b=c$ or $a=c$. We shall prove that each of these cases is in fact impossible.

First case: $a=b$. In this case we have $(aa)c\neq a(ac)$. The following equality is a consequence of $(\dagger)$: $((aa)c)c = (aa)(cc)=a(a(cc))$ and in $(a(ac))c=a((ac)c)=a(a(cc))$ the first equality is justified by noticing that it can only fail if $ac=b=a$ which by lemma 4 would imply either $c=e$, which isn't the case, or $aa=e$, which is disproved by lemma 5. The second equality is justified by the fact that $a\neq c$. So, strangely $((aa)c)c = (a(ac))c$. But since $c\neq b$, we can multiply by $c^{-1}$ on the right, use associativity and obtain $(aa)c=a(ac)$, a contradiction.

Second case: $b=c$. This one is disproved symmetrically as in the first case. (Using a lemma, symmetric to lemma 5.)

Third case: $a=c$. Here $a(ba)\neq (ab)a$. Multiplying by $b$, we see: $(a(ba))b=a((ba)b)=a(b(ab))=(ab)(ab)$, where the first two equalities follow from $a\neq b$ and the last one from $ab\neq a$, which is seen by multiplying by $a^{-1}$ from the left and using the fact that $b\neq a$. Also, $((ab)a)b=(ab)(ab)$, because $a\neq b$. So, $(a(ba))b = ((ab)a)b$. We multiply by $b^{-1}$ from the right, and use associativity, that follows from the fact that $b^{-1}\neq a$, which lemma 2 kindly provides us with, once again obtaining a contradiction.

This concludes the proof. $\square$

Proposition 3. $|\lbrace a,b,c\rbrace|\neq 3$

Proof. Because $a,b,c$ are distinct in this case, associations are justified a little more easily than before, so we will just write them down. If $ca\neq a$, we may use the following trick: $c((ab)c)=(c(ab))c=((ca)b)c=(ca)(bc)=c(a(bc))$ and multiplying by $c^{-1}$ and using the fact that $c\neq b$, we get $a(bc)=(ab)c$, a contradiction. If $ac\neq c$, a symmetric trick works. So we can assume without loss of generality, that $ac=c$ and $ca=a$. This implies $(ca)c=ac=c$ and $c(ac)=cc$, therefore $cc=c$ and $c=e$ by lemma 4, one last contradiction. $\square$

Now, the cardinality of $\lbrace a,b,c\rbrace$ is clearly $1,2$ or $3$, so these three propositions form a contradiction. This completes the argument.

share|improve this answer
    
Beautiful! I wish I could accept this answer twice! Your proof is not only really cool, but also well-written. It would have been easy to make this proof impossible to follow by writing it poorly, but your writing is extremely clear. I had never read a proof before that assumed non-associativity --- it really made me think! –  Barry Smith Apr 3 '12 at 12:05
    
You've argued to my satisfaction that the minimum positive number of associations that fail to hold for all non-associating magmas of size $n$ with identity and inverses is given by a function $f$ with $f(n) \geq 2$ for all $n$. Now I'm even more curious to know if it is possible to provide an f that increases with n. –  Barry Smith Apr 3 '12 at 12:51
    
@BarrySmith: Glad you like it! It was a really interesting question, so I immediately got hooked. =) I have a feeling such case-by-case analysis could become really hard for a larger number of non-associations, so we may need some new ideas, but it would indeed be interesting to know how $f$ grows. If I think of anything useful in this direction, I'll let you know. –  Dejan Govc Apr 3 '12 at 15:00
    
@BarrySmith: I have posted another answer which hopefully establishes some new (and possibly more interesting) bounds on $f$. –  Dejan Govc Apr 13 '12 at 19:23

I can't think of any good way to do this other than a brute force search. To avoid some isomorphic magmas, fix $a$ as the identity, then divide into 2 cases: $bb=a$ or $bb=c$. In the former case, you can then assume $bc=d$ so the second row is exactly as you show above. If now $cb=e$, then the second column is forced, and a choice of $cc$ as $a$ or $b$ forces the rest of the grid. If instead $cb=d$, then the second column is forced and $cc$ must be $e$ (choosing $a$ or $b$ would lead to an inconsistency); now a choice of $cd$ as $a$ or $b$ forces the rest of the grid. So there are at most 4 nonisomorphic magmas with $bb=a$.

Now if $bb=c$ instead, then we can still assume $bc=d$ so the second row must be $bcdea$, and $ce$ must be $b$ or $d$. If $ce=b$ then the rest of the grid is forced, leading to the group on 5 elements. If $ce=d$ then, $cd$ might be $a$ or $b$. If $cd=b$ this leads to (at most) 3 more (nonisomorphic) magmas depending on the choices for $cc$ and $dc$. If $cd=a$ then the grid completes to at most 2 more magmas.

So if I've done everything correctly (please check, I did it somewhat fast... it reminded me of a Sudoku puzzle), we have at most 10 magmas total, shouldn't be too hard to use a computer to check how much associativity there is in each one (I can't think of a better way).

share|improve this answer

I did some more thinking about non-associativity in magmas and came to some new conclusions. Since my previous answer is already quite long, I'll write a new one for better readability. This also seems more appropriate since this answer will cover a different aspect of the problem.

In the theory of non-associative algebras it is common to define a nucleus. This is the set of all elements that associate with every element. We shall define a nucleus of a magma analogously. We shall say $M$ is an almost-group if $M$ is a magma with identity and all inverses, such that at least one associativity fails (i.e. $\exists x,y,z\in M: (xy)z\neq x(zy)$). We shall define the nucleus of a magma $M$ as follows:$$N(M)=\lbrace x\in M|\text{ }\forall y,z\in M:(xy)z=x(yz)\textrm{ and }(yx)z=y(xz)\textrm{ and }(yz)x=y(zx)\rbrace.$$

We are interested in non-associative almost-groups with a lot of associativity. To study them efficiently, we shall define some functions. We shall say $(x,y,z)\in M^3$ is a non-associative triple if $(xy)z\neq x(yz)$. For each almost-group $M$ define the number of non-associative triples: $$k(M)=\operatorname{card}(\lbrace (a,b,c)\in M^3|\text{ }(a,b,c)\textrm{ is a non-associative triple}\rbrace)$$ Now we can define the following function (as proposed by Barry Smith): $$f:\mathbb N_{\ge 3}\to\mathbb N, f(n)=\min\lbrace k(M)|\text{ }M\textrm{ is an almost group of cardinality } n\rbrace$$

The function $f$ counts the least possible number of non-associative triples an almost-group $M$ of cardinality $n$ can have. In my other answer, I have proven that $f(n)\ge 2$ for all $n\ge 3$. (Note that there are no almost-groups of cardinality less than $3$.) The new result I shall prove here is that $f$ is in fact unbounded. But first I shall need the following lemma.

Lemma. Let $M$ be an almost-group. Then $N(M)$ is a group.

Proof. We shall prove the properties of a group one by one.

  1. Closure. Let $x,y\in N(M)$. We will prove that $xy\in N(M)$. To see this, let $z,w\in M$ be arbitrary elements. The following calculations show that $xy$ associates with every pair of elements from $M$: $$((xy)z)w=(x(yz))w=x((yz)w)=x(y(zw))=(xy)(zw)\\(z(xy))w=((zx)y)w=(zx)(yw)=z(x(yw))=z((xy)w)\\(zw)(xy)=((zw)x)y=(z(wx))y=z((wx)y)=z(w(xy))$$ Here each equality uses either the fact that $x\in N(M)$ or that $y\in N(M)$.
  2. Associativity. $N(M)$ is associative pretty much by definition.
  3. Identity. Let $e$ be the identity of $M$. Then $e$ is an identity of $N(M)$. To see that $e$ is in fact an element of $N(M)$, let $z,w\in M$. Then $(ez)w,e(zw),(ze)w,z(ew),(zw)e$ and $z(we)$ are clearly all equal to $zw$, which proves the claim.
  4. Inverses. Let $x\in N(M)$ and let $x'$ be an inverse of $x$, i.e. $xx'=x'x=e$. We shall prove that $x'\in N(M)$. Again we only have to verify some associativities, so let $z,w\in M$ again be arbitrary. Then: $$(x'z)w=(x'x)((x'z)w)=x'(x((x'z)w))=x'((x(x'z))w)=x'(((xx')z)w)=x'(zw)\\(zx')w=(zx')((xx')w)=(zx')(x(x'w))=((zx')x)(x'w)=(z(x'x))(x'w)=z(x'w)\\(zw)x'=(z(w(x'x)))x'=(z((wx')x))x'=((z(wx'))x)x'=(z(wx'))(xx')=z(wx')$$ Here each step uses either the fact that $x\in N(M)$ or the fact that $xx'=x'x=e$.

This concludes the proof. $\square$

This lemma tells us quite a lot about the structure of almost-groups with a lot of associativity, since these must have a big nucleus. It tells us a large part of them is already a group. Note that the proof of the lemma above (+some knowledge of group theory) actually proves something more: elements of $N(M)$ have unique inverses in $M$ which furthermore lie in $N(M)$.

The next proposition will tell us that for each $n\in\mathbb N$ and $m>6n$ we have $f(m)> n$. (This means $f$ is unbounded.)

Proposition. Let $M$ be an almost-group such that $|M|\ge 6n+1$. Then there are at least $n+1$ non-associative triples in $M$.

Proof. Let $M=N\cup K$, where $N=N(M)$ and $K=M\setminus N(M)$. Suppose there are $\le n$ non-associative triples. This means $|K|\le 3n$ and therefore $|N|\ge 3n+1$. Now, since $M$ is an almost-group, $K$ must be non-empty. So let $z\in K$. Let $A=\lbrace xz|\text{ }x\in N\rbrace$. Note that $A\subseteq K$. (Suppose not. Then there must be some $x\in N$, $z\in K$ such that $xz\in N$. But then $z = (x^{-1}x)z = x^{-1}(xz)\in N$, because $N$ is a group. This is a contradiction.) Therefore $|A|\le 3n$. But $N$ has $3n+1$ elements, so this implies (by the pigeonhole principle) that there must be a pair of distinct elements $x_1,x_2\in N$ such that $x_1z=x_2z$. Furthermore, $z$ has an inverse $z'$. This implies $(x_1z)z'=(x_2z)z'$ and thus $x_1=x_1(zz')=x_2(zz')=x_2$, since $x_1,x_2\in N$. But this contradicts the assumption that $x_1\neq x_2$ and thus concludes the proof. $\square$

So we have found a lower bound for $f$. An upper bound is easier to find: let $G$ be the unique cyclic group of cardinality $n \ge 3$. Change exactly one entry (for example, redefine $1+1$ to be $0$) in its multiplication (in this case addition) table to yield an almost-group $M$. We can count that by doing so, we have changed at most $2n$ triples, therefore we have found an almost-group of cardinality $M$ such that $k(M)\le 2n$. This implies that for each $n\ge 3$ we have the following bounds for $f$: $$\lceil\frac n6\rceil\le f(n)\le2n.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.