Theory and Applications of Categories, Vol. 26, No. 27, 2012, pp. 743–767.

TANGLED CIRCUITS

R. ROSEBRUGH AND N. SABADINI AND R. F. C. WALTERS

Abstract. We consider commutative Frobenius algebras in braided strict monoidal categories in the study of the circuits and communicating systems which occur in Computer Science, including circuits in which the wires are tangled. We indicate also some possible novel geometric interest in such algebras. For example, we show how Armstrong’s description ([1, 2]) of knot colourings and knot groups fit into this context.

1. Introduction

The theme of this paper is the use of commutative Frobenius algebras in braided strict monoidal categories in the study of varieties of circuits and communicating systems which occur in Computer Science, including circuits in which the wires are tangled. We indicate also some possible novel geometric interest in such algebras.

The main definition of the paper is of tangled circuit diagrams. To make this definition we need the notion of monoidal graph M (see Section 3). Then a tangled circuit diagram (over M) is an arrow in the free braided strict monoidal category on M in which the objects of M are equipped with commutative Frobenius algebra structures.

In order to study tangled circuit diagrams we define two different invariants for tangled circuits, one which takes values in a tangled category of relations, and the other in a tangled version of the category of spans. The second type of invariant includes as special cases the colourings of knots, and knot groups (following work of Armstrong [1, 2]).

The authors and collaborators have previously studied similar systems using symmetric monoidal categories ([8, 9, 10, 11, 17, 18, 19, 5]), with separable algebras instead of Frobenius algebras. These earlier works did not take into consideration any tangling of the wires. Further we will see in Section 6.5 the importance of considering Frobenius algebras rather than the more special separable algebras even in the symmetric monoidal case (no tangling).

There is a huge literature now relating monoidal categories and geometry beginning with [7, 12, 16]. We mention just two further items of an expository nature useful to reading this paper (apart from our own work mentioned above): the first [20] is a survey for computer scientists and others which discusses many additional structures but strangely not Frobenius algebras, and ignores our work on separable algebras; the second [13] is an introductory book on the relation between Frobenius algebras and 2-dimensional cobordism.

Received by the editors 2011-11-07 and, in revised form, 2012-11-14.

Transmitted by Ross Street. Published on 2012-12-03.

2010 Mathematics Subject Classification: 18B20, 18D10, 68Q05, 68Q85.

Key words and phrases: circuit diagram, braided monoidal category, tangle algebra.

\begin{matrix}c \\ ◯ \end{matrix} R. Rosebrugh and N. Sabadini and R. F. C. Walters, 2012. Permission to copy for private use granted.

1.1. Acknowledgements. We would like to thank Aurelio Carboni and the anonymous referee for helpful suggestions.

2. Braided monoidal categories and Frobenius algebras

We review immediately the notions which are fundamental for the paper.

2.1. Definition. A braided strict monoidal category ([7]) is a category C with a functor, called tensor, ⊗ : C × C [figure] C and a “unit” object I together with a natural family of isomorphisms τ_{A,B} : A ⊗ B [figure] B ⊗ A called twist satisfying

1) ⊗ is associative and unitary on objects and arrows,

2) the following diagrams commute for objects A, B, C:

[figure: B1 :; A ⊗ B ⊗ C; B ⊗ A ⊗ C; τ⊗1; A ⊗ B ⊗ C; B ⊗ C ⊗ A; τ; B ⊗ C ⊗ A; B ⊗ A ⊗ C; 1⊗τ]

and

[figure: B2 :; A ⊗ B ⊗ C; A ⊗ C ⊗ B; 1⊗τ; A ⊗ B ⊗ C; C ⊗ A ⊗ B; τ; C ⊗ A ⊗ B; A ⊗ C ⊗ B; τ⊗1]

Among the consequences of the definition is the Yang-Baxter equation which reads:

(1 ⊗ τ)(τ ⊗ 1)(1 ⊗ τ) = (τ ⊗ 1)(1 ⊗ τ)(τ ⊗ 1) : A ⊗ B ⊗ C [figure] C ⊗ B ⊗ A

A compact and comprehensible formulation of such properties is provided by circuit or“wire” diagrams like the one below for the Yang-Baxter equation. Composition is read from left to right and ⊗ is vertical juxtaposition. The twist is expressed by the “positive crossing” (top wire over bottom) and its inverse by the negative crossing.

=

Another consequence of the axioms above is that τ_{A,I} = τ_{I,A} = 1_{A} : A [figure] A.

The naturality of the twist τ leads to the following kind of equality of diagrams:

R  =                 R

In the case when the codomain of the component is I, naturality is drawn, for example, as:

R  =                 R

The following structures on an object in a braided monoidal category are fundamental to describing circuits.

2.2. Definition. A Frobenius algebra in a braided monoidal category consists of an object G and four arrows ∇ : G ⊗ G [figure] G, Δ : G [figure] G ⊗ G, n : I [figure] G and e : G [figure] I making (G, ∇, e) a monoid, (G, Δ, n) a comonoid and satisfying the equations

(1_{G} ⊗ ∇)(Δ ⊗ 1_{G}) = Δ∇ = (∇ ⊗ 1_{G})(1_{G} ⊗ Δ) : G ⊗ G [figure] G ⊗ G.

The Frobenius algebra is said to be commutative if in addition the following equations involving the twist hold:

∇τ = ∇ : G ⊗ G [figure] G
τΔ = Δ : G [figure] G ⊗ G

3. Tangled circuit diagrams

We propose a definition for a category of tangled circuit diagrams, in which it is possible to distinguish, for example, the first and second of the following circuit diagrams, while the second and third are equal.

R  R  R

The main definitions are:

3.1. Definition. A monoidal graph M consists of two sets M_{0} (objects or wires) and M_{1} (arrows or components) and two functions dom : M_{1} [figure] M_{0}^{∗} and cod : M_{1} [figure] M_{0}^{∗} where M_{0}^{∗} is the free monoid on M_{0}.

3.2. Definition. Given a monoidal graph M the free braided strict monoidal category in which the objects of M are equipped with commutative Frobenius algebra structures is called TCirc_{M}. Its arrows are called tangled circuit diagrams, or more briefly circuit diagrams. In the case that M has one object and no arrows we will denote TCirc_{M} simply by TCirc.

The basic structure we require on an object is the following.

3.3. Definition. An object X in a braided strict monoidal category (with twist τ) is called a tangle algebra when it is equipped with arrows η : I [figure] X ⊗X and ϵ : X ⊗X [figure] I that satisfy the equations (where we write 1 for all identities):

(i) (ϵ ⊗ 1)(1 ⊗ η) = 1 = (1 ⊗ ϵ)(η ⊗ 1)

(ii) ϵτ = ϵ and τη = η.

Axiom (i) says that X is a self-dual object. The reader can translate these into wire diagrams. For example the wire diagram for (i) is:

=  =

3.4. Theorem. If G is a commutative Frobenius algebra in a braided strict monoidal category, then the object G together with the arrows ϵ = e∇, η = Δn form a tangle algebra.

Proof. Let G be a commutative Frobenius algebra in a braided monoidal category. It is straightforward to give algebraic proofs for the tangle algebra axioms, but we remind the reader that these can be more easily found using wire diagrams.

To see that (ϵ ⊗ 1)(1 ⊗ η) = 1 notice that

(e ⊗ 1)(∇ ⊗ 1)(1 ⊗ Δ)(1 ⊗ n) = (e ⊗ 1)Δ∇(1 ⊗ n) = 1 · 1 = 1.

3.5. Definition. (Freyd-Yetter [6]) The category Tangle is the free braided strict monoidal category generated by one object X, equipped with a tangle algebra structure.

The category Tangle has a geometric description [21] consonant with its name. In that description the arrows from I to I are unoriented knots and links.

Given any object A of M it is straightforward to see that there is an appropriate functor from Freyd and Yetter’s category Tangle to TCirc_{M} since a symmetric Frobenius structure on A induces a tangle algebra structure on A. As a result any invariants of tangled circuit diagrams provide also invariants for tangles and knots. We conjecture that such functors Tangle [figure] TCirc_{M} are faithful. We also conjecture that there is a topological description of TCirc_{M} related to Freyd and Yetter’s description of Tangle and to cobordisms.

3.6. Corollary. Given an object A of a monoidal graph M there is a unique braided strict monoidal functor Tangle [figure] TCirc_{M} taking the generating object to A and the structure maps of Tangle to the corresponding structure maps of A in TCirc_{M}.

3.7. Remark. Notice that in TCirc_{M} the commutative Frobenius algebra structures on the objects of M induce Frobenius algebra structures on each object (that is, on multiple wires) of TCirc_{M}. However these Frobenius algebra structures are not commutative and hence the corresponding η and ϵ do not satisfy the commutativity property (ii) of tangle algebras.

3.8. Example equations. We now give some examples of equations between circuit diagrams.

3.9. Proposition. If R : X × Y [figure] I is an arrow in the monoidal graph M then

Rτ_{Y,X}^{−1} = ϵ_{X}(1_{X} ⊗ R ⊗ 1_{X})(η ⊗ 1_{Y} ⊗ 1_{X}) = Rτ_{X,Y}

.

Proof. First a picture of the equations:

R =           R  =           R

It is clearly sufficient to prove the first equation. Consider:

(commutativity) R  =  R  (naturality) R

R =  R =  (naturality) (duality)

3.10. Proposition. If R : I [figure] X ⊗ X and S : X ⊗ X [figure] I then Sτ^{2n}R = SR; that is, R and S joined by an even number of twists is equal to R and S joined directly.

Several more equations provable in TCirc follow:

3.11. Example.

                                       =

Proof.

(∇_{X} ⊗ 1_{X})(1_{X} ⊗ τ_{X})(Δ_{X} ⊗ 1_{X}) = (∇_{X} ⊗ 1_{X})(τ_{X} ⊗ 1_{X})(1_{X} ⊗ τ_{X})(Δ_{X} ⊗ 1_{X}) (commutativity)
= (∇_{X} ⊗ 1_{X})(1_{X} ⊗ Δ_{X})τ_{X}  (naturality)
= Δ_{X}∇_{X}τ_{X}  (Frobenius)
= Δ_{X}∇_{X}  (commutativity)

3.12. Remark. The geometric intuition is that single wires are thick (but not ribbons) and so can be deformed contracting segments. Notice however that it is not true in general in TCirc that the separable axiom ∇Δ = 1 holds. That is, cycles of wires cannot be contracted to a point.

3.13. Example.

= H_{1} H_{2}  U_{1} U_{2}  H_{1} H_{2}  U_{1} U_{2}

3.14. Example. If R : I [figure] X ⊗ X and S : X ⊗ X [figure] I then

S(ϵ ⊗ ϵ ⊗ 1 ⊗ 1)(1 ⊗ τ^{−1} ⊗ τ^{−1} ⊗ 1)(1 ⊗ 1 ⊗ η ⊗ η)R = SττR = SR.

Diagrammatically:

R  S  =        R  S

Proof. We will give a diagrammatic proof. A more explicit picture of the left hand expression is

R  S

By naturality this is equal to

R  S

and hence to

R  S

This simplifies by duality to

R  S

It is now clear that repeating the argument using naturality and duality we obtain the result.

3.15. Dirac’s belt trick. We claim that the following two circuits are equal in TCirc, that is that a rotation through 4π of a component I [figure] X^{3} is equal to the identity. We suspect, but are unable to prove, that a rotation through 2π is not the identity.

R  S

R  S

We give a sketch of a proof only. Using arguments similar to that of example 3.14 we may prove that the first (twisted) circuit is equal to

S R

Naturality gives equality to

S R

and then to

R  S

which is equal to the untwisted circuit.

3.16. Remark. In a separate article [15] we investigate a group structure on the set of blocked-braids on n-strings, that is, on circuits of the form SBR where R : I [figure] X^{n}, S : X^{n} [figure] I and B is a braid on n strings.

4. A braided category of relations

The category Rel whose objects are sets, and whose arrows are relations is symmetric monoidal with the tensor of sets being the cartesian product, and each object has a commutative Frobenius (even separable) algebra structure provided by the diagonal functions and their reverse relations. In fact this was the motivating example for the introduction in [3] of the Frobenius equations Equivalent axioms had been given earlier by Lawvere in [14]. We describe here a modification of Rel which we call TRel_{G}, which depends on a group G, and which is braided rather than symmetric. We further describe a commutative Frobenius algebra in TRel_{G} which hence yields a representation of TCirc_{M}, and this representation enables us to distinguish various circuits. We discuss distinguishing closed circuits, a problem analogous to classifying knots, using TRel_{G}.

4.1. The definition of TRel_{G}. We will describe a braided modification of the category Rel with a commutative Frobenius object.

4.2. Definition. Let G be a group. The objects of TRel_{G} are the formal powers of G, and the arrows from G^{m} to G^{n} are relations R from the set G^{m} to the set G^{n} satisfying:

1) if (x_{1}, ..., x_{m})R(y_{1}, ...y_{n}) then also for all g in G (gx_{1}g^{−1}, ..., gx_{m}g^{−1})R(gy_{1}g^{−1}, ..., gy_{m}g^{−1}),

2) if (x_{1}, ..., x_{m})R(y_{1}, ...y_{n}) then x_{1}...x_{m}(y_{1}...y_{n})^{−1} ∈ Z(G) (the center of G).

Composition and identities are defined to be composition and identity of relations.

It is straightforward to verify that TRel_{G} is a category; that is, that identities and composites of relations satisfying 1) and 2) also satisfy 1) and 2). Notice also that if the group G is abelian the conditions 1) and 2) of Definition 4.2 are trivially true. We introduce some useful notation. Write x = (x_{1}, ..., x_{m}), y = (y_{1}, ..., y_{n}), and so on. Write \overline{x} = x_{1}x_{2}...x_{m} and for g, h in G, as g^{h} = hgh^{−1}. For g in G write x^{g} = (x_{1}^{g}, x_{2}^{g}, ..., x_{m}^{g}). Thus, (\overline{x})^{g} = \overline{x^{g}}, and of course for any x, y in G^{m} × G^{n}, x^{g}y^{g} = (xy)^{g} where we write xy for (x_{1}, ..., x_{m}, y_{1}, ..., y_{n}).

4.3. Theorem. TRel_{G} is a braided strict monoidal category with tensor defined on objects by G^{m} ⊗ G^{n} = G^{m+n} and on arrows by product of relations. The twist

τ_{m,n} : G^{m} ⊗ G^{n} [figure] G^{n} ⊗ G^{m}

is the functional relation

(x, y) ∼ (y\overline{x}, x)

Proof. The monoidal structure of Rel restricts to TRel_{G} since if R : G^{m} [figure] G^{t} and S : G^{n} [figure] G^{u} satisfy 1) and 2) then so also does R × S. To see that R × S satisfies 1) notice that if xRy and zSw then for any g ∈ G, x^{g}Ry^{g} and z^{g}Sw^{g} and hence (xz)^{g}(R × S)(yw)^{g}. To see that R × S satisfies 2) notice that, if \overline{x}(\overline{y})^{−1} ∈ Z(G) and \overline{z}(\overline{w})^{−1} ∈ Z(G), then \overline{xz}(\overline{yw})^{−1} = (\overline{x})(\overline{z})((\overline{y})(\overline{w}))^{−1} = (\overline{x})(\overline{z})(\overline{w})^{−1}(\overline{y})^{−1}. But \overline{z}(\overline{w})^{−1} ∈ Z(G), so (\overline{x})(\overline{z})(\overline{w})^{−1}(\overline{y})^{−1} = (\overline{x})(\overline{y})^{−1}(\overline{z})(\overline{w})^{−1} and the latter is in Z(G).

It is straightforward that τ satisfies properties 1) and 2). We show that B1 holds for τ as defined. B2 is similar.

First note that τ_{m,n+p}(xyz) = (yz)\overline{x}x. Further (τ_{m,n} ⊗ 1_{G^{p}})(xyz) = y\overline{x}xz while (1_{G^{n}} ⊗ τ_{n,p})(xyz) = xz\overline{y}y. Thus

(1_{G^{n}} ⊗ τ_{n,p})(τ_{m,n} ⊗ 1_{G^{p}})(xyz) = (1_{G^{n}} ⊗ τ_{n,p})((y\overline{x})xz) = (y\overline{x})(z\overline{x})x = τ_{m,n+p}(xyz).

Lastly we need to show that τ_{m,n} : G^{m} × G^{n} [figure] G^{n} × G^{m} is natural. This amounts to two conditions. Consider R : G^{p} [figure] G^{m} and S : G^{q} [figure] G^{n} in TRel_{G}. The first condition for naturality is that

τ_{m,n}(R ⊗ 1_{G^{n}}) = (1_{G^{n}} ⊗ R)τ_{p,n} : G^{p+n} [figure] G^{n+m}.

But xyzw (x ∈ G^{p}, y ∈ G^{n}, z ∈ G^{n}, w ∈ G^{m}) belongs to the left-hand side iff xRw and z = y\overline{w}, whereas xyzw belongs to the right-hand side iff xRw and z = y\overline{x}. But condition 2) implies that if xRw then for any y it follows that y\overline{x} = y\overline{w}, and hence the result.

The second condition for naturality is that

τ_{m,n}(1_{G^{m}} ⊗ S) = (S ⊗ 1_{G^{m}})τ_{m,q} : G^{m+q} [figure] G^{n+m}.

But xyzw (x ∈ G^{m}, y ∈ G^{q}, z ∈ G^{n}, w ∈ G^{m}) belongs to the left-hand side iff x = w and yS(z^{\overline{x}^{−1}}), whereas xyzw belongs to the right-hand side iff x = w and y\overline{x}Sz. Condition 1) implies the result.

4.4. Remark. Notice that a relation in TRel_{G} from I to G^{n} is just a subset of G^{n} closed under conjugation by elements of G and whose elements x satisfy \overline{x} ∈ Z(g). Further a relation from I to I is either the empty set or the one-point set.

4.5. The commutative Frobenius structure on G. The commutative Frobenius structure on the object G of TRel_{G} mentioned above is as follows: ∇ is a function, namely the multiplication of the group G, n : I [figure] G is also a function, the identity of the group; Δ is the opposite relation of ∇, e is the opposite relation of n.

For the resulting tangle algebra structure on G, notice that η is the relation ∗ ∼ (x, x^{−1}), and ϵ is the opposite relation of η.

It is straightforward to check that these relations belong to TRel_{G}. We will just check one of the Frobenius equations, namely that

(1_{G} ⊗ ∇)(Δ ⊗ 1_{G}) = Δ∇ : G × G [figure] G × G.

If g, h, p, q are in G then (g, h, p, q) belongs to the left-hand relation if there is a r ∈ G such that g = pr and rh = q. But this is the same as saying that p^{−1}g = qh^{−1} or gh = pq which is exactly the condition for (g, h, p, q) to be in the right-hand relation.

The Frobenius algebra structure on G in TRel_{G} actually satisfies the additional separable axiom ∇Δ = 1.

4.6. Proving circuits distinct in TRel_{G}. In this section we discuss the possibility of distinguishing various tangled circuits by looking in TRel_{G}. These include the analogue of knots, or closed circuits, which are circuits from the one-point set I to I.

4.7. Example. First an example where two circuits may be distinguished in TRel_{S_{3}}, where S_{3} is the symmetric group on three letters. The circuits are:

R  S  R  S

Proof. Let each of R and S be the set of conjugates of u = ((1, 2), (1, 3), (2, 3), (1, 3)) under the action of G (not G × G × G × G). Notice that (1, 2)(1, 3)(2, 3)(1, 3) is the identity and so in the centre of G. The second circuit evaluates as the one point set.

The first circuit evaluates instead as the empty set since the braid ττ × 1_{G} × 1_{G} in the first circuit relates ((1, 2), (1, 3), (2, 3), (1, 3)) in R to ((1, 3), (2, 3), (2, 3), (1, 3)) which is not in the conjugacy class of u since the second and third elements are equated by the braid.

Notice that a similar argument using the symmetric group S_{3} works for two components joined by n > 3 wires, the first two of which are tangled.

4.8. Example. We will see that the first two circuits in Section 3 can also be shown distinct in TRel_{S_{3}}. It is clearly sufficient to show the following circuits distinct:

R  R

Take R to be the following subset of (S_{3})^{2} × (S_{3})^{2}: the conjugacy class of the element (((1, 2), (1, 3)), ((1, 2), (1, 3))). Then the first circuit evaluates as ∅ and the second as the one-point set.

4.9. Example. Next an example of two circuits which we believe are distinct in TCirc_{M} but are always equal in TRel_{G}. For any group G, TRel_{G} cannot distinguish them.

R  S R  S

Proof. Suppose (x, y, z) is an element of component R. Notice that since xyz is in the centre xyz = yzx = zxy. The braid between the two components in the first circuit relates (x, y, z) to

u = (xyx^{−1}zxy^{−1}x^{−1}, xyx^{−1}, z^{−1}xz) = (xyx^{−1}zxy^{−1}x^{−1}, z^{−1}yz, z^{−1}xz)

since yzx = zxy. Instead the braid in the second circuit relates (x, y, z) to

v = (z, z^{−1}yz, z^{−1}y^{−1}xyz) = (z, xyx^{−1}, x)

since z^{−1}y^{−1}xyz = z^{−1}y^{−1}yzx = x and zxy = yzx. But xzuz^{−1}x^{−1} = v since

xzxyx^{−1}zxy^{−1}x^{−1}z^{−1}x^{−1} = xyzxx^{−1}zxx^{−1}z^{−1}y^{−1}x^{−1} = xyzy^{−1}x^{−1} = z

and hence u and v are conjugate. Since S is closed under conjugacy, the element (x, y, z) gives rise to an element of the first circuit if and only if it does for the second circuit. Since this is true for any (x, y, z) the two circuits are equal in TRel_{G}.

4.10. Example. In fact the last example is general for three wires. The circuit obtained by composing in TRel_{G} any two components R : I [figure] G^{3} and S : G^{3} [figure] I with a braiding in between depends only on the permutation, not the braiding.

Proof. Suppose (x, y, z) ∈ R then xyz ∈ Z(G) and hence xyx^{−1} = z^{−1}yz, yzy^{−1} = x^{−1}zx and zxz^{−1} = y^{−1}xy. Consider two composites R composed with τ ⊗ 1 and R composed with τ^{−1} ⊗ 1. Consider (x, y, z) ∈ R. We will show that these two composites associate (x, y, z) with conjugate triples. Repeating this we see that the argument given in the above example can be applied, showing that in a composite τ and τ^{−1} are interchangeable.

In the first composite (x, y, z) is related to u = (xyx^{−1}, x, z) = (z^{−1}yz, y, z). In the second composite (x, y, z) is related to (y, y^{−1}xy, z). It is immediate that zuz^{−1} = v.

Of course such circuits with different permutations can be distinguished even in TRel_{ℤ_{2}}.

4.11. Example. Here are another two circuits we can distinguish in TRel_{S_{3}}:

H_{1} H_{2}  U_{1} U_{2} U_{3} U_{4}  H_{1} H_{2}  U_{1} U_{2} U_{3} U_{4}

Proof. Replace each of the four components U_{1},U_{2},U_{3},U_{4} by ϵ. Let H_{1} be the conjugacy class of ((1, 2), (1, 3), (2, 3), (1, 3)). The wires of the first circuit relate this element to u = ((1, 2), (2, 3), (1, 2), (1, 3)), and of the second circuit to v = ((1, 3), (1, 2), (1, 2), (1, 3)). Clearly u and v are not conjugate, and hence we can choose H_{2} so that the two circuits evaluate differently in TRel_{S_{3}}.

4.12. Example. The following two circuits can be distinguished in TRel_{S_{3}}.

R  S  R  S

Proof. Take R to be the conjugacy class of ((1, 2), (1, 3), (2, 3), (1, 3)) and S the conjugacy class of ((), (1, 3), (), (1, 3)). The first circuit evaluates as the one-point set and the second as ∅.

5. A braided category of spans

The principal category we have been using in the earlier work on circuits and communicating-parallel algebras of processes is the category of spans of graphs Span(Graph). For sequential systems we have used the category of cospans of graphs Cospan(Graph). Already in the paper [8] the separable algebra structure on each object played a crucial role. The relation between another model of circuits, namely Mealy automata and Span(Graph) was discussed in [9]. One of the motivations of the present work is to produce an semantic algebra in which the twisting (or crossing) of wires is also (at least partially) expressible. To this end we introduce first a simple braided modification of the category of spans of sets Span(Set) called TSpan_{G}, depending on a group G and with a commutative Frobenius algebra. It is clear that a similar construction TSpan_{G}(C) could be made for a group object G in a category C with limits in the place of Set.

Again, there is a representation of Tangle (via a representation of TCirc) which takes a tangle to the span of colourings of the tangle (introduced by John Armstrong in [2]). Applied to knots, the set of colourings is one of the simplest invariants for distinguishing knots. As a first example it allows one to show that a trefoil is not an unknot. The extended notion of colourings of tangled circuit diagrams gives further aid in distinguishing circuit diagrams.

The dual of the category of groups Group^{op} has finite limits. Further the free group on one generator F is a group object in Group^{op}. The category TSpan_{F} (Group^{op}) is braided monoidal with F equipped with a commutative Frobenius structure. The induced representation

Tangle [figure] TSpan_{F} (Group^{op})

associates the cospan of groups introduced by John Armstrong in [1] to a tangle, and the knot group to a knot.

Strictly speaking, because we are interested in categories of spans, we always consider isomorphism classes of spans (in the usual sense of isomorphism of spans) but we will often describe them in terms of representatives.

5.1. Definition. Let G be a group. The objects of TSpan_{G} are the formal powers of G,

and an arrow from G^{m} to G^{n} is an isomorphism class of spans of sets, G^{m} [figure: δ_{0}] S [figure: δ_{1}] G^{n}, from the set G^{m} to the set G^{n} such that there exists a function G × S [figure] S of G written (g, s) ↦ gs yielding a bijection for each g ∈ G, and satisfying:

1) if δ_{0}(s) = (x_{1}, ..., x_{m}) and δ_{1}(s) = (y_{1}, ..., y_{n}) then δ_{0}(gs) = (x_{1}^{g}, ..., x_{m}^{g}) and δ_{1}(gs) = (y_{1}^{g}, ..., y_{m}^{g}) for all g in G,

2) if δ_{0}(s) = (x_{1}, ..., x_{m}) and δ_{1}(s) = (y_{1}, ..., y_{n}) then x_{1}...x_{m}(y_{1}...y_{n})^{−1} ∈ Z(G).

Composition and identities are composition and identity of spans.

It is straightforward that TSpan_{G} is a category. Like TRel_{G} it has the structure of a braided strict monoidal category. Note again that if G is abelian then 1) and 2) in the definition are satisfied.

5.2. Theorem. TSpan_{G} is braided strict monoidal with tensor defined by G^{m} ⊗ G^{n} = G^{m+n} and twist τ_{m,n} : G^{m} ⊗ G^{n} [figure] G^{n} ⊗ G^{m} is the span with δ_{0} = 1_{G^{m}⊗G^{n}} and

δ_{1}(x_{1}, ..., x_{m}, y_{1}, ..., y_{n}) = (y\overline{x} ; 1, ..., y\overline{x} ; n, x_{1}, ..., x_{m}).

Proof. This is similar to Theorem 4.3. As noted, it is easy to show that identities and composites of spans satisfying conditions 1) and 2) also satisfy 1) and 2), so TSpan_{G} is a category.

To see that ⊗ is a functor recall that product of spans defines a tensor functor on the category Span(Set). It remains to show that TSpan_{G} is closed under ⊗. Suppose R : G^{m} [figure] G^{t} and S : G^{n} [figure] G^{u}. If x = δ_{0}(r), y = δ_{1}(r) and z = δ_{0}(s), wδ_{1}(s), then for any g, x^{g} = δ_{0}(gr), y^{g} = δ_{1}(gr) and z^{g} = δ_{0}(s), w^{g} = δ_{1}(s), whence (xz)^{g} = δ_{0}(gr, gs), (yw)^{g} = δ_{1}(gr, gs), so taking g(r, s) to be (gr, gs) condition 1) is satisfied. For x, y, z, w as defined, condition 2) follows exactly as in Theorem 4.3.

The associative and unitary properties for ⊗ in TSpan_{G} are immediate from the same properties in Span(Set).

The properties B1 and B2 for τ are identical to the case of TRel_{G}.

As in the case of TRel_{G} the conditions 1) and 2) assure the naturality of τ.

5.3. A commutative Frobenius structure on G. As for TRel_{G} and using the same functions viewed as spans, G has the structure of a commutative Frobenius algebra in TSpan_{G}. Consequently:

5.4. Corollary. There is a unique braided strict monoidal functor

[figure: Tangle; TSpan; G]

taking the generating object to G and the structure maps of Tangle to the corresponding arrows in TSpan_{G}.

While G is separable in TRel_{G}, it is not so in TSpan_{G} because, unlike the relational composite, the span composite ∇Δ is not the identity.

5.5. Knot colourings. The description of TSpan_{G} makes it clear that there is a faithful monoidal functor

TSpan_{G} [figure] Span(Set).

Consider the following composite of monoidal functors we have described above:

colourings_{G} : Tangle [figure] TCirc [figure] TSpan_{G} [figure] Span(Set).

colourings_{G} takes the generating object X of Tangle to the underlying set of G, and takes ϵ_{X} to the span G×G ← {(x, y) : xy = 1} → I, η_{X} to I ← {(x, y) : xy = 1} → G×G and τ_{X} to (x, y) ← (x, y) ↦ (xyx^{−1}, x).

5.6. Theorem. (J. Armstrong [2]) If K is a knot then colourings_{G} is the set of colourings of K in the group G.

5.7. Remark. Because of the faithfulness of the functor TSpan_{G} [figure] Span(Set) the calculation of the set of colourings of a knot may be done equally in TSpan_{G} or Span(Set). The advantage of introducing TSpan_{G} as we do is that TSpan_{G} has the same structure as Tangle (braided monoidal with a tangle algebra) whereas Span(Set) does not.

5.8. Colourings of a trefoil. We will calculate the colourings of a trefoil knot in the dihedral group D_{3} to allow us to introduce notation and indicate relations with other work. One expression in Tangle for a trefoil is

(ϵ ⊗ ϵ)(1 ⊗ τ ⊗ 1)(1 ⊗ 1 ⊗ τ^{−1})(1 ⊗ τ ⊗ 1)(η ⊗ η).

It is convenient to represent the arrows in this expression as components as follows:

η  ϵ  τ  τ^{−1}

Then the trefoil may be displayed as the circuit diagram:

ηη  τ  τ^{−1}  τ  ϵϵ

The evaluation of the expression for the trefoil in Span(Set) is a limit of the diagram in Set formed as follows: for each wire in the diagram take the set G and for each component take the pair of arrows constituting its span of sets. See [19] for the relation between limits in C and expressions in Span(C). An element of this limit is a tuple of elements of G one for each wire, satisfying the conditions of the components. Each of the components η, ϵ, τ, τ^{−1} is actually a relation from its domain to codomain, that is a subset of products of groups given by equational conditions.

It is convenient to refine the pictures of the components to include the conditions as follows:

1=xy x y η  ^{xy=1} x y  ^{xy=zw}^{x=w}τ x y  z w  ^{xy=zw}^{y=z} τ^{−1} ϵ  x y  z w

Then a colouring of the trefoil is an element of the limit. Thus it is a tuple of elements of G on the wires satisfying the conditions of the components:

1=ab^{1=ej}  ^{ad=1}^{hk=1} a b  c  d e  f  g  h j  k^{b=f}^{be=cf}  ^{c=h}^{cg=dh}^{j=g}^{fj=gk}

Clearly a and c determine the other letters. When the group is D_{3} there are twelve colourings: one for each of (a, c) = ((), ()), ((1, 2, 3), (1, 2, 3)), ((1, 3, 2), (1, 3, 2)), ((1, 2), (1, 2)), ((1, 3), (1, 3)), ((2, 3), (2, 3)), ((1, 2), (1, 3)), ((1, 2), (2, 3)), ((1, 3), (1, 2)), ((1, 3), (2, 3)), ((2, 3), (1, 2)), ((2, 3), (1, 2)), whereas the unknot has only six colourings.

5.9. Knot groups. Consider now the free group on one generator F as a group object in the category Group^{op}. As we have mentioned, the construction TSpan works for any category with finite limits, not just Set, and hence there is a braided monoidal category TSpan_{F} (Group^{op}), and a corresponding representation

Gp : Tangle [figure] TSpan_{F} (Group^{op}) [figure] Span(Group^{op}) = Cospan(Group)

5.10. Theorem. (J. Armstrong [1]) If K is a knot then Gp(K) is the knot group of K.

5.11. The knot group of a trefoil. Limits in Group^{op} are colimits in Group. We can calculate the knot group from the same picture we used to calculate the knot colouring. In the diagram

1=ab^{1=ej}  ^{ad=1}^{hk=1} a b  c  d e  f  g  h j  k^{b=f}^{be=cf}  ^{c=h}^{cg=dh}^{j=g}^{fj=gk}

a letter represents the free group F on that generator, letters on a pair of wires represent the free group on two generators F × F in Group^{op}. The components are quotients of the free group on the boundary wires by the equations. The evaluation of the circuit in TSpan_{F} (Group^{op}) is a colimit, namely the free group on all the wires quotiented by all the equations.

In the case of the trefoil the knot group is

< a, b, c, d, e, f, g, h, j, k ; ab = 1, b = f, be = cf, c = h,
cg = dh, ad = 1, ej = 1, j = g, fj = gk, hk = 1 > .

Eliminating the variables b, d, e, f, g, h, j, k this presentation reduces to

< a, c ; aca = cac > .

6. Extending TRel_{G} and TSpan_{G}

We now describe an extension of TRel_{G} which depends not only on the group G but also on a set X, and we denote it TRel_{X,G}, and a similar extension of TSpan_{G} denoted TSpan_{X,G}. These will enable us to model circuits with state. The idea is that in TRel_{X,G} the object X × G is a single wire carrying data X.

6.1. Definition. The category TRel_{X,G} has objects (X × G)^{n}. An arrow of TRel_{X,G} is a relation S in Set from (X × G)^{m} to (Y × G)^{n} such that 1) if (x, h)S(y, k) then for any g ∈ G, (x, h^{g})S(y, k^{g}), and 2) if (x, h)S(y, k) then (\overline{h})(\overline{k})^{−1} ∈ Z(G). Composition and identities are defined as in Rel.

In TRel_{X,G} we define a tensor product by (X × G)^{m} ⊗ (X × G)^{n} = (X × G)^{m+n}.

6.2. Proposition. TRel_{X,G} is a braided strict monoidal category with

τ_{(XG)^{m}⊗(XG)^{n}} : (XG)^{m} ⊗ (XG)^{n} [figure] (XG)^{n} ⊗ (XG)^{m}

defined to be the relation

((x, g), (y, h)) ∼ ((y, h\overline{g}), (x, g)).

As in TRel_{G} and TSpan_{G}, a “single wire” X × G in TRel_{X,G} admits a commutative Frobenius algebra structure, namely the multiplication is the relation ((x, g), (x, h)) ∼ (x, gh); the comultiplication is (x, gh) ∼ ((x, g), (x, h)), the counit is (x, 1) ∼ ∗ and the unit is ∗ ∼ (x, 1).

6.3. Analogue resistive circuits in TRel_{ℝ,ℝ}. We begin by describing circuits of resistors which may be described in TRel_{X,G} where X = ℝ is the real numbers, and G = ℝ as a group under addition. It is useful to use a graphical notation similar to that of Section 5 to do calculations in TRel_{ℝ,ℝ}. For example, we draw a relation S : ℝ × ℝ [figure] X × G as:

i_{1}, v_{1}  i_{2}, v_{2} (i_{1}, v_{1})S(i_{2}, v_{2})

With this notation, where i denotes current and v denotes voltage, a resistor of resistance r is:

i_{1}, v_{1}  i_{2}, v_{2} i_{1} = i_{2} v_{2} = v_{1} − ir

The multiplication and comultiplication, which we sometimes draw as forks, and which embody Kirchhoff’s law of currents are:

i_{1}, v_{1}  i_{2}, v_{2} i_{3}, v_{3}  i_{1}, v_{1} i_{2}, v_{2}  i_{3}, v_{3} i_{1} = i_{2} + i_{3} v_{1} = v_{2} = v_{3}  i_{1} + i_{2} = i_{3} v_{1} = v_{2} = v_{3}

Using the operations of TRel_{ℝ,ℝ} one can now evaluate a network of resistors. For example the circuit with two parallel resistors with resistances r_{1}, r_{2} respectively

\begin{matrix}r_{1} \\ r_{2} \end{matrix}

evaluates as:

i_{1}, v_{1}  i_{2}, v_{2} i_{1} = i_{2} v_{2} − v_{1} = i_{1}(\frac{r_{1}r_{2}}{r_{1}+r_{2}} )

6.4. Definition. The category TSpan_{X,G} has objects (X×G)^{n}. An arrow of TSpan_{X,G}

is an isomorphism class of spans S in Set: (X × G)^{m} [figure: δ_{0}] S [figure: δ_{1}] (Y × G)^{n} such that such that there exist a function G × S [figure] S of G on S written (g, s) ↦ gs yielding a bijection for each g ∈ G, and satisfying:

1) if δ_{0}(s) = (x_{1}, h_{1}, ..., x_{m}, h_{m}) and δ_{1}(s) = (y_{1}, k_{1}, ..., y_{n}, k_{n}) then δ_{0}(gs) = (x_{1}, h_{1}^{g}, ..., x_{m}, h_{m}^{g}) and δ_{1}(gs) = (y_{1}, k_{1}^{g}, ..., y_{n}, k_{n}^{g}) for all g in G,

2) if δ_{0}(s) = (x_{1}, h_{1}, ..., x_{m}, h_{m}) and δ_{1}(s) = (y_{1}, k_{1}, ...y_{n}, k_{n}) then h_{1}...h_{m}(k_{1}..., k_{n})^{−1} ∈ Z(G).

Composition and identities and tensor are defined as in Span(Set). The braiding and Frobenius structure are as in TRel_{X,G}.

It is clear that this definition may be made in any category C with finite limits to give a category TSpan_{X,G}(C).

6.5. RLC circuits in TSpan_{X,G}(Graph). This example comes from the paper [9] where it is discussed in detail. However the Frobenius algebra structure was not noticed in that paper. The category is analogous to TSpan_{G}(Graph) where the group G is the real numbers under addition. The Frobenius algebra structure arises from the Kirchhoff law for currents. Since the group is abelian there is no information about the tangling of wires. We describe, as an example, circuits composed of resistors, capacitors and inductors.

The algebra of RLC circuits we will describe was introduced in [9]. We will give a brief recapitulation without full details.

We need to say something first about the somewhat unusual interpretation of a graph in this setting. If the graph consists of the two (domain and codomain) functions ϕ : X [figure] Y and ψ : X [figure] Y we will interpret this as the formal differential equation ϕ′ = ψ. For further explanation of this interpretation see [9]. In the examples we describe the interpretation will have a clear meaning. There is a notion of behaviour for such a system, namely a function x : ℝ [figure] X such that ϕ′(x(t)) = ψ(x(t)) (only meaningful with smoothness assumptions).

We will now consider TSpan_{X,G}(Graph) where both X and G are the graph with one object, and set of arrows ℝ; we will identify both X and G with the set ℝ, the group structure being addition.

Again it is useful to use a graphical notation similar to that of Section 5 to do calculations in TSpan_{ℝ,ℝ}(Graph). For example, we draw the spans corresponding to the constants τ, Δ, ∇, η, ϵ, and the resistors of the algebra (in which all of the graphs have one object) exactly as in Section 6.3.

The graph of a capacitor with capacitance c is the pair of functions ϕ, ψ : ℝ^{3} [figure] ℝ defined by ϕ(i, v, q) = q and ψ(i, v, q) = i; the interpretation is that a capacitor has state i, v, and also state q, the charge of the capacitor, and that q′ = i. The boundary conditions (the morphism of the span) are on the left v_{1} = v, and i_{1} = i, and on the right v_{2} = v − \frac{q}{c} and i_{2} = i. Hence we draw the capacitor as follows:

q′ = i i_{1}, v_{1}  i_{2}, v_{2} i_{1} = i = i_{2}, v_{1} = v v_{2} − v_{1} = \frac{q}{c}

Similarly an inductor with inductance l has an extra variable of state p with graph ℝ^{3} [figure] ℝ, and pictures:

i′ = p i_{1}, v_{1}  i_{2}, v_{2} i_{1} = i = i_{2}, v_{1} = v v_{2} − v_{1} = lp

Using the operations of TSpan_{ℝ,ℝ}(Graph) one can now evaluate a network of resistors, capacitors and inductors. For example the circuit of an inductance and a capacitance

\begin{matrix}l \\ c \end{matrix}

evaluates as

i, v_{1}, v_{2}, p, q
(−i)′ = p
q′ = i
\frac{q}{c} = v_{1} − v_{2} = lp

A behaviour consists of five functions from ℝ to ℝ, namely i(t), v_{1}(t), v_{2}(t), q(t), p(t) such that i′ = −p, q′ = i and \frac{q}{c} = v_{2} − v_{1} = lp.

References

[1] J, Armstrong, The extension of knot groups to tangles, arXiv:0509.665

[2] J. Armstrong, Categorifying coloring numbers, arXiv:0803.1642

[3] A. Carboni, R.F.C. Walters, Cartesian bicategories I, Journal of Pure and Applied Algebra, 49, 11–32, 1987.

[4] L. de Francesco Albasini, N. Sabadini, R.F.C. Walters, Systems with discrete geometry, ART 2008, Analysing Reduction Systems using Transition Systems, 122–131, Forum, Udine, 2008.

[5] L. de Francesco Albasini, N. Sabadini, R.F.C. Walters, Cospans and spans of graphs: a categorical algebra for the sequential and parallel composition of discrete systems, arXiv:0909.4136

[6] P. Freyd and D. Yetter, Braided compact monoidal categories with applications to low dimensional topology, Adv. Math. 77, 156–182, 1989.

[7] A. Joyal, R.H. Street, Braided monoidal categories, Adv. Math., 102, 20–78, 1993.

[8] P. Katis, N. Sabadini, R.F.C. Walters, Span(Graph): A categorical algebra of transition systems, Proc. AMAST’97, LNCS 1349, 307–321, Springer Verlag, 1997.

[9] P. Katis, N. Sabadini, R.F.C. Walters, On the algebra of systems with feedback and boundary, Rendiconti del Circolo Matematico di Palermo Serie II, Suppl. 63: 123–156, 2000.

[10] P. Katis, N. Sabadini, R.F.C. Walters, A formalisation of the IWIM Model, in: Proc. COORDINATION 2000, (Eds.) A. Porto, G.-C. Roman, LNCS 1906, 267–283, Springer Verlag, 2000.

[11] P. Katis, N. Sabadini, R.F.C. Walters, Feedback, trace and fixed-point semantics, Theoret. Informatics Appl. 36, 181–194, 2002.

[12] G. M. Kelly and M. L. Laplaza. Coherence for compact closed categories. Jour- nal of Pure and Applied Algebra 19, 193–213, 1980.

[13] J. Kock, Frobenius algebras and 2D topological Quantum Field Theories, Cambridge University Press, 2004.

[14] F. W. Lawvere, Ordinal sums and equational doctrines, Springer Lecture Notes in Mathematics, 80, 141–155, 1967.

[15] D. Maglia, N. Sabadini, R.F.C. Walters, Blocked-braid groups, in preparation.

[16] R. Penrose, Applications of negative dimensional tensors , in Combinatorial Mathematics and its Applications, Academic Press, 1971.

[17] R. Rosebrugh, N. Sabadini, R.F.C. Walters, Minimization and minimal realization in Span(Graph), Mathematical Structures in Computer Science, 14, 685–714, 2004.

[18] R. Rosebrugh, N. Sabadini, and R.F.C. Walters, Generic commutative separable algebras and cospans of graphs, Theory and Applications of Categories, 15, 164–177, 2005.

[19] R. Rosebrugh, N. Sabadini, R.F.C. Walters, Calculating colimits compositionally, Concurrency, Graphs and Models, Essays dedicated to Ugo Montanari on the occasion of his 65th birthday, LNCS 5065, 581–592, 2008.

[20] P. Selinger, A survey of graphical languages for monoidal categories, in New Structures for Physics, Springer Lecture Notes in Physics 813, 289–355, 2011.

[21] D. Yetter, Functorial Knot Theory: Categories of Tangles, Coherence, Categorical Deformations, and Topological Invariants, World Scientific, 2001.

Department of Mathematics and Computer Science Mount Allison University Sackville, N. B. E4L 1E6 Canada

Dipartimento di Scienza e Alta Tecnologia Università dell’ Insubria via Carloni, 78, Como, Italy

Dipartimento di Scienza e Alta Tecnologia Università dell’ Insubria via Carloni, 78, Como, Italy

Email: rrosebrugh@mta.ca
      nicoletta.sabadini@uninsubria.it
      robert.walters@uninsubria.it

This article may be accessed at http://www.tac.mta.ca/tac/ or by anonymous ftp at

ftp://ftp.tac.mta.ca/pub/tac/html/volumes/26/27/26-27.{dvi,ps,pdf}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods. Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication. Full text of the journal is freely available in .dvi, Postscript and PDF from the journal’s server at http://www.tac.mta.ca/tac/ and by ftp. It is archived electronically and in printed paper format.

Subscription information Individual subscribers receive abstracts of articles by e-mail as they are published. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors The typesetting language of the journal is TEX, and use of L^{A}TEX2e is strongly encouraged. Articles should be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

Managing editor Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor Michael Barr, McGill University: barr@math.mcgill.ca

Assistant TEX editor Gavin Seal, Ecole Polytechnique Fédérale de Lausanne:

gavin seal@fastmail.fm

Transmitting editors

Clemens Berger, Université de Nice-Sophia Antipolis, cberger@math.unice.fr Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: ronnie.profbrown(at)btinternet.com

Valeria de Paiva: valeria.depaiva@gmail.com

Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Kathryn Hess, Ecole Polytechnique Fédérale de Lausanne : kathryn.hess@epfl.ch Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, Macquarie University: steve.lack@mq.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Tom Leinster, University of Edinburgh, Tom.Leinster@ed.ac.uk Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Giuseppe Rosolini, Università di Genova: rosolini@disi.unige.it Alex Simpson, University of Edinburgh: Alex.Simpson@ed.ac.uk James Stasheff, University of North Carolina: jds@math.upenn.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca