12 Weak central groupoids

In this chapter we study weak central groupoids Definition 2.30,

x = (y ⋄ x) ⋄ (x ⋄ (z ⋄ y)) .

The first observation is that this law is equivalent to its dual:

Lemma 12.1 1485 equivalent to 2162

Definition 2.30 is equivalent to the dual law

x = ((y ⋄ z) ⋄ x) ⋄ (x ⋄ y)

(equation 2162).

Proof ▶

It suffices to prove that Equation 1 implies Equation 2. Write $w = y ⋄ z$ , then from Equation 1 we can write $z = z_{1} ⋄ z_{2}$ with $z_{1} = z ⋄ z$ and $z_{2} = z ⋄ (z ⋄ z)$ , and then by Equation 1

y = (z_{2} ⋄ y) ⋄ (y ⋄ (z_{1} ⋄ z_{2})) = (z_{2} ⋄ y) ⋄ w .

From another application of Equation 1 we have

x = (w ⋄ x) ⋄ (x ⋄ ((z_{2} ⋄ y) ⋄ w)) = ((y ⋄ z) ⋄ x) ⋄ (x ⋄ y)

as required.

Given a weak central groupoid $G$ , define a directed graph with vertices in $G$ by declaring $x \to y$ if and only if $y = x ⋄ z$ for some $z$ . There is an equivalent characterization of this graph:

Lemma 12.2 Equivalent characterization of graph

One has $x \to y$ if and only if $x = w ⋄ y$ for some $w$ .

Proof ▶

If $x \to y$ then $y = x ⋄ z$ , then writing $z = z_{1} ⋄ z_{2}$ as before we obtain

x = (z_{2} ⋄ x) ⋄ (x ⋄ (z_{1} ⋄ z_{2})) = (z_{2} ⋄ x) ⋄ y

giving the forward implication. The backwards implication follows by duality.

Define a good path in $G$ to be a path of the form

x \to x ⋄ y \to y

for some $x, y \in G$ (we allow loops). By the above lemma, this is a path in $G$ . The following claims are clear from definition and the above lemma:

If $x, y \in G$ then there is exactly one good path $x \to z \to y$ from $x$ to $y$ .
Any edge $x \to y$ in the directed graph is the initial segment of some good path $x \to y \to z$ .
Any edge $x \to y$ in the directed graph is the final segment of some good path $w \to x \to y$ .

Slightly more non-trivial is

Lemma 12.3 Claim 4

If $a \to b \to c \to d \to e \to a$ is a 5-cycle in the directed graph, and $a \to b \to c$ and $c \to d \to e$ are good paths, then $b \to c \to d$ is also good.

Proof ▶

If $a \to b \to c$ is good then $b = a ⋄ c$ ; if $c \to d \to e$ is good then $d = c ⋄ e$ ; and if $e \to a$ then $a = e ⋄ z$ for some $z$ by definition. By Equation 2 we then have

c = ((e ⋄ z) ⋄ c) ⋄ (c ⋄ e) = b ⋄ d

so $b \to c \to d$ is good.

Conversely, we have

Lemma 12.4 Reversing the claims

Let $G$ be a directed graph, with some paths of length two in the graph designated as “good”, in such a way that Claims 1-4 hold. Then there is a weak central groupoid structure on the vertices of $G$ such that the good paths are precisely the paths of the form $x \to x ⋄ y \to y$ .

Proof ▶

Define an operation $⋄ : G \times G \to G$ by defining $x ⋄ y$ to be the unique vertex $z$ for which one has a good path $x \to z \to y$ ; this is well-defined by Claim 1, and by Claims 2-3, the property $x \to y$ holds if and only if $y = x ⋄ z$ for some $z$ , and also if and only if $x = w ⋄ y$ for some $w$ . In particular, for all $x, y, z$ , we have a $5$ -cycle

y \to y ⋄ x \to x \to x ⋄ (z ⋄ y) \to (z ⋄ y) \to y

with $y \to y ⋄ x \to x$ and $x \to x ⋄ (z ⋄ y) \to (z ⋄ y)$ good, hence by Claim 4 we have Equation 1 as required.

This gives us a graph-theoretical route to construct weak central groupoids. We first introduce a weaker version of Claim 1:

If $x, y \in G$ then there is at least one good path $x \to z \to y$ from $x$ to $y$ .

Let us call a relaxed weak central groupoid a directed graph with some paths of length 2 designated as “good” that obeys Claims 1’, 2, 3, 4.

We also define a partial weak central groupoid to be a directed graph with some paths of length 2 that obeys Claim 4 as well as the following opposite weakening of Claim 1:

If $x, y \in G$ then there is at most one good path $x \to z \to y$ from $x$ to $y$ .

If we can upgrade Claim 1” to Claim 1, and we also have Claim 2 and Claim 3, then we call this a complete weak central groupoid, and by the previous proposition this is in correspondence with Equation 1.

Let $G_{0}$ be a relaxed weak central groupoid. A partial extension of $G_{0}$ is a partial weak central groupoid $G$ with a “projection map” $π : G \to G_{0}$ , which is a homomorphism in the sense that the image $π (x) \to π (y)$ of any edge $x \to y$ in $G$ is an edge in $G_{0}$ , the image $π (x) \to π (y) \to π (z)$ of any good path $x \to y \to z$ in $G$ is a good path in $G_{0}$ , and the image $π (x) \to π (y) \to π (z)$ of any bad path $x \to y \to z$ in $G$ is a bad path in $G_{0}$ . Note that Claim 4 for $G$ is then automatic from Claim 4 of the base $G_{0}$ . The extension is complete if the partial weak central groupoid is complete.

We have the following convenient completion property:

Proposition 12.5 Completion property

Let $G_{0}$ be a directed graph obeying claims 1’, 2, 3, 4. Then any finite partial extension of $G_{0}$ with carrier $G_{0} \times N$ (and projection map $π (a, n) = a$ ) can be completed to a complete extension.

Proof ▶

By the previous comments, we can ignore Claim 4 as it is automatic, and focus on completing the partial weak central groupoid on $G$ to a complete weak central groupoid by ensuring Claims 1, 2, 3 hold. By the usual greedy algorithm, it suffices to show that any individual failure of Claim 1, 2 or 3 can be resolved by adding some finite number of edges to the graph.

Suppose first that Claim 2 fails, that is to say the partial weak central groupoid contains an edge $(a, n) \to (b, m)$ that is not the initial segment of any good path. Since the base relaxed weak central groupoid $G_{0}$ obeys Claim 2, we can find a good path $a \to b \to c$ in the base. We then pick a natural number $l$ not previously occurring in the partial weak central groupoid, and adjoin the edge $(b, m) \to (c, l)$ to that partial weak central groupoid. All new paths created in this way are declared good or bad depending on whether their images in $G_{0}$ are good or bad, in particular $(a, n) \to (b, m) \to (c, l)$ is good. This can be checked to still be a partial extension of $G_{0}$ (no violation of Claim 1” is created), and now Claim 2 is resolved at for the edge $(a, n) \to (b, m)$ . A similar argument permits one to resolve any violations of Claim 3.

If Claim 1 is violated, then there is a pair $(a, n), (b, m)$ that currently has no good path of length two in the partial weak central groupoid. As the base relaxed weak central groupoid $G_{0}$ obeys Claim 1’, we can find a good path $a \to c \to b$ in $G_{0}$ . We then pick a natural number $l$ not previously occurring, and adjoin the edges $(a, n) \to (c, l) \to (b, m)$ . All new paths created in this way are declared good or bad depending on whether their images in $G_{0}$ are good or bad, in particular $(a, n) \to (c, l) \to (b, m) \to (c, l)$ . One can check that this is still a partial extension of $G_{0}$ (no violation of Claim 1” is created), and now Claim 1 is resolved at the pair $(a, n), (b, m)$ .

Theorem 12.6 1485 does not imply 1483

Definition 2.30 does not imply any of the following laws:

Equation 3457: $x ⋄ x = x ⋄ ((x ⋄ x) ⋄ y)$ .
Equation 2087: $x = ((y ⋄ x) ⋄ x) ⋄ (x ⋄ x)$ .
Equation 2124: $x = ((y ⋄ y) ⋄ x) ⋄ (x ⋄ x)$ .
Equation 3511: $x ⋄ y = x ⋄ ((x ⋄ y) ⋄ x)$ .

Proof ▶

Computer check reveals that the carrier $G_{0} = {0, 1, 2, 3, 4}$ with incidence matrix

(\begin{matrix} 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \end{matrix})

is a relaxed weak central groupoid if we declare the paths $0 \to 0 \to 0$ , $0 \to 0 \to 1$ , $0 \to 1 \to 1$ , $1 \to 0 \to 0$ , $1 \to 1 \to 0$ , $1 \to 1 \to 1$ to be bad, and all other paths in the directed graph to be good. We can also check the following axioms:

Anti-3457: There exist $x, y, z, w$ with $x \to z \to x$ , $z \to w \to y$ both good, and $x \to z \to w$ bad. (One can take $x = 1$ , $y = 4$ , $z = 0$ , $w = 0$ .)
Anti-2087: There exist $x, y, z, w, u$ with $y \to z \to x$ , $z \to w \to x$ , and $x \to u \to x$ good, and $w \to x \to u$ is bad. (One can take $x = 1, y = 2$ , $z = 4$ , $w = 1$ , $u = 0$ .)
Anti-2124: There exists $x, y, z, w, u$ with $y \to z \to y$ , $z \to w \to x$ and $x \to u \to x$ good, and $w \to x \to u$ bad. (One can take $x = 1$ , $y = 2$ , $z = 4$ , $w = 1$ , $u = 0$ .)
Anti-3511: There exists $x, y, z, w$ with $x \to z \to y$ and $z \to w \to x$ good, and $x \to z \to w$ bad. (One can take $x = 1$ , $y = 3$ , $z = 1$ , $w = 0$ .)

Let $G_{*}$ be a finite partial extension of $G_{0}$ to be chosen later. By Proposition 12.5, we can complete this to a complete weak central groupoid $G$ with carrier $G_{0} \times N$ . Depending on how we choose $G_{*}$ , we can ensure that this $G$ refutes one of the four laws 3457, 2087, 2124, 3511:

Refuting 3457: Let $x, y, z, w$ be as in the claim Anti-3457, then select $G_{*}$ to be the directed graph with edges $(x, 0) \to (z, 2) \to (x, 0) \to (z, 2) \to (w, 3) \to (y, 1)$ . One can check that this is a partial extension, and that $G$ will refute 3457 with $x, y$ replaced by $(x, 0), (y, 1)$ .
Refuting 2087: Let $x, y, z, w, u$ be as in the claim Anti-2087, then select $G_{*}$ to be the directed graph with edges $(y, 1) \to (z, 2) \to (x, 0)$ and $(z, 2) \to (w, 3) \to (x, 0) \to (u, 4) \to (x, 0)$ . One can check that this is a partial extension, and that $G$ will refute 2087 with $x, y$ replaced by $(x, 0), (y, 1)$ .
Refuting 2124: Let $x, y, z, w, u$ be as in the claim Anti-2124, then select $G_{*}$ to be the directed graph with edges $(y, 1) \to (z, 2) \to (y, 1)$ and $(z, 2) \to (w, 3) \to (x, 0) \to (u, 4) \to (x, 0)$ . One can check that this is a partial extension, and that $G$ will refute 2124 with $x, y$ replaced by $(x, 0), (y, 1)$ .
Refuting 3511: Let $x, y, z, w$ be as in the claim Anti-3511, then select $G_{*}$ to be the directed graph with edges $(x, 0) \to (z, 2) \to (y, 1)$ and $(z, 2) \to (w, 3) \to (x, 0)$ . One can check that this is a partial extension, and that $G$ will refute 3511 with $x, y$ replaced by $(x, 0), (y, 1)$ . □

12.1 Twisting a weak central groupoid

Occasionally, an equational law is preserved under a “twist” operation in which one replaces the magma operation $x ⋄ y$ by $x ⋄^{'} y := T x ⋄ U y$ for some automorphisms $T, U$ of the magma $G$ that obey additional relations. In the case of the weak central groupoid law Equation 1, we see that

(y ⋄^{'} x) ⋄^{'} (x ⋄^{'} (z ⋄^{'} y)) = (T^{2} y ⋄ T U x) ⋄ (U T x ⋄ (U T U z ⋄ U^{3} y))

so if $T$ is an automorphism of order $5$ and $U = T^{- 1}$ (so that $T^{2} = U^{3}$ ), we conclude that this twisted magma is also a weak central groupoid. This can be used to generate further counterexamples. For instance, let $M_{2}$ be the order two weak central groupoid with carrier $F_{2}$ and with the NAND operation $x ⋄ y := 1 - x y$ ; this can easily be verified to be a weak central groupoid. It does not have any nontrivial automorphisms, but its fifth power $M_{2}^{\otimes 5}$ has a cyclic shift $T$ of order $5$ : $T ((x_{i})_{i \in Z / 5 Z}) = (x_{i + 1})_{i \in Z / 5 Z}$ . If we twist $M_{2}^{\otimes 5}$ by $T$ and $T^{- 1}$ , we obtain a weak central groupoid $M$ with carrier $F_{2}^{5}$ and magma operation

(x_{i})_{i \in Z / 5 Z} ⋄ (y_{i})_{i \in Z / 5 Z} = (1 - x_{i + 1} y_{i - 1})_{i \in Z / 5 Z} .

In particular, if $x = (x_{i})_{i \in Z / 5 Z}$ , then

x ⋄ x = (1 - x_{i + 1} x_{i - 1})_{i \in Z / 5 Z}

and

(x ⋄ x) ⋄ (x ⋄ x) = (1 - (1 - x_{i + 2} x_{i}) (1 - x_{i} x_{i - 2}))_{i \in Z / 5 Z}

which by the laws of boolean algebra simplify to

(x ⋄ x) ⋄ (x ⋄ x) = (x_{i} (x_{i - 2} + x_{i} + x_{i + 2}))_{i \in Z / 5 Z}

from which one can easily refute equation 151,

x = (x ⋄ x) ⋄ (x ⋄ x) .

Informally, the reason for this is that equation 151 has a different semigroup twist symmetries: $T^{2} = 1, T = U^{- 1}$ instead of $T^{5} = 1, T = U^{- 1}$ .