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

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

  • 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
    But that violates (4), no?2012-06-07