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
1  
I just updated my answer. I'm sure you no longer need the help, but I've recently better acquainted myself with (how to use TeX to make) Cayley-like diagrams. I suspect you're even better at it than I am, at this point, so if you have any suggestions for how to clean up the formatting, let me know. (I also included a reference to the portion of Carter's text that explains determinism, for future users' reference.) –  Cameron Buie yesterday

3 Answers 3

up vote 2 down vote accepted

Edit: To construct such a diagram, we can consider the multiplication table of $\mathbb{Z}_n$ for any $n>1$. (Considering $\mathbb{Z}_n$ as an additive group, of course.)

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

enter image description here

Above, the arrows clearly indicate the action of addition by $1,$ modulo $4$, which generates the group. However, the diagram for multiplication would be:

enter image description here

Above, the red arrows indicate multiplication by $2,$ modulo $4;$ the blue line indicates a two directional swap that occurs under multiplication by $3,$ modulo $4.$ These two actions readily generate all four actions in the monoid.

Now, this diagram violates reversibility in two ways, since there's no way back from $0$, at all, and there is no way to get from $2$ back to either $1$ or $3$. (The corresponding diagram for $\Bbb Z_n$ violates reversibility in exactly one way if and only if $n$ is prime.) This does not, however, violate determinism, as a perusing of Carter $\S1.2,$ pages $4-5$ shows. To elucidate this further, consider the following example, which (arguably) violates only determinism.


Suppose we have a thin metal disk with rounded edges (such that it cannot balance on edge), one black face, and one white face. We will put this disk in a large, flat, circular area with up-curved edges (like a large, flat-bottomed bowl), so that it can't escape or fetch up against a wall. Our generating action is to put the disk on edge in the center of the area and spin it until it comes to rest again. The available states are black-side-up and white-side-up. This yields the following Cayley-like diagram:

enter image description here

Note in particular that for every instance of the action, there is a chance of remaining in the pre-spin state or switching states--in this uncertainty, determinism is violated. However, due to our construction, no matter how many times we spin it, there are no other states in which the disk can be, so any sequence of consecutive actions is again an action. The finicky part is reversibility. The argument is that the disk will eventually switch sides with probability $1,$ which (in real-world terms) means we'll always return to a previous state, if we simply act sufficiently-many times.

The situation is, of course, rather contrived (and arguably doesn't really work), but the Cayley-like diagram shows what happens when determinism fails: there is at least one action that "branches" at at least one node. This doesn't happen with multiplication in $\Bbb Z_4$, and so determinism is not violated in that case.

share|improve this answer
1  
Let me make up a few graphs, and then I'll edit the post. –  Cameron Buie Jun 7 '12 at 20:05
1  
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
1  
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
1  
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
1  
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
1  
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

 
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.