6
$\begingroup$

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)?

  • 0
    Cayley graphs/diagrams [are well-defined for semigroups as well](https://books.google.com/books?id=BfawBAAAQBAJ&pg=PA66), 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.2015-04-04
  • 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.)2015-07-26

3 Answers 3

2

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.

  • 0
    Can you elaborate? In particular, I'm not sure what the Cayley graph would look like? Are there finite examples?2012-06-07
  • 1
    Let me make up a few graphs, and then I'll edit the post.2012-06-07
  • 0
    @raxacoricofallapatorius: It has been edited.2012-06-07
  • 0
    Thanks, that helps (and its on the right track, I think). In the second figure though, sometimes $a^2=e$, and sometimes $a^2=a$, even though $a\neq e$. Doesn't that violate (3). If not, then my first figure works after all.2012-06-07
  • 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?2012-06-07
  • 0
    Yes, that's a good question. It's actually unclear to me what "deterministic" means in this context. My interpretation had actually been (A) the first of yours (so I concluded that my first diagram satisfied (3), as yours does). On consideration though (and [based on another question here](http://math.stackexchange.com/q/148970/12400)), I came to the conclusion that it means (B) that if $xy=a$ and $xy=b$ than it must be the case that $a=b$ (which I think is different from being [cancellative](http://en.wikipedia.org/wiki/Cancellation_property).2012-06-07
  • 0
    So my question (here) boils down to whether "deterministic" means (A) or (B). If the former, then the answer to my question is "yes" (as indicated in my first figure and your second); if the latter then the answer—so far anyway—is "no", though I'd like to know for sure.2012-06-07
  • 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.2012-06-07
  • 0
    Thanks. I appreciate it. One point of confusion though: if (B) doesn't my first example violate (3), since "$r^4=e$ and (starting from n) $r^4=r^{−1}$ even though $r^{−1}\neq e$"?2012-06-07
  • 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.2012-06-08
  • 0
    Ah, yes. I was treating the the inverse of the $r$ from the bottom to top right nodes in my $D_4$ and the (non-existant) inverse of the $r$ from $n$ as fungible, which they're not. So my first figure does *not* (despite what I say in the question) violate (3) after all. Note that it does in fact matter how $n$ is connected: the connections must (as they do in the figure) be consistent with $G$ (i.e. they must duplicate the connections from an existing node, here the lower right one). If, for example, $f$ had been connected to the upper right node of the $D_4$ diagram, (3) would be violated.2012-06-08
  • 0
    I believe that your second diagram does violate (3) though (if it means (B)): sometimes $a^2=e$ and sometimes $a^2=a$ (e.g. $1\rightarrow 3;3\rightarrow 1=1\rightarrow 1$, while $1\rightarrow 2;2\rightarrow 0=1\rightarrow 0$). In fact, doesn't it violate (3) even if it means (A), because at nodes 3 and 1, there are 3 possible outcomes for $a$.2012-06-08
  • 1
    I have edited my answer, and hopefully this will dispel further confusion. Let me know what you think/discover.2012-06-08
  • 0
    Thanks, that's *very* helpful, and clears things up quite a bit. Your third diagram now (as near as I can tell) does not violate (3) (even as (B); since, for example even though $f=g^2$ and $f=gf$, that's ok because $g^2=gf$). But it does now violate (4), since there are plenty of combinations of actions that are not possible (for example $f^2$)—unless, at 0, $f=g=h=e$, which would then violate (3) $sensu$ (B).2012-06-08
  • 1
    Yes, at $0$, $f=g=h=e$. *Every* action fixes $0$. That is one of several reasons why it violates (3) $sensu$ (B). Glad I could clear things up for you.2012-06-08
  • 0
    Excellent. Thank you. So my figure does indeed only violate rule (2)—regardless of whether (3) is (A) or (B)—while yours also violates (3) $sensu$ (B), but not (A). Thanks again for your persistence!2012-06-08
  • 0
    Exactly right. Not a problem. Wanna go ahead and accept my answer so we can put this thing to bed?2012-06-08
  • 0
    Sorry! I thought I'd accepted it a while ago.2012-06-09
  • 1
    I've added a note to the question that highlights some of the points you've made here.2012-06-11
  • 0
    Good plan! Always nice to make things available and accessible to future viewers.2012-06-11
  • 0
    @CameronBuie: Exquisite pictures! Can you please delete the blank space over and under each fabulous picture?2014-01-20
  • 0
    @Frank: I am not certain whether I still have copies of the pictures, and at any rate, I don't see a real need to improve the layout.2014-01-20
1

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}$.

  • 0
    That or any semigroup would work.2015-04-05
  • 0
    @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).2015-04-07
  • 1
    It seems commutative monoids can be embedded in groups only when they are also cancellative (via the http://en.wikipedia.org/wiki/Grothendieck_group construction). Your example is such a commutative and cancellative monoid.2015-04-07
0

$A \rightarrow B \rightarrow C$

  • 0
    Isn't that the last figure in my question?2012-06-07
  • 0
    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.2012-06-07
  • 0
    Yes, got turned around. But then $a^{-1}=a^2$, satisfying (2). (Referring to [this version](http://math.stackexchange.com/revisions/155305/2).)2012-06-07
  • 0
    Sorry, we can violate (2) by not sending $C$ anywhere. Otherwise, it is a group.2012-06-07
  • 0
    But that violates (4), no?2012-06-07