Categorical interpretation of disjoint cycle notation for tracing permutations

Question

For a natural number $n\in\mathbb{N}$, let $\underline{n}$ denote the finite set $$\underline{n}:=\{1,2,\ldots,n\}.$$ A permutation $\sigma\in Aut(\underline{n})$ can be uniquely written (up to order) as a product of disjoint cycles. To set an example we'll use $n^~_0=8$ and $$\sigma_0^~=(1247)(358)(6).$$

I'm looking for a categorical interpretation of this notion of maximal cycle decomposition. A bit more precisely, let $\mathcal{Bij}$ denote the symmetric monoidal category of finite ordinals $\underline{n}$ as objects, automorphisms as morphisms, and disjoint union as the monoidal structure. That is, $\mathcal{Bij}$ is a skeleton of $FinSet$. I'm looking for to understand maximal cycle decomposition category-theoretically in terms of $\mathcal{Bij}$.

My motivation comes from the fact that there is a trace on $\mathcal{Bij}$ whose definition is quite simply expressed in terms of the "disjoint cycle notation". Namely, suppose given a bijection $\sigma:X\sqcup U\to Y\sqcup U$ for which you want the trace $Tr^U_{X,Y}(\sigma):X\to Y$. To obtain it, simply write $\sigma$ in maximal cycle notation, and remove every element of $U$ you see.

The above formula is not precisely stated, which is exactly the problem---how can I state this formula precisely?---but it is quite easy to think about. An example will help.

Let $X=Y=\underline{5}$ and $U=\underline{3}$, and let $\sigma_0^~: X\sqcup U\to Y\sqcup U$ be $(1247)(358)(6)$ as above, where the elements of $X$ and $Y$ are denoted $1,2,3,4,5$ and the elements of $U$ are denoted $6,7,8$. Then the trace is given by $$Tr^U_{X,Y}(\sigma^~_0)=(124)(35).$$ We simply removed the elements of $U$ from the cycle notation and dropped of the now-empty cycle where $(6)$ was. (There is another traced monoidal category $\mathcal{Bij}'$ with the same objects, but which keeps track of the number of empty cycles.)

Category theoretically, we are just performing a trace. But this trick with disjoint cycle notation appears to be the simplest way to write the operation. How do we think about this strange but simple description?

Answer 1

I'm not completely clear on what answer would be considered satisfactory, but here's one categorical way to think about tracing in $\mathbf{Bij}$.

The morphisms of the symmetric monoidal category with duals obtained by applying the Joyal-Street-Verity construction to $\mathbf{Bij}$ can be pictured in terms of string diagrams that are essentially 1-cobordisms, i.e, curves bounded by compact 0-manifolds that are built from string diagrams for permutations and from cups and caps (which are counits and units of dual pairs) by applying the usual composition and juxtaposition operations. Now cobordisms generally are certain types of cospans in the category of manifolds. Thus, what we can do is consider $\mathbf{Bij}$ (or more generally $\mathbf{Set}$) as embedded in the bicategory of cospans between sets, where a bijection or function $\sigma: A \to B$ is mapped to the cospan

$$A \stackrel{\sigma}{\to} B \stackrel{1_B}{\leftarrow} B.$$

Composition of cospans (i.e., of 1-cells)

$$(A \stackrel{f}{\to} B \stackrel{g}{\leftarrow} C) \; ; \; (C \stackrel{h}{\to} D \stackrel{k}{\leftarrow} E)$$

is obtained by taking the pushout of $g$ and $h$, and composing $f$ and $k$ with the pushout coprojections. The disjoint sum induces an obvious tensor product on cospans.

The category obtained by taking isomorphism classes of 1-cells is a symmetric monoidal category $\mathbf{Cospan}$ with duals, in which each object is dual to itself. This works in a manner dual to the situation for $\mathbf{Span}$, where the unit and counit are given by "equality predicates"; thus for each object $U$, the unit and counit of $U \dashv U$ are given by coequality cospans

$$\eta_U = (0 \to U \stackrel{\nabla_U}{\leftarrow} U + U), \qquad \epsilon_U = (U + U \stackrel{\nabla_U}{\to} U \leftarrow 0).$$

Thus, given a bijection $\sigma: A + U \to B + U$, the tracing $Tr_{A, B}^U(\sigma)$, given by a composite of cospans

$$A \cong A + 0 \stackrel{1_A + \eta_U}{\to} A + U + U \stackrel{\sigma + U}{\to} B + U + U \stackrel{1_B + \epsilon_U}{\to} B +0 \cong B,$$

can be read off by taking a pushout in $\mathbf{Set}$ of the diagram

$$A + U \stackrel{1_A + \nabla}{\leftarrow} (A + U + U \stackrel{\sigma + U}{\to} B + U + U \stackrel{1_B + \nabla_U}{\to} B + U) \qquad (1)$$

and then composing the pushout coprojections with the canonical inclusions $A \hookrightarrow A + U$, $B \hookrightarrow B + U$.

This gives a precise categorical description of the trace operation in terms of pushouts in $\mathbf{Set}$, but: it's the trace operation that pertains to the traced monoidal category denoted $\mathbf{Bij}'$ in the original post (where one keeps track of loops formed in the tracing process). If one wants to ignore loops that are formed by composing cospans, i.e., work with the traced monoidal category $\mathbf{Bij}$, one ought to work with co-relations instead of cospans.

By definition, a co-relation is a cospan $A \stackrel{f}{\to} C \stackrel{g}{\leftarrow} B$ such that the induced map $(f, g): A + B \to C$ is epic. In other words, a co-relation is a relation in the category $\mathbf{Set}^{op}$. One should pause to note that the power set functor $P: \mathbf{Set}^{op} \to \mathbf{Set}$ is monadic, and since a monadic category over $\mathbf{Set}$ is Barr exact and in particular a regular category, the usual calculus of relations goes through. In particular, to compose co-relations in $\mathbf{Set}$, one composes them as cospans but then one applies the epi-mono factorization to the composition cospan $(f, g): A + B \to C$; the epi part $q: A + B \to C'$ gives the composition co-relation. All the relevant structural features one had from $\mathbf{Cospan}$ carry over: $\mathbf{Corel}$ is a symmetric monoidal category in which each object is dual to itself, using the same formulas for the unit and counit of $U \dashv U$.

So, in summary, the result of the pushout (1) above induces a cospan from $A$ to $B$, and after applying the appropriate epi-mono factorization to get a co-relation, one can check that the result is a bijection from $A$ to $B$ (i.e., a cospan obtained by applying the inclusion functor $\mathbf{Bij} \hookrightarrow \mathbf{Corel}$ to a suitable bijection). This is the trace in $\mathbf{Bij}$.

It's not hard to see what is really going on. Tracing is basically the introduction of a feedback loop where outputs of $\sigma$ in $U$ are fed back in as inputs in $U$ living in $A + U$, and iterating through cycles until you exit $U$. That's exactly what the string diagram picture suggests (with the proviso that we are dealing with co-relation composition, which elides over free-floating loops where one never exits $U$). The meaning in terms of the cycle decomposition is hopefully clear. For instance, to take the example of the OP, we have in one of the cycles of $\sigma$ a path $5 \to 8$; this output $8 \in U$ is reinterpreted as an input where the next step in the cycle is $8 \to 3$, at which point we have exited out of $U$.