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.

My group theory text asks for an example of a Cayley-like diagram that exhibits all the properties of a group except (only) that at least some elements lack an inverse. Is it possible to construct such a diagram?

Nathan Carter p. 24 Question 2.15. in Visual Group Theory (in the context of this question) defines a group as a "collection of actions" that satisfies four rules:

  1. There is a predefined list of actions [generators] that never changes.
  2. Every action is reversible.
  3. Every action is deterministic.
  4. Any sequence of consecutive actions is also an action.

Clearly (2) will be violated in any diagram that is constructed by adding new node, $n$, to the diagram for a group $G$ by one-way arrows for each of the generators in $G$, since it provides no way to reach $n$ from any other nodes, so that paths starting at $n$ (only) cannot be reversed. This will be the case regardless of what nodes in $G$ each of the arrows from $n$ lead to. For example, starting with $G=D_4$:

enter image description here

But, while this diagram satisfies rules (1) and (4), doesn't it also violate (3) because, for example, $r^4=e$ and (starting from $n$) $r^4=r^{-1}$ even though $r^{-1}\neq e$?

EDIT: As discussed below, this figure does not, in fact, violate (3): the $r^{-1}$ mentioned above (the one starting at $n$) does not exist. Also, it does matter where the arrows from $n$ are connected: they must be connected to $G$ in a way that follows $G$'s rules. In the diagram above, for example, if the dotted path had been chosen for $f$ instead of the one indicated, the diagram would violate (3). Rule (3) will always be satisfied in a diagram where the connections from the added node replicate outgoing connections from a node in $G$ (here $m$).

The answer provided in the book's key focuses on the fact that (2) requires that any diagram

...cannot have two arrows of the same type pointing to the same destination from two different sources.

However, while this is certainly a property of (all?) diagrams (including the one above) that violate (2), it is not sufficient to violate (2), and can result in the violation of other rules instead. For example simply "rewiring" one of the cyclic actions in $D_4$ so that it points "to the same destination from two different sources" can produce a diagram that satisfies, (2) but violates (3):

enter image description here

The example offered in the key, violates not only (2), but (3) and (4) as well:

enter image description here

Is it possible to construct a diagram that satisfies rules (1), (3), and (4) while violating (2)?

share|improve this question
Cayley graphs/diagrams are well-defined for semigroups as well, even though Cayley didn't think of them... and you don't often hear of them because semigroup theory is a somewhat boutique area of math. –  Respawned Fluff Apr 4 at 18:57

3 Answers 3

up vote 2 down vote accepted

Multiplication table of $\mathbb{Z}_n$ for any non-prime $n>1$. (Considering $\mathbb{Z}_n$ as an additive group, of course.)

Consider in particular $\Bbb Z_4$. A Cayley graph corresponding to it as an additive group would be:

enter image description here

However, one corresponding to multiplication would be:

enter image description here

There's no way back from $0$, at all, and there is no way to get from $2$ back to either $1$ or $3$. Does that fit what you're looking for?

Edit: I see that my failure to distinguish which arrows corresponded to which actions was confusing. My apologies. There are $4$ actions here--$e,f,g,h$, with $e$ the identity (so no arrows needed)--and I have labeled the various arrows appropriately:

enter image description here

The $0$ node is fixed under every action, and $e$ fixes every node. The $2$ node is also fixed under $h$, and both $f$ and $g$ take $2$ to $0$. Now, if "deterministic" means that different actions cannot take the same node to the same place, then this of course violates (3) for several reasons. However, if it means a given action will work a certain way on a given node, then (3) is not violated, as each node has a clearly designated target corresponding to each action (as I hope the labeling and explication make clear).

I would recommend that you peruse your text for a precise definition of a "deterministic" action. The validity of this answer and of your first example depends entirely on that, as you've noted. Please do let me know what you find out, one way or another. If it turns out that they mean "cancellative"...well, I'll have to think about it some more. I suspect in that case that there may well be no finite examples of what you're looking for.

share|improve this answer
Let me make up a few graphs, and then I'll edit the post. –  Cameron Buie Jun 7 '12 at 20:05
I suppose it depends on what you mean by "deterministic" action. If by that you mean that for a given action and any given node, the action either takes that node to some consistent other node or leaves it be, then this doesn't violate (3), at all. If by "deterministic", you mean that if there is a given node such that 2 actions take that node to the same place, then those 2 actions are the same, then yes, it does violate (3). (The latter type is sometimes also referred to as "cancellative".) Is it one of these, or is it something else? –  Cameron Buie Jun 7 '12 at 20:42
Okay. Well, if it means $xy=a$ and $xy=b$ implies $a=b$, then (3) is not violated, so your first example works. If it means cancellative (that is, $xy=xz$ implies $y=z$), then the examples violate (3), as well, and I'm not sure if we can get around that. I'll think on it. –  Cameron Buie Jun 7 '12 at 21:08
Actually, no...and that is precisely because there is no longer any such action $r^{-1}$, since there is no $r$ arrow leading to $n$. Just as there is no inverse to multiplication by $2$ in my example. –  Cameron Buie Jun 8 '12 at 1:46
I have edited my answer, and hopefully this will dispel further confusion. Let me know what you think/discover. –  Cameron Buie Jun 8 '12 at 15:36

Just take the natural numbers under addition. The diagram then looks like the following. $$0\rightarrow1\rightarrow 2\rightarrow3\rightarrow\cdots$$ This works because the group $\mathbb{Z}$ can be split into $X\sqcup X^{-1}\sqcup \{0\}$ and $X\sqcup\{0\}$ forms a monoid with identity $0$, where $X$ and $X^{-1}$ are such that $x\in X$ if and only if $x\in X^{-1}$.

share|improve this answer
That or any semigroup would work. –  Respawned Fluff Apr 5 at 13:08
@RespawnedFluff Well, any monoid. But I think the problem is more subtle - in semigroups there are "left" Cayley graphs and there are "right" Cayley graphs, which are usually different. But here it is commutative so this doesn't matter. Also, I suspect some commutative monoids would have Cayley graphs which do not form part of a groups Cayley graph (so there is something else going on). I think this is why this example is nice - it is missing inverses, and nothing else. If we add in inverses we get a group/the Cayley graph of a group (note that there is a unique way of adding in the inverses). –  user1729 Apr 7 at 8:17
It seems commutative monoids can be embedded in groups only when they are also cancellative (via the en.wikipedia.org/wiki/Grothendieck_group construction). Your example is such a commutative and cancellative monoid. –  Respawned Fluff Apr 7 at 12:56

$A \rightarrow B \rightarrow C$

share|improve this answer
Isn't that the last figure in my question? –  raxacoricofallapatorius Jun 7 '12 at 20:08
No we send $C\rightarrow A$. In your diagram, sending both $A,B \rightarrow C$ violates (3), like Cameron says, check out the Cayley diagram for $\mathbb{Z}$, which is exactly this. –  rckrd Jun 7 '12 at 20:11
Yes, got turned around. But then $a^{-1}=a^2$, satisfying (2). (Referring to this version.) –  raxacoricofallapatorius Jun 7 '12 at 20:14
Sorry, we can violate (2) by not sending $C$ anywhere. Otherwise, it is a group. –  rckrd Jun 7 '12 at 20:17
But that violates (4), no? –  raxacoricofallapatorius Jun 7 '12 at 20:19

Your Answer


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.