<figure><img src="image_1.png" /></figure>

HAL
open science

# A coherence theorem for pseudonatural transformations

Maxime Lucas

► To cite this version:

Maxime Lucas. A coherence theorem for pseudonatural transformations. Journal of Pure and Applied Algebra, 2017, 221 (5), pp.1146-1217. 10.1016/j.jpaa.2016.09.005. hal-01191867v2

HAL Id: hal-01191867

https://hal.science/hal-01191867v2

Submitted on 31 Aug 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A coherence theorem for pseudonatural transformations

Maxime LUCAS*

## Abstract

We prove coherence theorems for bicategories, pseudofunctors and pseudonatural transformations. These theorems boil down to proving the coherence of some free (4, 2)-categories. In the case of bicategories and pseudofunctors, existing rewriting techniques based on Squier's Theorem allow us to conclude. In the case of pseudonatural transformations this approach only proves the coherence of part of the structure, and we use a new rewriting result to conclude. To this end, we introduce the notions of white-categories and partial coherence.

## Contents

<table><tr><td>1</td><td>Higher-dimensional rewriting</td><td>8</td></tr><tr><td>1.1</td><td>Polygraphs</td><td>8</td></tr><tr><td>1.2</td><td>Termination</td><td>9</td></tr><tr><td>1.3</td><td>Branchings and Confluence</td><td>10</td></tr><tr><td>1.4</td><td>Coherence</td><td>11</td></tr><tr><td>2</td><td>Partial coherence and transformation of polygraphs</td><td>13</td></tr><tr><td>2.1</td><td>White-categories and White-polygraphs</td><td>13</td></tr><tr><td>2.2</td><td>Partial coherence in pointed (4, 3)-white-categories</td><td>16</td></tr><tr><td>2.3</td><td>Injective functors between white-categories</td><td>18</td></tr><tr><td>3</td><td>Application to the coherence of pseudonatural transformations</td><td>24</td></tr><tr><td>3.1</td><td>Coherence for bicategories</td><td>24</td></tr><tr><td>3.2</td><td>Coherence for pseudofunctors</td><td>28</td></tr><tr><td>3.3</td><td>Coherence for pseudonatural transformations</td><td>31</td></tr><tr><td>4</td><td>Proof of the coherence for pseudonatural transformations</td><td>36</td></tr><tr><td>4.1</td><td>A convergent sub-polygraph of PNTrans[f, g]</td><td>36</td></tr><tr><td>4.2</td><td>A sub-polygraph of PNTrans[f, g] satisfying 2-Squier condition of depth 2</td><td>37</td></tr><tr><td>4.3</td><td>Adjunction of the units 2-cells</td><td>41</td></tr><tr><td>4.4</td><td>Adjunction of the units 3-cells</td><td>43</td></tr><tr><td>5</td><td>Transformation of a (4, 2)-polygraph into a (4, 3)-white-polygraph</td><td>48</td></tr><tr><td>5.1</td><td>Weakening of the exchange law</td><td>49</td></tr><tr><td>5.2</td><td>Weakening of the invertibility of 3-cells</td><td>51</td></tr><tr><td>5.3</td><td>Adjunction of formal inverses to 2-cells</td><td>52</td></tr><tr><td>5.4</td><td>Adjunction of connections between 2-cells</td><td>53</td></tr><tr><td>5.5</td><td>Reversing the presentation of a (4, 3)-white-category</td><td>57</td></tr><tr><td>6</td><td>Proof of Theorem 1.4.9</td><td>61</td></tr><tr><td>6.1</td><td>Local coherence</td><td>61</td></tr><tr><td>6.2</td><td>Orderings on the cells of F<sup>w</sup></td><td>63</td></tr><tr><td>6.3</td><td>Partial coherence of F<sup>w</sup>(3)</td><td>66</td></tr></table>

<footnote>*Univ Paris Diderot, Sorbonne Paris Cité, IRIF, UMR 8243 CNRS, PiR2, INRIA Paris-Rocquencourt, F-75205 Paris, France - maxime.lucas@pps.univ-paris-diderot.fr</footnote>
# Introduction

## An overview of coherence theorems

A mathematical structure, such as the notion of monoid or algebra, is often defined in terms of some data satisfying relations. In the case of monoids, the data is a set and a binary application, and the relations are the associativity and the unit axioms. In category theory, one often considers relations that only hold *up to isomorphism*. One of the simplest example of such a structure is that of monoidal categories, in which the product is not associative, but instead there exist isomorphisms $\alpha_{A,B,C} : (A \otimes B) \otimes C \to A \otimes (B \otimes C)$. This additional data must also satisfy some relation, known as Mac-Lane's pentagon:

<figure><img src="image_3.png" /></figure>

The intended purpose of this relation is that, between any two bracketings of $A_1 \otimes A_2 \otimes \dots \otimes A_{n-1} \otimes A_n$, there exists a unique isomorphism constructed from the isomorphisms $\alpha_{A,B,C}$. This statement was made precise and proved by Mac Lane in the case of monoidal categories [12]. In general a coherence theorem contains a description of a certain class of diagrams that are to commute. Coherence theorems exist for various other structures, e.g. bicategories [13], or V-natural transformations for a symmetric monoidal closed category V [10].

Coherence results are often a consequence of (arguably more essential [9]) strictification theorems. A strictification theorem states that a “weak” structure is equivalent to a “strict” (or at least “stricter”) one. For example any bicategory is biequivalent to a 2-category, and the same is true for pseudofunctors (this is a consequence of this general strictification result [15]). It does not hold however for pseudonatural transformations.

## Free categories and rewriting

Coherence theorems can also be proven through rewriting techniques. The link between coherence and rewriting goes back to Squier's homotopical Theorem [16], and has since been expanded upon [6]. Squier's theory is constructive, which means that the coherence conditions can be calculated from the relations, in a potentially automatic way. It can also be expanded to higher dimensions [8], a feature that may prove useful when studying weaker structures. In [7], the authors use Squier's theory to prove the coherence of monoidal categories. Let us give an outline of the proof in the case of categories equipped with an associative tensor product.

Polygraphs are presentations for higher-dimensional categories and were introduced by Burroni [3], and by Street under the name of computads [17] [18]. In this paper we use Burroni's terminology. For example, a 1-polygraph is given by a graph $G$, and the free 1-category it generates is the category of paths on $G$. If $\Sigma$ is an $n$-polygraph, we denote by $\Sigma^*$ the free $n$-category generated by $\Sigma$.

An $(n,p)$-category is a category where all $k$-cells are invertible, for $k > p$. In particular, $(n,0)$-categories are commonly called $n$-groupoids, and $(n,n)$-categories are just $n$-categories. There is a corresponding notion of $(n,p)$-polygraph. If $\Sigma$ is an $(n,p)$-polygraph, we denote by $\Sigma^{*(p)}$ the free $(n,p)$-category generated by $\Sigma$.

The structure of category equipped with an associative tensor product is encoded into a 4-polygraph Assoc, which generates a free (4, 2)-category Assoc$^{*(2)}$. The 4-polygraph Assoc contains one generating 2-cell $\mathcal{V}$ coding for product, one generating 3-cell $\mathcal{V}^3$ coding for associativity and one
generating 4-cell $\mathbb{A}$ corresponding to Mac Lane's pentagon:

<figure><img src="image_4.png" /></figure>

The coherence result for categories equipped with an associative product is now reduced to showing that, between every parallel 3-cells $A, B$ in $\mathbf{Assoc}^{*(2)}$, there exists a 4-cell $\alpha : A \overset{\alpha}{\rightleftharpoons} B$ in $\mathbf{Assoc}^{*(2)}$. A 4-category satisfying this property is said to be 3-coherent.

Let us denote by $\mathbf{Assoc}^*$ the free 4-category generated by $\mathbf{Assoc}$. We have the following properties:

* Starting from any given 2-cell in $\mathbf{Assoc}^*$, it is impossible to form an infinite sequence of non-identity 3-cells. This property is known as 3-termination.

* If $A$ and $B$ are two 3-cells in $\mathbf{Assoc}^*$ with the same source, there exists 3-cells $A'$ and $B'$ in $\mathbf{Assoc}^*$ such that the composites $A \star_2 A'$ and $B \star_2 B'$ are well-defined and have the same target. This property is known as 3-confluence.

The conjunction of these two properties make $\mathbf{Assoc}$ into a 3-convergent 4-polygraph.

## Squier's theory and coherence

A generating 3-cell composed with some lower dimensional context is called a *rewriting step* of $\mathbf{Assoc}$. A local branching in $\mathbf{Assoc}$ is a pair of rewriting step of same source. Local branching are ordered by adjunction of context, that is a branching $(f,g)$ is smaller than a branching $(u \star_i f \star_i v, u \star_i g \star_i v)$ for any 2-cells $u$ and $v$ and $i = 0, 1$. There are three types of local branchings:

* A branching of the form $(f, f)$ is called *aspherical*.

* A branching of the form $(f \star_i s(g), s(f) \star_i g)$ for $i = 0$ or $1$ is called a *Peiffer branching*.

* Otherwise, $(f,g)$ is called an *overlapping branching*.

Overlapping branchings that are also minimal are called *critical branchings*.

There is exactly one critical branching in $\mathbf{Assoc}$, of source $\mathbb{A}$. Note that the critical pair appears as the source of the generating 4-cell of $\mathbf{Assoc}$. In particular there is a one-to-one correspondence between 4-cells and critical pairs. A 3-convergent 4-polygraph that satisfies this property is said to satisfy the 3-Squier condition.

Proposition 4.3.4 in [6] states that a 4-polygraph satisfying the 3-Squier condition is 3-coherent (and more generally, that any $(n+1)$-polygraph satisfying the $n$-Squier condition is $n$-coherent). In particular, the 4-polygraph $\mathbf{Assoc}$ satisfies the 3-Squier condition, so it is 3-coherent.

In Section 3, we exhibit, for any sets $C$ and $D$ and any application $f: C \to D$ two 4-polygraphs $\mathbf{BiCat}[C]$ and $\mathbf{PFonct}[f]$ presenting respectively the structures of bicategory and pseudofunctor. Applying the reasoning we just presented, we prove our first two results:

**Theorem 3.1.6 (Coherence for bicategories).** Let $C$ be a set.

The 4-polygraph $\mathbf{BiCat}[C]$ is 3-convergent and the free (4,2)-category $\mathbf{BiCat}[C]^{*(2)}$ is 3-coherent.

**Theorem 3.2.7 (Coherence for pseudofunctors).** Let $C$ and $D$ be sets, and $f: C \to D$ an application.

The 4-polygraph $\mathbf{PFonct}[f]$ is 3-convergent and the free (4,2)-category $\mathbf{PFonct}[f]^{*(2)}$ is 3-coherent.
However, this approach fails to work in the case of pseudonatural transformations, because the (4, 2)-polygraph PNTrans[f, g] (where f and g are applications C → D) encoding the structure of pseudonatural transformation is not 3-confluent.

## The 2-Squier condition of depth 2

In order to circumvent this difficulty, we introduce the notion of 2-Squier condition of depth 2. We say that a (4, 2)-polygraph Σ satisfies the 2-Squier condition of depth 2 if it satisfies the 2-Squier condition, and if the 4-cells of Σ correspond to the critical triples induced by the 2-cells (with a prescribed shape).

For example, the 4-polygraph Assoc satisfies the 2-Squier condition of depth 2: its underlying 2-polygraph is both 2-terminating and 2-confluent. Moreover the only critical pair corresponds to the associativity 3-cell. Finally, Mac Lane's pentagon can be written as follows, which shows that it corresponds to the only critical triple:

<figure><img src="image_5.png" /></figure>

We prove the following result about (4, 2)-polygraph satisfying the 2-Squier condition of depth 2:

**Theorem 1.4.9.** Let Σ be a (4, 2)-polygraph satisfying the 2-Squier condition of depth 2.

For every parallel 3-cells A, B ∈ Σ₃⁽²⁾ whose 1-target is a normal form, there exists a 4-cell α : A ⇝ B in the free (4, 2)-category Σ₄⁽²⁾.

Note in particular that the 2-Squier condition of depth 2 does not imply the 3-coherence of the (4, 2)-category generated by the polygraph, but only a partial coherence, "above the normal forms". For example in the case of Assoc, the only normal form is the 1-cell |. So Theorem 1.4.9 only expresses the coherence of the 3-cells of Assoc⁽²⁾ whose 1-target is |. On the other hand, Squier's Theorem as extended in [6] concerns all the 3-cells of Assoc⁽²⁾, regardless of their 1-target.

The (4, 2)-polygraph PNTrans[f, g] does not satisfy the 2-Squier condition. However, we identify in Section 4.2 a sub-(4, 2)-polygraph PNTrans⁽⁺⁾[f, g] of PNTrans[f, g] that does. By Theorem 1.4.9, we get a partial coherence result in PNTrans⁽⁺⁾[f, g]⁽²⁾. The rest of Section 4 is spent extending this partial coherence result to the rest of PNTrans[f, g]⁽²⁾. To do so, we define a weight application from PNTrans[f, g]⁽²⁾ to N to keep track of the condition on the 1-targets of the 3-cells considered. We thereby prove the following result:

**Theorem 3.3.8 (Coherence for pseudonatural transformations).** Let C and D be sets, and f, g : C → D applications.

Let A, B ∈ PNTrans[f, g]₃⁽²⁾ be two parallel 3-cells whose 1-target is of weight 1.

There is a 4-cell α : A ⇝ B ∈ PNTrans[f, g]₄⁽²⁾.

## White-categories and partial coherence

Let j < k < n be integers. In an n-category C, one can define the j-composition of (k + 1)-cells A and B using the k-composition and whiskering by setting:

$$A \star_j B := (A \star_j s_k(B)) \star_k (t_k(A) \star_j B) = (s_k(A) \star_j B) \star_k (A \star_j t_k(B)).$$

This is made possible by the exchange axiom between $\star_k$ and $\star_j$. An n-white-category is an n-category in which the exchange axioms between $\star_k$ and $\star_0$ need not hold (even up to isomorphism) for any $k > 0$.
As a result, 0-composition is not defined for $k$-cells, for $k > 1$. The notion of 2-white-category coincides with the notion of sesquicategory (see [19]).

Most concepts from rewriting have a straightforward transcription in the setting of white-categories. In particular in Section 2.1, we define the notions of $(n, k)$-white-category and $(n, k)$-white-polygraph. We also give an explicit description of the free $(n, k)$-white-category $\Sigma^{\mathbf{w}(k)}$ generated by an $(n, k)$-white-polygraph $\Sigma$.

In this setting, we give a precise definition to the notion of partial coherence. Let $\mathcal{C}$ be a (4,3)-white-category and $\mathcal{S}$ be a set of distinguished 2-cells of $\mathcal{C}$. We call such a pair a *pointed (4, 3)-white-category*. We say that $\mathcal{C}$ is $\mathcal{S}$-coherent if for any parallel 2-cells $f, g \in \mathcal{S}$ and any 3-cells $A, B : f \Rightarrow g \in \mathcal{C}$, there exists a 4-cell $\alpha : A \twoheadrightarrow B \in \mathcal{C}$. In particular any (4,3)-white category is $\emptyset$-coherent, and a (4,3)-white category $\mathcal{C}$ is $\mathcal{C}_2$-coherent if and only if it is 3-coherent (where $\mathcal{C}_2$ is the set of all the 2-cells of $\mathcal{C}$). Theorem 1.4.9 amounts to showing that the free (4,2)-category $\Sigma^{(2)}$ is $\mathcal{S}_{\Sigma}$-coherent, where $\mathcal{S}_{\Sigma}$ is the set of all 2-cells whose target is a normal form.

Finally, we give a way to modify partially coherent categories while retaining information about the partial coherence. Let $(\mathcal{C}, \mathcal{S})$ and $(\mathcal{C}', \mathcal{S}')$ be pointed (4,3)-white-categories. We define a relation of *strength* between pointed (4,3)-white-categories. We show that if $(\mathcal{C}, \mathcal{S})$ is stronger than $(\mathcal{C}', \mathcal{S}')$, then the $\mathcal{S}$-coherence of $\mathcal{C}$ implies the $\mathcal{S}'$-coherence of $\mathcal{C}'$.

## Sketch of the proof of Theorem 1.4.9

We now give an overview of the proof of Theorem 1.4.9. Let us fix a (4,2)-polygraph $\mathcal{A}$ satisfying the 2-Squier condition of depth 2, and denote by $S_{\mathcal{A}}$ the set of 2-cells whose target is a normal form. In particular, $(\mathcal{A}^{*(2)}, S_{\mathcal{A}})$ is a pointed (4,3)-white-category. The first half of the proof (Section 5) consists in applying to $(\mathcal{A}^{*(2)}, S_{\mathcal{A}})$ a series of transformations. At each step, we verify that the new pointed (4,3)-white-category we obtain is stronger than the previous one. In the end, we get a pointed (4,3)-white-category $(\mathcal{F}^{\mathbf{w}}(3), S_{\mathcal{E}})$, where $\mathcal{F}$ is a 4-white-polygraph. In dimension 2, the 2-cells of $\mathcal{F}$ consists of the union of the 2-cells of $\mathcal{A}$ together with their formal inverses. We denote by $\bar{f}$ the formal inverse of a 2-cell $f \in \mathcal{A}^*$. Let $\mathcal{F}_3$ be the set of 3-cells of $\mathcal{F}$. It contains 3-cells $C_{f,g}$ for any minimal local branching $(f,g)$, and cells $\eta_f$ for any 2-cell $f \in \mathcal{A}$ of the following shape:

<figure><img src="image_6.png" /></figure>

The purpose of this transformation is that in $\mathcal{F}^{\mathbf{w}}(3)$, for any 2-cells $f, g \in S_{\mathcal{E}}$, 3-cells of the form $f \Rightarrow g$ (and 4-cells between them) are in one-to-one correspondence with 3-cells of the form $\bar{g} \star_1 f \Rightarrow 1_{\hat{u}}$ (and 4-cells between them), where $\hat{u}$ is the common target of $f$ and $g$. More generally we study cells of the form $h \Rightarrow 1_{\hat{u}}$, and 4-cells between them.

We start by studying the rewriting system induced by the 3-cells. Note that the 4-white-polygraph $\mathcal{F}$ is not 3-terminating, so we cannot use a Squier-like Theorem to conclude. However, let $\mathbb{N}[\mathcal{A}_1^*]$ be the free monoid on $\mathcal{A}_1^*$, the set of 1-cells of $\mathcal{A}^*$. There is a well-founded ordering on $\mathcal{A}_1^*$ induced by the fact that $\mathcal{A}$ is 2-terminating. This order induces a well-founded ordering on $\mathbb{N}[\mathcal{A}_1^*]$ called the *multiset order*. We define an application $\mathbf{p} : \mathcal{F}_2^{\mathbf{w}} \to \mathbb{N}[\mathcal{A}_1^*]$ which induces a well-founded ordering on $\mathcal{F}_2^{\mathbf{w}}$, the set of 2-cells of $\mathcal{F}^{\mathbf{w}}$, and show that the cells $C_{f,g}$ are compatible with this ordering (that is, the target of a cell $C_{f,g}$ is always smaller than the source). Thus, the fragment of $\mathcal{F}_3$ consisting of the cells $C_{f,g}$ is 3-terminating.

Thus the $\eta_f$ cells constitute the non-terminating part of $\mathcal{F}_3^{\mathbf{w}}$. To control their behaviour, we introduce a *weight* application $\mathbf{w}_{\eta} : \mathcal{F}_3^{\mathbf{w}} \to \mathbb{N}[\mathcal{A}_1^*]$, that essentially counts the number of $\eta_f$ cells present in a 3-cell. In section 6.3, using the applications $\mathbf{p}$ and $\mathbf{w}_{\eta}$, we prove that for any $h \in \mathcal{F}_2^{\mathbf{w}}$ whose source and target are normal forms (for $\mathcal{A}_2$), and for any 3-cells $A, B : h \Rightarrow 1_{\hat{u}}$ in $\mathcal{F}_3^{\mathbf{w}}$, there is a 4-cell $\alpha : A \twoheadrightarrow B$ in $\mathcal{F}^{\mathbf{w}}(3)$. Finally, we prove that this implies that $\mathcal{F}^{\mathbf{w}}(3)$ is $S_{\mathcal{E}}$-coherent, which concludes the proof.
## Organisation

In Section 1, we recall some classical definitions and results from rewriting theory, and we enunciate (without proof) Theorem 1.4.9. Section 2 contains the definitions of white-categories and white-polygraphs, together with the study of the notion of partial coherence. In Section 3, we construct the free categories encoding the structures we want to study, and prove the coherence Theorems for bicategories (Theorem 3.1.6) and pseudofunctors (Theorem 3.2.7). The proof uses a lot of notions defined in Section 1 and relies in particular on Squier's Theorem to conclude. There remains to show the coherence of pseudonatural transformations (Theorem 3.3.8), which is done in Section 4. To prove Theorem 3.3.8, we show that a fragment of the structure of pseudonatural transformations satisfies the hypotheses of Squier's Theorem while an other satisfies the hypotheses of Theorem 1.4.9, which is temporarily admitted. The following sections contain the proof of Theorem 1.4.9. The first half of the proof is contained in Section 5 and consists in applying a series of transformations to a (4,3)-polygraph satisfying the hypotheses of Theorem 1.4.9. The combinatorics of the result of these transformations is analysed in Section 6 where we conclude the proof.

**Acknowledgments** This work was supported by the Sorbonne-Paris-Cité IDEX grant Focal and the ANR grant ANR-13-BS02-0005-02 CATHRE.
# 1 Higher-dimensional rewriting

We recall definitions and results from rewriting theory. Section 1.1 is devoted to polygraphs, which are presentations of higher-dimensional categories. In Section 1.2, we define termination and enunciate Theorem 1.2.4 which we will use throughout Sections 3 and 4 in order to prove the 3-termination of polygraphs. In Section 1.3 we define the notion of branchings and classify them, which allows for a simple criterion to prove the n-confluence of a polygraph. Finally in Section 1.4, we define the n-Squier condition, and recall Squier’s homotopical theorem, in a generalized form proven in [6]. We conclude this section by enunciating Theorem 1.4.9, whose proof will occupy Sections 5 and 6. Except for Theorem 1.4.9, the proof of every result in this section can be found in [6].

## 1.1 Polygraphs

**Definition 1.1.1.** Let $n$ be a natural number. Let $\mathcal{C}$ be a (strict, globular) $n$-category. For $k \le n$, we denote by $\mathcal{C}_k$ both the set of $k$-cells of $\mathcal{C}$ and the $k$-category obtained by deleting the cells of dimension greater than $k$. For $x \in \mathcal{C}_k$ and $i < k$, we denote by $s_i(x)$ and $t_i(x)$ respectively the $i$-source and $i$-target of $x$. Finally we write $s(x)$ and $t(x)$ respectively for $s_{k-1}(x)$ and $t_{k-1}(x)$.

For $\mathcal{C}$ a 2-category, we denote by $\mathcal{C}^{\text{op}}$ the 2-category obtained by reversing the direction of the 1-cells, and by $\mathcal{C}^{\text{co}}$ the 2-category obtained by reversing the direction of the 2-cells.

We recall the definition of Polygraphs from [3]. For $n \in \mathbb{N}$, we denote by $\mathbf{Cat}_n$ the category of $n$-categories and by $\mathbf{Graph}_n$ the category of $n$-graphs. The category of $n$-categories equipped with a cellular extension, denoted by $\mathbf{Cat}_n^+$, is the limit of the following diagram:

<figure><img src="image_7.png" /></figure>

where the functor $\mathbf{Cat}_n \to \mathbf{Graph}_n$ forgets the categorical structure and the functor $\mathbf{Graph}_{n+1} \to \mathbf{Graph}_n$ deletes the top-dimensional cells.

Hence an object of $\mathbf{Cat}_n^+$ is a couple $(\mathcal{C}, G)$ where $\mathcal{C}$ is an $n$-category and $G$ is a graph $\mathcal{C} \stackrel{s}{\rightleftarrows} \mathcal{C} \stackrel{t}{\rightleftarrows} S_{n+1}$, such that for any $u, v \in S_{n+1}$, the following equations are verified:

$$s(s(u)) = s(t(u)) \quad t(s(u)) = t(t(u))$$

Let $\mathcal{R}_n$ be the functor from $\mathbf{Cat}_{n+1}$ to $\mathbf{Cat}_n^+$ that sends an $(n+1)$-category $\mathcal{C}$ on the couple $(\mathcal{C}_n, \mathcal{C}_n \stackrel{\mathcal{L}_n}{\rightleftarrows} \mathcal{C}_{n+1})$. This functor admits a left-adjoint $\mathcal{L}_n : \mathbf{Cat}_n^+ \to \mathbf{Cat}_{n+1}$ (see [14]).

We now define by induction on $n$ the category $\mathbf{Pol}_n$ of $n$-polygraphs together with a functor $\mathcal{Q}_n : \mathbf{Pol}_n \to \mathbf{Cat}_n$.

* The category $\mathbf{Pol}_0$ is the category of sets, and $\mathcal{Q}_0$ is the identity functor.

* Assume $\mathcal{Q}_n : \mathbf{Pol}_n \to \mathbf{Cat}_n$ is defined. Then $\mathbf{Pol}_{n+1}$ is the limit of the following diagram:

<figure><img src="image_8.png" /></figure>

and $\mathcal{Q}_{n+1}$ is the composite

$$\mathbf{Pol}_{n+1} \longrightarrow \mathbf{Cat}_n^+ \stackrel{\mathcal{L}_n}{\longrightarrow} \mathbf{Cat}_{n+1}$$
**Definition 1.1.2.** Given an $n$-polygraph $\Sigma$, the $n$-category $\mathcal{Q}_n(\Sigma)$ is denoted by $\Sigma^*$ and is called the free $n$-category generated by $\Sigma$.

**Definition 1.1.3.** Let $\mathcal{C}$ be an $n$-category, and $0 \le i < n$ and $A \in \mathcal{C}_{i+1}$. If it exists, we denote by $A^{-1}$ the inverse of $A$ for the $i$-composition.

For $k \le n$, an $(n, k)$-category is an $n$-category which has every $(i+1)$-cell invertible for the $i$-composition, for $i \ge k$. We denote by $\mathbf{Cat}_n^{(k)}$ the full subcategory of $\mathbf{Cat}_n$ whose objects are the $(n, k)$-categories.

In particular $\mathbf{Cat}_n^{(0)}$ is the category of $n$-groupoids, and $\mathbf{Cat}_n^{(n)} = \mathbf{Cat}_n$.

The functor $\mathcal{R}_n$ restricts to a functor $\mathcal{R}_n^{(n)}$ from $\mathbf{Cat}_{n+1}^{(n)}$ to $\mathbf{Cat}_n^+$. Once again this functor admits a left-adjoint $\mathcal{L}_n^{(n)} : \mathbf{Cat}_n^+ \to \mathbf{Cat}_{n+1}^{(n)}$. We define categories $\mathbf{Pol}_n^{(k)}$ of $(n, k)$-polygraphs and functors $\mathcal{Q}_n^{(k)} : \mathbf{Pol}_n^{(k)} \to \mathbf{Cat}_n^{(k)}$ in a similar way to $\mathbf{Pol}_n$ and $\mathcal{Q}_n$. See 2.2.3 in [8] for an explicit description of this construction.

**Definition 1.1.4.** Given an $(n, k)$-polygraph $\Sigma$, the $(n, k)$-category $\mathcal{Q}_n^{(k)}(\Sigma)$ is denoted by $\Sigma^{*(k)}$ and is called the free $(n, k)$-category generated by $\Sigma$. For $j \le n$, we denote by $\Sigma_j^{*(k)}$ both the the of $j$-cells of $\Sigma^{*(k)}$ and the $(j, k)$-category generated by $\Sigma$. Hence an $(n, k)$-polygraph $\Sigma$ consists of the following data:

<figure><img src="image_9.png" /></figure>

**Remark 1.1.5.** Let $n, j$ and $k$ be integers, with $j \le k \le n$. Since an $(n, k)$-category is also an $(n, j)$-category, an $(n, k)$-polygraph gives rise to an $(n, j)$-polygraph. In particular, if $\Sigma$ is an $(n, k)$-polygraph, we denote by $\Sigma^{*(j)}$ the $(n, j)$-category it generates.

**Definition 1.1.6.** Let $\mathcal{C}$ be an $(n+1, k)$-category. We denote by $\bar{\mathcal{C}}$ the $(n, k)$-category $\mathcal{C}_n/\mathcal{C}_{n+1}$.

Let $\Sigma$ be an $(n+1, k)$-polygraph. We denote by $\bar{\Sigma}$ the $(n, k)$-category $\Sigma^{*(k)}$ and call it the $(n, k)$-category presented by $\Sigma$.

## 1.2 Termination

**Definition 1.2.1.** Let $\Sigma$ be an $n$-polygraph. For $0 < k \le n$, the binary relation $\to_k^*$ defined by $u \to_k^* v$ if there exists $f : u \to v$ in $\Sigma_k^*$ is a preorder on $\Sigma_{k-1}^*$ (transitivity is given by composition, and reflexivity by the units). We say that the $n$-polygraph $\Sigma$ is $k$-terminating if $\to_k^*$ is a well-founded ordering. We denote by $\to_k^+$ the strict ordering associated to $\to_k^*$.

We recall Theorem 4.2.1 from [6], which we will use in order to show the 3-termination of some polygraphs.

**Definition 1.2.2.** Let $\mathbf{sOrd}$ be the 2-category with one object, whose 1-cells are partially ordered sets, whose 2-cells are monotonic functions and which 0-composition is the cartesian product.

**Definition 1.2.3.** Let $\mathcal{C}$ be a 2-category, $X : \mathcal{C}_2 \to \mathbf{sOrd}$ and $Y : \mathcal{C}_2^{\mathcal{C}} \to \mathbf{sOrd}$ two 2-functors, and $M$ a commutative monoid. An $(X, Y, M)$-derivation on $\mathcal{C}$ is given by, for every 2-cell $f \in \mathcal{C}_2$, an application

$$d(f) : X(s(f)) \times Y(t(f)) \to M,$$

such that for every 2-cells $f_1, f_2 \in \mathcal{C}_2$, every $x, y, z$ and $t$ respectively in $X(s(f_1)), Y(t(f_1)), X(s(f_2))$ and $Y(t(f_2))$, the following equalities hold:

$$d(f_1 \star_1 f_2)[x, t] = d(f_1)[x, Y(f_2)[y]] + d(f_2)[X(f_1)[x], y]$$

$$d(f_1 \star_0 f_2)[(x, z), (y, t)] = d(f_1)[x, y] + d(f_2)[z, t].$$
In order to show the 3-termination of some polygraphs, we are going to use the following result (Theorem 4.2.1 from [6]).

**Theorem 1.2.4.** Let $\Sigma$ be an $n$-polygraph, $X : \Sigma_2^* \to \mathbf{sOrd}$ and $Y : (\Sigma_2^*)^{\mathbf{co}} \to \mathbf{sOrd}$ two 2-functors, and $M$ be a commutative monoid equipped with a well-founded ordering $\geq$, and whose addition is strictly monotonous in both arguments.

Suppose that for every 3-cell $A \in \Sigma_3$, the following inequalities hold:

$$X(\mathbf{s}(A)) \geq X(\mathbf{t}(A)) \quad Y(\mathbf{s}(A)) \geq Y(\mathbf{t}(A)) \quad d(\mathbf{s}(A)) > d(\mathbf{t}(A)).$$

Then the $n$-polygraph $\Sigma$ is 3-terminating.

## 1.3 Branchings and Confluence

**Definition 1.3.1.** Let $\Sigma$ be an $n$-polygraph. A $k$-fold branching of $\Sigma$ is a $k$-tuple $(f_1, f_2, \dots, f_k)$ of $n$-cells in $\Sigma^*$ such that every $f_i$ has the same source $u$, which is called the source of the branching.

The symmetric group $S_k$ acts on the set of all $k$-fold branchings of $\Sigma$. The equivalence class of a branching $(f_1, f_2, \dots, f_k)$ under this action is denoted by $[f_1, f_2, \dots, f_k]$. Such an equivalence class is called a $k$-fold symmetrical branching, and $(f_1, f_2, \dots, f_k)$ is called a representative of $[f_1, f_2, \dots, f_k]$

**Definition 1.3.2.** Let $\Sigma$ be an $n$-polygraph. We denote by $\mathbb{N}$ the $n$-category with exactly one $k$-cell for every $k < n$, whose $n$-cells are the natural numbers and whose compositions are given by addition.

We define an application $\ell : \Sigma^* \to \mathbb{N}$ by setting $\ell(f) = 1$ for every $f \in \Sigma_n$. For $f \in \Sigma_n^*$, we call $\ell(f)$ the length of a $f$.

An $n$-cell of length 1 in $\Sigma_n^*$ is also called a *rewriting step*.

**Definition 1.3.3.** Let $\Sigma$ be an $n$-polygraph. A $k$-fold local branching of $\Sigma$ is a $k$-fold branching $(f_1, f_2, \dots, f_k)$ of $\Sigma$ where every $f_i$ is a rewriting step.

A $k$-fold local branching $(f_1, \dots, f_k)$ of source $u$ is a *strict aspherical branching* if there exists an integer $i$ such that $f_i = f_{i+1}$. We say that it is an *aspherical branching* if it is in the equivalence class of a strict aspherical branching.

A $k$-fold local branching $(f_1, \dots, f_k)$ is a *strict Peiffer branching* if it is not aspherical and there exist $v_1, v_2 \in \Sigma_{n-1}^*$ such that $u = v_1 \star_i v_2$, an integer $m < n$ and $f_1', \dots, f_k' \in \Sigma_n^*$ such that for every $j \le m$, $f_j = f_j' \star_i v_2$ and for every $j > m$, $f_j = v_1 \star_i f_j'$. It is a *Peiffer branching* if it is in the equivalence class of a strict Peiffer branching.

A local branching that is neither aspherical nor Peiffer is *overlapping*.

Given an $n$-polygraph $\Sigma$, one defines an order $\subseteq$ on $k$-fold local branchings by saying that $(f_1, \dots, f_k) \subseteq (u \star_i f_1 \star_i v, \dots, u \star_i f_k \star_i v)$ for every $u, v \in \Sigma_{n-1}^*$ and every $k$-fold local branching $(f_1, \dots, f_k)$.

**Definition 1.3.4.** An overlapping branching that is minimal for $\subseteq$ is a *critical branching*.

A 2-fold (resp. 3-fold) critical branching is also called a *critical pair* (resp. *critical triple*).

**Definition 1.3.5.** Let $\Sigma$ be an $n$-polygraph. A 2-fold branching $(f, g)$ is *confluent* if there are $f', g' \in \Sigma_n^*$ of the following shape:

<figure><img src="image_10.png" /></figure>

**Definition 1.3.6.** An $n$-polygraph $\Sigma$ is $k$-confluent if every 2-fold branching of $\Sigma_k$ is confluent.

**Definition 1.3.7.** An $n$-polygraph is $k$-convergent if it is $k$-terminating and $k$-confluent.

The following two propositions are proven in [6].

**Proposition 1.3.8.** Let $\Sigma$ be an $n$-terminating $n$-polygraph. It is $n$-confluent if and only if every 2-fold critical branching is confluent.
**Proposition 1.3.9.** Let $\Sigma$ be a $k$-convergent $n$-polygraph. For every $u \in \Sigma_{k-1}^*$, there exists a unique $v \in \Sigma_{k-1}^*$ such that $u \to_k^* v$ and $v$ is minimal for $\to_k^*$.

**Definition 1.3.10.** Let $\Sigma$ be an $n$-polygraph. A normal form for $\Sigma$ is an $(n-1)$-cell minimal for $\to_n^*$. If $\Sigma$ is $n$-convergent, for every $u \in \Sigma_{n-1}^*$, the unique normal form $v$ such that $u \to_n^* v$ is denoted by $\hat{u}$ and is called the normal form of $u$.

## 1.4 Coherence

**Definition 1.4.1.** Two $k$-cells are parallel if they have the same source and the same target.

An $(n+1)$-category $\mathcal{C}$ is $n$-coherent if, for each pair $(f,g)$ of parallel $n$-cells in $\mathcal{C}_n$, there exists an $(n+1)$-cell $A : f \to g$ in $\mathcal{C}_{n+1}$.

**Definition 1.4.2.** Let $\Sigma$ be an $(n+1)$-polygraph, and $(f,g)$ be a local branching of $\Sigma_n$. A filling of $(f,g)$ is an $(n+1)$-cell $A \in \Sigma_{n+1}^{*(n)}$ of the shape:

<figure><img src="image_11.png" /></figure>

**Definition 1.4.3.** An $(n+1)$-polygraph $\Sigma$ satisfies the $n$-Squier condition if:

* it is $n$-convergent,

* there is a bijective application from $\Sigma_{n+1}$ to the set of all critical pairs of $\Sigma_n$ that associates to every $A \in \Sigma_{n+1}$, a critical pair $b$ of $\Sigma_n$ such that $A$ is a filling of a representative of $b$.

The following Theorem is due to Squier for $n=2$ [16] and was extended to any integer $n \ge 2$ by Guiraud and Malbos [6].

**Theorem 1.4.4.** Let $\Sigma$ be an $(n+1)$-polygraph satisfying the $n$-Squier condition. Then the free $(n+1, n-1)$-category $\Sigma^{*(n-1)}$ is $n$-coherent.

In the proof of this Theorem appears the following result (Lemma 4.3.3 in [6]).

**Proposition 1.4.5.** Let $\Sigma$ be an $(n+1)$-polygraph satisfying the $n$-Squier condition.

For every parallel $n$-cells $f, g \in \Sigma_n^*$ whose target is a normal form, there exists an $(n+1)$-cell $A : f \to g$ in $\Sigma_{n+1}^{*(n)}$.

Let us compare those two last results. Let $\Sigma$ be an $(n+1)$-polygraph satisfying the $n$-Squier relation, and let $f, g \in \Sigma_n^*$ be two parallel $n$-cells whose target is a normal form. According to Theorem 1.4.4, there exists an $(n+1)$-cell $A : f \to g$ in the free $(n+1, n-1)$-category $\Sigma_{n+1}^{*(n-1)}$. Proposition 1.4.5 shows that such an $A$ can be chosen in the free $(n+1, n)$-category $\Sigma_{n+1}^{*(n)}$, where the $n$-cells are not invertible. Hence for cells $f, g \in \Sigma_n^*$ whose target is a normal form, Proposition 1.4.5 is more precise than Theorem 1.4.4.

**Definition 1.4.6.** Let $\Sigma$ be an $(n+1)$-polygraph, and $(f,g)$ a local branching in $\Sigma_n$. Depending on the nature of $(f,g)$, we define the notion of *canonical filling* of $(f,g)$.

* If $(f,g)$ is an aspherical branching, then its canonical filling is the identity $1_f$.

* If $(f,g)$ is a Peiffer branching, if $(f,g) = (f' \star_i v_1, v_2 \star_i g')$ (resp. $(f,g) = (v_1 \star_i f', g' \star_i v_2)$), then its canonical filling is $1_{f' \star_i g'}$ (resp. $1_{g' \star_i f'}$).

* Assume that $\Sigma$ satisfies the $n$-Squier condition, and let $(f,g)$ be a critical pair. Let $A$ be the $(n+1)$-cell associated to $[f,g]$. If $A$ is a filling of $(f,g)$ then the canonical filling of $(f,g)$ is $A$. Otherwise, $A$ is a filling of $(g,f)$ and the canonical filling of $(f,g)$ is $A^{-1}$.
* Assume that the branching $(f,g)$ admits a canonical filler $A$. Then the canonical filler of $(u \star_i f \star_i v, u \star_i f \star_i v)$ is $u \star_i A \star_i v$.

**Definition 1.4.7.** Let $\Sigma$ be an $(n+2, n)$-polygraph satisfying the $n$-Squier condition, and $(f,g,h)$ be a local branching of $\Sigma_n$. A *filling* of $(f,g,h)$ is an $(n+2)$-cell $\alpha \in \Sigma_{n+2}^{*(n)}$ of the shape:

<figure><img src="image_12.png" /></figure>

where $A, A_{f,g}, A_{g,h}, A_{f,h}, B_1$ and $B_2$ are $(n+1)$-cells in $\Sigma_{n+1}^{*(n)}$, and $A_{f,g}, A_{g,h}$ and $A_{f,h}$ are the canonical fillings of respectively $(f,g)$, $(g,h)$ and $(f,h)$.

**Definition 1.4.8.** An $(n+2, n)$-polygraph $\Sigma$ satisfies the $n$-Squier condition of depth 2 if:

* it satisfies the $n$-Squier condition,

* there is a bijective application from $\Sigma_{n+2}$ to the set of all critical triples of $\Sigma_n$ that associates to every $\alpha \in \Sigma_{n+2}$ a critical triple $b$ of $\Sigma_n$ such that $\alpha$ is a filling of a representative of $b$.

We now enunciate the theorem whose proof will occupy Sections 5 and 6.

**Theorem 1.4.9.** Let $\Sigma$ be a (4, 2)-polygraph satisfying the 2-Squier condition of depth 2.

For every parallel 3-cells $A, B \in \Sigma_3^{*(2)}$ whose 1-target is a normal form, there exists a 4-cell $\alpha : A \stackrel{\alpha}{\rightleftharpoons} B$ in the free (4, 2)-category $\Sigma_4^{*(2)}$.

This Theorem can be compared with Proposition 4.4.4 in [8]. There, for every parallel $A, B \in \Sigma_3^{*(1)}$, a 4-cell $\alpha$ is constructed in the free (4, 1)-category $\Sigma_4^{*(1)}$. Hence Theorem 1.4.9 gives a more precise statement, at the cost of restricting the set of 3-cells allowed.
## 2 Partial coherence and transformation of polygraphs

In Section 2.1 we define the notion of white-category together with the associated notion of white-polygraph. The 2-white-categories are also known as sesquicategories (see [19]). White-categories are strict categories in which the interchange law between the compositions $\star_0$ and $\star_i$ need not hold, for every $i > 0$. That is, strict $n$-categories are exactly the $n$-white-categories satisfying the additional condition that for every $i$-cells $f$ and $g$ of 1-sources (resp. 1-targets) $u$ and $v$ (resp. $u'$ and $v'$): $(f \star_0 v) \star_i (u' \star_0 g) = (u \star_0 g) \star_i (f \star_0 v)$.

In Section 2.2, we define a notion of partial coherence for (4,3)-white-categories. We show a simple criterion in order to deduce the partial coherence of a (4,3)-white-category from that of an other one. This criterion will be used throughout Section 5. We also adapt the notion of Tietze-transformation from [5] to our setting of partial coherence in white-categories, in preparation for Section 5.5.

In Section 2.3, we study injective functors between free white-categories. In particular, we give a sufficient condition for a morphism of white-polygraphs to yield an injective functor between the white-categories they generate. This result will be used in Section 5.3.

Note that, although Sections 2.2 and 2.3 are expressed in terms of white-categories (since this is how they will be used throughout Section 5), all the definitions and results in these Sections also hold in terms of strict categories, mutatis mutandis.

### 2.1 White-categories and White-polygraphs

**Definition 2.1.1.** Let $n \in \mathbb{N}$. An $(n+1)$-white-category is given by:

* a set $C_0$,

* for every $x, y \in C_0$, an $n$-category $\mathcal{C}(x, y)$. We denote by $\star_{k+1}$ the $k$-composition in this category,

* for every $z \in C_0$ and every $u : x \to y \in C_1$, functors $u \star_0 \mathcal{C}(y, z) \to \mathcal{C}(x, z)$ and $\mathcal{C}(z, y)$, so that for every composable 1-cells $u, v \in C_1$, their composite $u \star_0 v$ is defined in a unique way,

* for every $x \in C_0$, a 1-cell $1_x \in \mathcal{C}(x, x)$.

Moreover, this data must satisfy the following axioms:

* For every $x \in C_0$, and every $y \in C_0$, the functors $1_x \star_0 \mathcal{C}(x, y) \to \mathcal{C}(x, y)$ and $\mathcal{C}(x, y) \to \mathcal{C}(x, y)$ are identities.

* For every $u, v \in C_1$, the following equalities hold:

$$ - u \star_0 (v \star_0 \mathcal{C}(x, y)) = (u \star_0 v) \star_0 \mathcal{C}(x, y), $$

$$ - u \star_0 (\mathcal{C}(x, y) \star_0 v) = (u \star_0 \mathcal{C}(x, y)) \star_0 v, $$

$$ - \mathcal{C}(x, y) \star_0 (u \star_0 v) = (\mathcal{C}(x, y) \star_0 u) \star_0 v, $$

An $(n, k)$-white-category is an $n$-white-category in which every $(i+1)$-cell is invertible for the $i$-composition, for every $i \ge k$.

Let $n$ be a natural number. Let $\mathcal{C}$ be an $n$-white-category. For $k \le n$, we denote by $C_k$ both the set of $k$-cells of $\mathcal{C}$ and the $k$-white-category obtained by deleting the cells of dimension greater than $k$. For $x \in C_k$ and $i < k$, we denote by $s_i(x)$ and $t_i(x)$ respectively the $i$-source and $i$-target of $x$. Finally we write $s(x)$ and $t(x)$ respectively for $s_{k-1}(x)$ and $t_{k-1}(x)$.

**Definition 2.1.2.** Let $\mathcal{C}$ and $\mathcal{D}$ be $n$-white-categories. An $n$-white-functor is given by:

* an application $F_0 : C_0 \to \mathcal{D}_0$,

* for every $x, y \in C_0$, a functor $F_{x,y} : \mathcal{C}(x, y) \to \mathcal{D}(F_0(x), F_0(y))$.

Moreover, this data must satisfy the following axioms:

* for every $x \in C_0$, $F(1_x) = 1_{F_0(x)}$,
* for every $z \in \mathcal{C}_0$ and $u : x \to y \in \mathcal{C}_1$, the following equalities hold between functors:

$$ - F(u) \star_0 F(\_) = F(u \star_0 \_) : \mathcal{C}(y, z) \to \mathcal{D}(F_0(x), F_0(z)) $$

$$ - F(\_) \star_0 F(u) = F(\_ \star_0 u) : \mathcal{C}(z, x) \to \mathcal{D}(F_0(z), F_0(y)) $$

This makes $n$-white-categories into a category, that we denote by $\mathbf{WCat}_n$.

**Remark 2.1.3.** Let us define a structure of monoidal category $\otimes$ on $\mathbf{Cat}_n$, in such a way that $\mathbf{WCat}_{n+1}$ is the category of categories enriched over $(\mathbf{Cat}_n, \otimes)$.

Let $\mathcal{C}, \mathcal{D}$ be two $n$-categories. The $n$-categories $\mathcal{C} \times \mathcal{D}_0$ and $\mathcal{C}_0 \times \mathcal{D}$ are defined as follows:

$$ \mathcal{C} \times \mathcal{D}_0 := \bigsqcup_{y \in \mathcal{D}_0} \mathcal{C}, \quad \mathcal{C}_0 \times \mathcal{D} := \bigsqcup_{x \in \mathcal{C}_0} \mathcal{D} $$

Let $\mathcal{C}_0 \times \mathcal{D}_0$ be the $n$-category whose 0-cells are couples $(x, y) \in \mathcal{C}_0 \times \mathcal{D}_0$, and whose $i$-cells are identities for every $i > 0$. Let $F : \mathcal{C}_0 \times \mathcal{D}_0 \to \mathcal{C} \times \mathcal{D}_0$ (resp. $G : \mathcal{C}_0 \times \mathcal{D}_0 \to \mathcal{C}_0 \times \mathcal{D}$) be the $n$-functor which is the identity on 0-cells. Then $\mathcal{C} \otimes \mathcal{D}$ is the pushout $(\mathcal{C} \times \mathcal{D}_0) \underset{\mathcal{C}_0 \times \mathcal{D}_0}{\otimes} (\mathcal{C}_0 \times \mathcal{D})$:

$$ \begin{array}{ccc} \mathcal{C}_0 \times \mathcal{D}_0 & \xrightarrow{F} & \mathcal{C} \times \mathcal{D}_0 \\ \mathcal{G} & \searrow^{\Box} & \mathcal{C} \times \mathcal{D} \\ \mathcal{C}_0 \times \mathcal{D} & \longrightarrow & \mathcal{C} \otimes \mathcal{D}. \end{array} $$

The category of $n$-white-categories equipped with a cellular extension, denoted by $\mathbf{WCat}_n^+$, is the limit of the following diagram:

$$ \begin{array}{ccc} \mathbf{WCat}_n^+ & \longrightarrow & \mathbf{Graph}_{n+1} \\ \downarrow & & \downarrow \\ \mathbf{WCat}_n & \longrightarrow & \mathbf{Graph}_n \end{array} $$

where the functor $\mathbf{WCat}_n \to \mathbf{Graph}_n$ forgets the white-categorical structure and the functor $\mathbf{Graph}_{n+1} \to \mathbf{Graph}_n$ deletes the top-dimensional cells.

Let $\mathcal{R}_n^w$ be the functor from $\mathbf{WCat}_{n+1}$ to $\mathbf{WCat}_n^+$ that sends an $(n+1)$-white-category $\mathcal{C}$ on the couple $(\mathcal{C}_n, \mathcal{C}_n \stackrel{\sim}{\longrightarrow} \mathcal{C}_{n+1})$.

**Proposition 2.1.4.** The functor $\mathcal{R}_n^w$ admits a left-adjoint $\mathcal{L}_n^w : \mathbf{WCat}_n^+ \to \mathbf{WCat}_{n+1}$.

*Proof.* Let $(\mathcal{C}, \Sigma) \in \mathbf{WCat}_n^+$ be an $n$-white-category equipped with a cellular extension. The construction of $\mathcal{L}_n^w(\mathcal{C}, \Sigma)$ is split into three parts:

* First, we define a formal language $E_\Sigma$.

* Then, we define a typing system $T_C$ on $E_\Sigma$. We denote by $E_\Sigma^T$ the set of all typable expressions of $E_\Sigma$.

* Finally, we define an equivalence relation $\equiv_\Sigma^*$ on $E_\Sigma^T$. The set of $(n+1)$-cell of $\mathcal{L}_n^w(\mathcal{C}, \Sigma)$ is then the quotient $E_\Sigma^T / \equiv_\Sigma^*$.

Let $E_\Sigma$ be the formal language consisting of:

* For every 1-cells $u, v \in \mathcal{C}_1$, and every $(n+1)$-cell $A \in \Sigma_{n+1}$, such that $t_0(u) = s_0(A)$ and $t_0(A) = s_0(v)$, a constant symbol $c_{uAv}$.

* For every $n$-cell $f \in \mathcal{C}_n$, a constant symbol $i_f$.

* For every $0 < i \le n$, a binary function symbol $\star_i$.
Thus $E_Σ$ is the smallest set of expressions containing the constant symbols and such that $e \star_i f \in Σ$ whenever $e, f \in E_Σ$.

Let $T_C$ be the set of all $n$-spheres of $C$, that is of couples $(f, g)$ in $C_n$ such that $s(f) = s(g)$ and $t(f) = t(g)$. For $e \in E_Σ$ and $t \in T_C$, we define $e : t$ (read as "e is of type t") as the smallest relation satisfying the following axioms:

* For every 1-cells $u$ and $v$ in $C_1$, and every $(n+1)$-cell $A \in Σ$, such that $t_0(u) = s_0(A)$ and $t_0(A) = s_0(v)$

$$c_{uAv} : (us(A)v, ut(A)v)$$

* For every $n$-cell $f \in C_n$

$$i_f : (f, f)$$

* For every $e_1, e_2 \in E_Σ$ and $i < n$, if $e_1 : (s_1, t_1)$, $e_2 : (s_2, t_2)$ and $t_i(t_1) = s_i(s_2)$, then

$$e_1 \star_i e_2 : (s_1 \star_i s_2, t_1 \star_i t_2)$$

* For every $e_1, e_2 \in E_Σ$, if $e_1 : (s_1, t_1)$, $e_2 : (s_2, t_2)$ and $t_1 = s_2$, then

$$e_1 \star_n e_2 : (s_1, t_2)$$

An expression $e \in E_Σ$ is said to be *typable* if $e : (s, t)$ for some $n$-sphere $(s, t) \in T_C$. Moreover there is only one such $n$-sphere, so the operations $s(e) := s$ and $t(e) := t$ are well defined. We denote by $E_Σ^T$ be the set of all typable expressions.

Let $\equiv_Σ$ be the symmetric relation generated by the following relations on $E_Σ^T$:

* For every $A, B, C, D \in E_Σ^T$, and every $i_1, i_2 \le n$ non-zero distinct natural numbers,

$$(A \star_{i_1} B) \star_{i_2} (C \star_{i_1} D) \equiv_{\Sigma} (A \star_{i_2} C) \star_{i_1} (B \star_{i_2} D)$$

* For every $A, B, C \in E_Σ^T$, and every $0 < i \le n$,

$$(A \star_i B) \star_i C \equiv_{\Sigma} A \star_i (B \star_i C)$$

* For every $A \in E_Σ^T$ and $f \in C_n$:

$$i_f \star_n A \equiv_{\Sigma} A \quad A \star_n i_f \equiv_{\Sigma} A$$

* For every $f_1, f_2 \in C_n$ and every $i < n$,

$$i_{f_1} \star_i i_{f_2} \equiv_{\Sigma} i_{f_1 \star_i f_2}$$

* For every $A, A', B \in E_Σ^T$ and every $0 < i \le n$, if $A \equiv_Σ A'$, then

$$A \star_i B \equiv_{\Sigma} A' \star_i B$$

* For every $A, B, B' \in E_Σ^T$ and every $0 < i \le n$, if $B \equiv_Σ B'$, then

$$A \star_i B \equiv_{\Sigma} A \star_i B'$$

Let $\equiv_Σ^*$ be the reflexive closure of $\equiv_Σ$. The $(n+1)$-cells of $L_n^w(C, Σ)$ are given by the quotient $E_Σ^T / \equiv_Σ^*$. The $i$-composition is given by the one of $E_Σ^T$, and identities by $i_f$. $\square$

**Definition 2.1.5.** We now define by induction on $n$ the category $WPol_n$ of $n$-white-polygraphs together with a functor $Q_n^w : WPol_n \to WCat_n$.

* The category $WPol_0$ is the category of sets, and $Q_0^w$ is the identity functor.
• Assume $Q_n^w : \mathrm{WPol}_n \to \mathrm{WCat}_n$ defined. Then $\mathrm{WPol}_{n+1}$ is the limit of the following diagram:

<figure><img src="image_13.png" /></figure>

and $Q_{n+1}^w$ is the composite

$$ \mathrm{WPol}_{n+1} \longrightarrow \mathrm{WCat}_n^+ \xrightarrow{\mathcal{L}_n^w} \mathrm{WCat}_{n+1} $$

Given an $n$-white-polygraph $\Sigma$, the $n$-white-category $Q_n^w(\Sigma)$ is denoted by $\Sigma^w$ and is called the free $n$-white-category generated by $\Sigma$.

**Definition 2.1.6.** Let $\mathrm{WCat}_{n+1}^{w(n)}$ be the category of $(n+1, n)$-white-categories. Once again we have a functor $\mathcal{R}_n^{w(n)} : \mathrm{WCat}_{n+1}^{w(n)} \to \mathrm{WCat}_n^+$, and we are going to describe its left-adjoint $\mathcal{L}_{n+1}^{w(n)}$. Let $(C, \Sigma)$ be an $n$-white-category together with a cellular extension. To construct $\mathcal{L}_{n+1}^{w(n)}(C, \Sigma)$, we adapt the construction of the free $n$-white-categories as follows:

• Let $F_\Sigma$ be the formal language $E_{\Sigma \cup \bar{\Sigma}}$, where $\bar{\Sigma}$ consists of formal inverses to the elements of $\Sigma$ (that is their source and targets are reversed).

• The type system is extended by setting, for every 1-cells $u, v$ in $C_1$ and every $(n+1)$-cell $A \in \Sigma$ such that $t_0(u) = s_0(v)$ and $t_0(A) = s_0(A)$:

$$ c_{u\bar{A}v} : (ut(A)v, us(A)v). $$

We denote by $F_\Sigma^T$ the set of all typable expressions for this new typing system.

• We extend $\equiv_\Sigma$ into a relation denoted by $\cong_\Sigma$ by adding the following relations:

$$ c_{uAv} \star_n c_{u\bar{A}v} \cong_\Sigma i_{us(A)v} \qquad c_{u\bar{A}v} \star_n c_{uAv} \cong_\Sigma i_{ut(A)v} $$

for every $u, v$ in $C_1$ and every $(n+1)$-cell $A \in \Sigma$, such that $t_0(u) = s_0(A)$ and $t_0(A) = s_0(v)$.

We define categories $\mathrm{WPol}_n^{(k)}$ of $(n, k)$-white-polygraphs and functors $Q_n^{w(k)} : \mathrm{WPol}_n^{(k)} \to \mathrm{WCat}_n^{(k)}$ in a similar way to $\mathrm{Pol}_n^{(k)}$ and $Q_n^{w(k)}$.

**Definition 2.1.7.** Given an $(n, k)$-white-polygraph $\Sigma$, the $(n, k)$-white-category $Q_n^{w(k)}(\Sigma)$ is denoted by $\Sigma^{w(k)}$ and is called the free $(n, k)$-white-category generated by $\Sigma$. For $j \le n$, we denote by $\Sigma_j^{w(k)}$ both the $j$-cells of $\Sigma^{w(k)}$ and the $(j, k)$-category generated by $\Sigma$. Hence an $(n, k)$-polygraph $\Sigma$ consists of the following data:

<figure><img src="image_14.png" /></figure>

## 2.2 Partial coherence in pointed (4, 3)-white-categories

**Definition 2.2.1.** A pointed (4, 3)-white-category is a couple $(C, S)$, where $C$ is a 4-white-category, and $S$ is a subset of $C_2$.

**Definition 2.2.2.** Let $(C, S)$ be a pointed (4, 3)-white-category. The restriction of $C$ to $S$, denoted by $C|_S$, is the following (2, 1)-category:
• its 0-cells are the 2-cells of $\mathcal{C}_2$ that lie in $S$,

• its 1-cells are the 3-cells of $\mathcal{C}_3$ with source and target in $S$,

• its 2-cells are the 4-cells of $\mathcal{C}_4$ with 2-source and 2-target in $S$,

• its 0-composition and 1-composition are respectively induced by the compositions $\star_2$ and $\star_3$ of $\mathcal{C}$.

**Definition 2.2.3.** Let $(\mathcal{C}, S)$ be a pointed (4,3)-white-category. We say that $\mathcal{C}$ is $\mathcal{S}$-coherent if for every parallel 1-cells $A, B$ in the (2,1)-category $\mathcal{C}|S$, there exists a 2-cell $\alpha : A \Rightarrow B \in \mathcal{C}|S$.

**Example 2.2.4.** Every (4,3)-white-category is $\emptyset$-coherent. A (4,3)-white-category $\mathcal{C}$ is $\mathcal{C}_2$-coherent if and only if it is 3-coherent.

We now rephrase Theorem 1.4.9 in the setting of partial coherence.

**Theorem 1.4.9.** Let $\mathcal{A}$ be a (4,2)-polygraph satisfying the 2-Squier condition of depth 2, and let $S_A$ be the set of all 2-cells whose target is a normal form.

Then $\mathcal{A}$ is $S_A$-coherent.

**Definition 2.2.5.** Let $\mathcal{C}$ and $\mathcal{D}$ be two 2-categories, $F : \mathcal{C} \to \mathcal{D}$ a 2-functor.

We say that $F$ is 0-surjective if the application $F : \mathcal{C}_0 \to \mathcal{D}_0$ is surjective.

Let $0 < k < 2$. We say that $F$ is $k$-surjective if, for every $(k-1)$-parallel cells $s, t \in \mathcal{C}_{k-1}$, the application $F : \mathcal{C}_k(s, t) \to \mathcal{D}_k(F(s), F(t))$ is surjective.

**Definition 2.2.6.** Let $(\mathcal{C}, S)$ and $(\mathcal{C}', S')$ be two pointed (4,3)-categories. We say that $(\mathcal{C}', S')$ is stronger than $(\mathcal{C}, S)$ if there is a functor $F : \overline{\mathcal{C}'}|S' \to \overline{\mathcal{C}}|S$ which is 0-surjective and 1-surjective.

**Lemma 2.2.7.** Let $(\mathcal{C}, S)$, $(\mathcal{C}', S')$ be two pointed (4,3)-white-categories. If there exists a 2-functor $F : \mathcal{C}'|S' \to \mathcal{C}|S$ which is 0-surjective and 1-surjective, then $(\mathcal{C}', S')$ is stronger than $(\mathcal{C}, S)$.

*Proof.* The functor $F$ induces a functor $\bar{F} : \overline{\mathcal{C}'}|S' \to \overline{\mathcal{C}}|S$. Since it is equal to $F$ on objects, it is 0-surjective. On 1-cells $\bar{F}$ is the composition of $F$ with the canonical projection associated to the quotient, hence it is 1-surjective, and so $(\mathcal{C}', S')$ is stronger than $(\mathcal{C}, S)$. $\square$

**Lemma 2.2.8.** Let $(\mathcal{C}, S)$, $(\mathcal{C}', S')$ be two pointed (4,3)-white-categories, and assume $(\mathcal{C}', S')$ is stronger than $(\mathcal{C}, S)$.

If $\mathcal{C}'$ is $S'$-coherent, then $\mathcal{C}$ is $\mathcal{S}$-coherent.

*Proof.* Let $F : \overline{\mathcal{C}'}|S' \to \overline{\mathcal{C}}|S$ be a functor that is 0-surjective and 1-surjective. Let $A, B : f \to g \in (\mathcal{C}|S)_1$ be parallel 1-cells, and $\bar{A}, \bar{B}$ be their projections in $\overline{\mathcal{C}}|S$.

Since $F$ is 0-surjective, there exists $f', g' \in (\mathcal{C}'|S')_0$ in the preimage of $f$ and $g$ under $F$. Since $F$ is 1-surjective, there exists $A', B' \in (\mathcal{C}'|S')_1$ of source $f'$ and of target $g'$ such that $F(\bar{A}') = \bar{A}$ and $F(\bar{B}') = \bar{B}$.

Since $\mathcal{C}'|S'$ is 2-coherent, there exists $\alpha' : A' \Rightarrow B' \in (\mathcal{C}'|S')_2$. Thus $\bar{A}' = \bar{B}'$ and $\bar{A} = \bar{B}$. Hence there exists $\alpha : A \Rightarrow B \in \mathcal{C}|S$. This shows that $\mathcal{C}|S$ is 1-coherent, and therefore that $\mathcal{C}$ is $\mathcal{S}$-coherent. $\square$

We are going to define four families of Tietze-transformations on (4,3)-white-polygraphs. Tietze transformations originate from combinatorial group theory [11], and was adapted for (3,1)-categories in [5], as a way to modify a (3,1)-polygraph without modifying the 2-categories it presents. In particular, they preserve the 2-coherence. Here we adapt these transformations to our setting of (4,3)-white-polygraphs and show that they preserve the partial coherence. This will be used in Section 5.5. We fix a 4-white-polygraph $\mathcal{A}$.

**Definition 2.2.9.** Let $A \in \mathcal{A}^{w(3)}$. We define a 4-white-polygraph $\mathcal{A}(A)$ by adding to $\mathcal{A}$ a 3-cell $B$ and a 4-cell $\alpha$, whose sources and targets are given by:

• $s(B) = s(A)$,

• $t(B) = t(A)$,

• $s(\alpha) = A$,
• $t(\alpha) = B$.

The inclusion induces a functor between (4,3)-white-categories $\iota_A : \mathcal{A}^{w(3)} \to (\mathcal{A}(A))^{w(3)}$. We call this operation the *adjunction of a 3-cell with its defining 4-cell*.

**Definition 2.2.10.** Let $\alpha \in \mathcal{A}_4$ and $A \in \mathcal{A}_3$ such that:

• $t(\alpha) = A$

• $s(\alpha) \in (\mathcal{A} \setminus \{t(\alpha)\})_3^{w(3)}$.

The 4-cell $\alpha$ induces an application $\mathcal{A}_3 \to (\mathcal{A}_3 \setminus \{t(\alpha)\})^{w(3)}$, by sending $t(\alpha)$ on $s(\alpha)$ and that is the identity on the other cells of $\mathcal{A}_3$. This application extends into a 3-functor $\pi_\alpha : \mathcal{A}_3^w \to (\mathcal{A}_3 \setminus \{t(\alpha)\})^w$. Let $\mathcal{A}/(A; \alpha)$ be the following 4-white-polygraph:

$$ \mathcal{A}_0 \underset{\mathbf{t}}{\overset{\mathbf{s}}{\rightleftarrows}} \mathcal{A}_1^{w(3)} \underset{\mathbf{t}}{\overset{\mathbf{s}}{\rightleftarrows}} \mathcal{A}_2^{w(3)} \underset{\mathbf{t}}{\overset{\mathbf{s}}{\rightleftarrows}} (\mathcal{A}_3 \setminus \{\mathbf{t}(\alpha)\})^{w(3)} \underset{\pi_\alpha \circ \mathbf{t}}{\overset{\pi_\alpha \circ \mathbf{s}}{\rightleftarrows}} \mathcal{A}_4 \setminus \{\alpha\} $$

Then $\pi_\alpha$ induces a functor $\mathcal{A}^{w(3)} \to (\mathcal{A}/(A; \alpha))^{w(3)}$, which sends $\alpha$ on the identity of $s(\alpha)$, and which is the identity on the other cells of $\mathcal{A}_4$. We call this operation the *removal of a 3-cell with its defining 4-cell*.

**Definition 2.2.11.** Let $\alpha$ be a 4-cell in $\mathcal{A}_4^{w(3)}$. We define a 4-white-polygraph $\mathcal{A}(\alpha)$ by adding to $\mathcal{A}$ a 4-cell $\beta : s(\alpha) \equiv \mathbf{t}(\alpha)$. The inclusion of $\mathcal{A}$ into $\mathcal{A}(\alpha)$ induces a functor $\iota_\alpha : \mathcal{A}^{w(3)} \to \mathcal{A}(\alpha)^{w(3)}$. We call this operation the *adjunction of a superfluous 4-cell*.

**Definition 2.2.12.** Let $\beta \in \mathcal{A}_4$ such that there exists a 4-cell $\alpha \in (\mathcal{A} \setminus \{\beta\})^{w(3)}$ parallel to $\beta$. Let $\mathcal{A}/\beta$ be the 4-white-polygraph obtained by removing $\beta$ from $\mathcal{A}$. There exists a functor $\pi_\beta : \mathcal{A}^{w(3)} \to (\mathcal{A}/\beta)^{w(3)}$, that sends $\beta$ on $\alpha$ and which is the identity on the other cells of $\mathcal{A}$. We call this operation the *removal of a superfluous 4-cell*.

**Remark 2.2.13.** Note that, in those four cases, the set of 2-cells is left unchanged. In particular, let $\mathcal{A}$ be a 4-white-polygraph, and $\mathcal{B}$ a 4-white-polygraph constructed from $\mathcal{A}$ through a series of Tietze-transformations. If $S$ is a sub-set of $\mathcal{A}_2^w$, then $S$ still is a subset of $\mathcal{B}_2^w$.

**Proposition 2.2.14.** Let $\mathcal{A}$ be a 4-white-polygraph, $S$ a sub-set of $\mathcal{A}_2^w$, and $\mathcal{B}$ a 4-white-polygraph constructed from $\mathcal{A}$ through a series of Tietze-transformations.

If $\mathcal{B}^{w(3)}$ is $S$-coherent, then $\mathcal{A}^{w(3)}$ is $S$-coherent.

*Proof.* We check that if $\mathcal{B}$ is constructed from $\mathcal{A}$ through a Tietze-transformation, then the 3-white-categories presented by $\mathcal{A}$ and $\mathcal{B}$ are isomorphic.

Suppose now that $\mathcal{B}$ is $S$-coherent, and let $A, B \in \mathcal{A}_3^w$ be parallel 3-cells, whose source and target are in $S$. Since $\mathcal{B}^{w(3)}$ is $S$-coherent, the images of $A$ and $B$ in the 3-white-category presented by $\mathcal{B}$ are equal. Since it is isomorphic to the 3-white-category presented by $\mathcal{A}$, there exists a 4-cell $\alpha : A \equiv B \in \mathcal{A}_4^{w(3)}$, which proves that $\mathcal{A}$ is $S$-coherent. $\square$

## 2.3 Injective functors between white-categories

**Definition 2.3.1.** Let $\Sigma$ and $\Gamma$ be two $(n, k)$-polygraphs (resp. $(n, k)$-white-polygraphs), and let $F : \Sigma \to \Gamma$ be a morphism of $(n, k)$-polygraphs (resp. $(n, k)$-white-polygraphs). We say that $F$ is *injective* if for all $j \le n$ it induces an injective application from $\Sigma_n$ to $\Gamma_n$.

**Definition 2.3.2.** Let $\mathcal{C}$ and $\mathcal{D}$ be two $n$-white-categories, and let $F : \mathcal{C} \to \mathcal{D}$ be a morphism of $n$-white-categories. We say that $F$ is *injective* if for all $j \le n$ it induces an injective application from $\mathcal{C}$ to $\mathcal{D}$.

**Remark 2.3.3.** An injective morphism between $(n, k)$-polygraphs does not always induce an injective functor between the free $(n, k)$-categories they generate. To show that, we are going to define two 2-polygraphs $\Sigma$ and $\Gamma$, an injective morphism of 2-polygraphs $F : \Sigma \to \Gamma$, and two distinct 2-cells $f, g \in \Sigma^{*(1)}$ such that $F^{*(1)}(f) = F^{*(1)}(g)$.
Let $\Sigma$ be the following 2-polygraph:

$$ \Sigma_0 = \{*\} \quad \Sigma_1 = \{|: * \to *\} \quad \Sigma_2 := \{\emptyset, \Box: | \Rightarrow |\} $$

and $\Gamma$:

$$ \Gamma_0 = \{*\} \quad \Gamma_1 = \{|: * \to *\} \quad \Gamma_2 := \{\emptyset, \Box: | \Rightarrow |, \bullet: | \to 1_*\} $$

Let $F$ be the inclusion of $\Sigma$ into $\Gamma$, $f = \Box$ and $g = \Box$. They are distinct elements of $\Sigma_2^{* (1)}$. However using the exchange law, the following equality holds in $\Gamma_2^{* (1)}$, where $\bullet$ denotes the inverse of $\Box$:

$$ F(f) = \Box = \Box = \Box = \Box = \Box = \Box = F(g) $$

In what follows, we prove some sufficient conditions so that a morphism between two $(n, k)$-white-polygraphs induces an injective function between the $(n, k)$-categories they present. This is achieved in Proposition 2.3.8. This result will be used in Section 5.3.

To prove this result, we start by studying the more general case of an injective morphism $I$ between $(n, k)$-white-categories equipped with a cellular extension. When its image is closed by divisors (see Definition 2.3.5), we show a simple sufficient condition so that $I$ induces an injective $(n + 1)$-white-functor. We also show that the image of the $(n + 1)$-white-functor induced by $I$ is then automatically closed by divisors. Hence this hypothesis disappears when we go back to morphisms of $(n, k)$-white-polygraphs. In particular we show that every injective morphism of $n$-white-polygraphs induces an injective white-functor between $n$-white-categories.

For the rest of this section, we fix two $n$-white-categories equipped with cellular extensions $(C, \Sigma)$, $(C', \Sigma') \in \mathbf{WCat}^+$, and a morphism $I : (C, \Sigma) \to (C', \Sigma') \in \mathbf{WCat}^+$. That is, $I$ is given by an $n$-white-functor $I : C \to C'$ together with an application $I_{n+1} : \Sigma \to \Sigma'$ such that the following squares are commute:

$$ \begin{tikzcd} \Sigma \arrow[r, "I_{n+1}"] \arrow[d, "s"'] & \Sigma' \arrow[d, "s"'] \\ \Sigma \arrow[r, "I_{n+1}"] \arrow[d, "t"'] & \Sigma' \arrow[d, "t"'] \\ \Sigma \arrow[r, "I_{n+1}"] \arrow[d, "s"'] & \Sigma' \arrow[d, "s"'] \\ \Sigma \arrow[r, "I_{n+1}"] \arrow[d, "t"'] & \Sigma' \arrow[d, "t"'] \end{tikzcd} $$

We denote by $I^w$ (resp. $I^{w(n)}$) the $(n+1)$-white-functor $\mathcal{L}^w(I)$ (resp. $\mathcal{L}^{w(n)}(I)$). By definition, $I^w$ (resp. $I^{w(n)}$) is induced by an application from $E_{\Sigma}^T$ to $E_{\Sigma'}^T$ (resp. from $F_{\Sigma}^T$ to $F_{\Sigma'}^T$), that we again denote by $I^w$ (resp. $I^{w(n)}$).

Using their explicit definitions, the following properties of $I^w$ (resp. $I^{w(n)}$) hold:

* Any element of $E_{\Sigma}^T$ (resp. $F_{\Sigma}^T$) whose image is an $i$-composite is an $i$-composite.

* Any element of $E_{\Sigma}^T$ (resp. $F_{\Sigma}^T$) whose image is an identity is an identity.

* Any element of $E_{\Sigma}^T$ (resp. $F_{\Sigma}^T$) whose image is a $c_{u'A'v'}$ is a $c_{uAv}$.

* Any element of $F_{\Sigma}^T$ whose image by $I^{w(n)}$ is a $c_{u'A'v'}$ is a $c_{uAv}$.

**Lemma 2.3.4.** Assume that the application $I_{n+1}$ is injective, and that $I$ induces an injection on $C$. Then the applications $I^w : E_{\Sigma}^T \to E_{\Sigma'}^T$ and $I^{w(n)} : F_{\Sigma}^T \to F_{\Sigma'}^T$ are injective.
*Proof.* Let $a_1, a_2 \in E_{\Sigma}^T$ such that $I^w(a_1) = I^w(a_2)$. We reason by induction on the structure of $I^w(a_1)$.

If $I^w(a_1) = c_{u'A'v'}$, with $u', v' \in C'_1$ and $A' \in \Sigma'$. Then there are $u_1, v_1, u_2, v_2 \in C_1$ and $A_1, A_2 \in \Sigma$ such that $a_1 = c_{u_1A_1v_1}$ and $a_2 = c_{u_2A_2v_2}$, and so:

$$I(u_1) = I(u_2) = u' \quad I_{n+1}(A_1) = I_{n+1}(A_2) = A' \quad I(v_1) = I(v_2) = v'$$

Since $I$ and $I_{n+1}$ are injective, we get:

$$u_1 = u_2 \quad A_1 = A_2 \quad v_1 = v_2,$$

which proves that $a = b$.

If $I^w(a_1) = i_f$, with $f' \in C'_n$. Then there exist $f_1, f_2 \in C_n$ such that:

$$a_1 = i_{f_1} \quad a_2 = i_{f_2} \quad I(f_1) = f' \quad I(f_2) = f.$$

Since $I$ is injective, $f_1 = f_2$, and so $a_1 = a_2$.

If $I^w(a_1) = A' \star_i B'$, with $i < n$, and $A', B' \in E_{\Sigma'}^T$. Then there exist $A_1, A_2, B_1, B_2 \in E_{\Sigma}^T$ such that:

$$a_1 = A_1 \star_i B_1 \quad a_2 = A_2 \star_i B_2 \quad I^w(A_1) = I^w(A_2) = A' \quad I^w(B_1) = I^w(B_2) = B'$$

Using the induction hypothesis, we get that $A_1 = A_2$ and $B_1 = B_2$, and so $a_1 = a_2$.

In the case of $I^{w(n)}$, we reason as previously, and we have one more case to check: if $I^{w(n)}(a_1) = c_{u'\bar{A}'v'}$, with $u', v' \in C'_1$ and $A' \in \Sigma'$. Then there are $u_1, v_1, u_2, v_2 \in C_1$ and $A_1, A_2 \in \Sigma$ such that $a_1 = c_{u_1\bar{A}_1v_1}$ and $a_2 = c_{u_2\bar{A}_2v_2}$, and so:

$$I(u_1) = I(u_2) = u' \quad I_{n+1}(A_1) = I_{n+1}(A_2) = A' \quad I(v_1) = I(v_2) = v'$$

Using the injectivity of $I$ and $I_{n+1}$, we get:

$$u_1 = u_2 \quad A_1 = A_2 \quad v_1 = v_2,$$

and finally $a_1 = a_2$.

□

**Definition 2.3.5.** Let $C$ be an $n$-white-category, and $E$ be a subset of $C_n$. We say that $E$ is closed by divisors if, for any $f \in E$, if $f = f_1 \star_i f_2$, then $f_1$ and $f_2$ are in $E$.

**Lemma 2.3.6.** Assume the image of $I$ in $C_n$ is closed by divisors, and that $I$ and $I_{n+1}$ are injective.

Then, for every $a', b' \in E_{\Sigma'}^T$ such that $a' \equiv_{\Sigma'} b'$, and for every $a \in E_{\Sigma}^T$ such that $I^w(a) = a'$, there exists $b \in E_{\Sigma}^T$ such that

$$I^w(b) = b' \quad a \equiv_{\Sigma} b.$$

Assume moreover that the application $I_{n+1}$ is bijective and that $I$ is bijective on the 1-cells of $C$.

Then, for every $a', b' \in F_{\Sigma'}^T$ such that $a' \cong_{\Sigma'} b'$, and for every $a \in F_{\Sigma}^T$ such that $I^{w(n)}(a) = a'$, there exists $b \in F_{\Sigma}^T$ such that

$$I^{w(n)}(b) = b' \quad a \cong_{\Sigma} b.$$

*Proof.* To show the result on $I^w$ we reason by induction on the structure of $a'$.

If there exist $A', B', C', D' \in E_{\Sigma'}^T$, $0 < i_1 < i_2 \le n$ and $a \in E_{\Sigma}^T$ such that:

$$a' = (A' \star_{i_1} B') \star_{i_2} (C' \star_{i_1} D') \quad b' = (A' \star_{i_2} C') \star_{i_1} (B' \star_{i_2} D') \quad I^w(a) = a'$$

then, $a = (A \star_{i_1} B) \star_{i_2} (C \star_{i_1} D)$, with $A, B, C, D \in E_{\Sigma}^T$. Let $b := (A \star_{i_2} C) \star_{i_1} (B \star_{i_2} D)$: by construction, we have $I^w(b) = b'$ and $a \equiv_{\Sigma} b'$. The case where the roles of $a'$ and $b'$ are reversed is symmetrical.

If there exist $A', B', C' \in E_{\Sigma'}^T$, $0 < i \le n$ and $a \in E_{\Sigma}^T$ such that:

$$a' = (A' \star_i B') \star_i C' \quad b' = A' \star_i (B' \star_i C') \quad I^w(a) = a'$$

then, $a = (A \star_i B) \star_i C$, with $A, B, C \in E_{\Sigma}^T$. Let $b := A \star_i (B \star_i C)$: By construction, we have $I^w(b) = b'$ and $a \equiv_{\Sigma} b'$. The case where the roles of $a'$ and $b'$ are reversed is symmetrical.
If there exist $A' \in E_{\Sigma}^T$, $f' \in C'_n$ and $a \in E_{\Sigma}^T$ such that

$$a' = i_{f'} \star_n A' \quad b' = A' \quad I^w(a) = a',$$

then $a = i_f \star_n A$, with $f \in C_n$ and $A \in E_{\Sigma}^T$. Let $b := A'$: by construction, we have $I^w(b) = b'$ and $a \equiv_{\Sigma} b$. If there exist $A' \in E_{\Sigma}^T$, $f' \in C'_n$ and $a \in E_{\Sigma}^T$ such that

$$a' = A' \quad b' = i_{f'} \star_n A' \quad I^w(a) = a',$$

let $b := i_{s(A)} \star_n a$. Since $b'$ is well typed, we have $f' = s(A')$, hence $I(s(A)) = s(I^w(A)) = s(A') = f'$, and so $I^w(b) = b'$ and $a \equiv_{\Sigma} b$. The case of the right-unit is symmetrical.

If there are $f'_1, f'_2 \in C'_n$, $i < n$ and $a \in E_{\Sigma}^T$ such that:

$$a' = i_{f'_1} \star_i f'_2 \quad b' = i_{f'_1 \star_i f'_2} \quad I^w(a) = a,$$

then $a = i_{f_1} \star_i f_2$, with $f_1, f_2 \in C_n$. Let $b := i_{f_1 \star_i f_2}$: by construction, we have $I^w(b) = b'$ and $a \equiv_{\Sigma} b$. If there are $f'_1, f'_2 \in C'_n$, $i < n$ and $a \in E_{\Sigma}^T$ such that:

$$a' = i_{f'_1 \star_i f'_2} \quad b' = i_{f'_1 \star_i f'_2} \quad I^w(a) = a'$$

then $a = i_f$, with $f \in C_n$. Since the image of $I$ in $C_n$ is closed by divisors, there exist $f_1, f_2 \in C_n$ such that

$$I(f_1) = f'_1 \quad I(f_2) = f'_2 \quad f = f_1 \star_i f_2.$$

Let us define $b' := i_{f_1} \star_i f_2$: By construction, we have $I^w(b) = b'$ and $a \equiv_{\Sigma} b$.

If there are $A'_1, A'_2, B' \in E_{\Sigma'}^T$, $i < n$ and $a \in E_{\Sigma}^T$ such that:

$$a' = A'_1 \star_i B' \quad A'_1 \equiv_{\Sigma'} A'_2 \quad b' = A'_2 \star_i B' \quad I^w(a) = a'$$

then $a = A_1 \star_i B$, with $A_1, B \in E_{\Sigma}^T$. Using the induction hypothesis, there exist $A_2 \in E_{\Sigma}^T$ such that $I^w(A_2) = A'_2$ and $A_1 \equiv_{\Sigma} A_2$. Let us define $b := A_2 \star_i B$: by construction, we have $I^w(b) = b'$ and $a \equiv_{\Sigma} b$. The last case is symmetric.

In the case of $I^w(n)$, we reason as previously, and we have two more cases to check. If there exist $u', v' \in C'_1$, $A \in \Sigma'$ and $a \in F_{\Sigma}^T$ such that:

$$a' = c_{u'A'v'} \star_n c_{u'\bar{A}'v'} \quad b' = i_{u's(A')v'} \quad I^{w(n)}(a) = a'$$

then $a = c_{u_1A_1v_2} \star_n c_{u_2\bar{A}_2v_2}$, with $u_1, u_2, v_1, v_2 \in C_1$ and $A_1, A_2 \in \Sigma$ such that:

$$I(u_1) = I(u_2) = u' \quad I(v_1) = I(v_2) = v' \quad I_{n+1}(A_1) = I_{n+1}(A_2) = A.$$

Let $b := i_{u_1s(A_1)v_1}$. Since $I$ and $I_{n+1}$ are injective, we have $I^w(b) = b'$ and $a \cong_{\Sigma} b$.

If there exist $u', v' \in C'_1$, $A \in \Sigma'$ and $a \in F_{\Sigma}^T$ such that:

$$a' = i_{u's(A')v'} \quad b' = c_{u'A'v'} \star_n c_{u'\bar{A}'v'} \quad I^{w(n)}(a) = a'$$

Then $a = i_f$, with $f \in C_n$. Let $b' := c_{uAv} \star_i c_{u\bar{A}v}$, with $u = I^{-1}(u')$, $v = I^{-1}(v')$ and $A = I_{n+1}^{-1}(A')$: by construction, we have $I^w(b) = b'$ and $a \cong_{\Sigma} b$. The final case is symmetrical. $\square$

**Lemma 2.3.7.** Assume that $I_{n+1}$ and $I$ are injective, and that the image of $I$ in $C_n$ is closed by divisors. Then the functor $I^w: L^w(C, \Sigma) \to L^w(C', \Sigma')$ is injective, and its image is closed by divisors.

Assume moreover that $I_{n+1}$ is bijective, and that $I$ is bijective on the 1-cells of $C$. Then the functor $I^{w(n)}: L^{w(n)}(C, \Sigma) \to L^{w(n)}(C', \Sigma')$ is injective and its image is closed by divisors.

*Proof.* Let $f_1, f_2 \in L^w(C, \Sigma)$ and $a_1, a_2 \in E_{\Sigma}^T$ such that:

$$I^w(f_1) = I^w(f_2) \quad [a_1] = f_1 \quad [a_2] = f_2.$$

Then $[I^w(a_1)] = [I^w(a_2)]$, that is $I^w(a_1) \equiv_{\Sigma'}^* I^w(a_2)$. Hence by definition, there exist $n > 0$ and $t'_1, \dots, t'_n \in E_{\Sigma'}^T$ such that:

$$t'_1 = I^w(a_1) \quad t'_i \equiv_{\Sigma'} t'_{i+1} \quad t'_n = I^w(a_2).$$
Applying Lemma 2.3.6 successively, we get $t_1, \dots, t_n \in E_{\Sigma'}^T$ such that:

$$t_1 = a_1 \qquad t_i \equiv_{\Sigma} t_{i+1} \qquad I^{\mathbf{w}}(t_i) = t_i'$$

In particular $a_1 \equiv_{\Sigma}^* t_n$ and $I^{\mathbf{w}}(t_n) = t'_n = I^{\mathbf{w}}(a_2)$. Using Lemma 2.3.4, this implies that $t_n = a_2$, and so $a_1 \equiv_{\Sigma}^* a_2$, which proves that $f_1 = [a_1] = [a_2] = f_2$.

It remains to show that the image of $I^{\mathbf{w}}$ is closed by divisors. Let $f', f'_1, f'_2 \in L^{\mathbf{w}}(C', \Sigma')$ and $i \le n$ such that $f' = f'_1 \star_i f'_2$, and assume that there is an $f \in L^{\mathbf{w}}(C', \Sigma')$ such that $I^{\mathbf{w}}(f) = f'$. Let $a \in E_{\Sigma}^T$ and $b'_1, b'_2 \in E_{\Sigma'}^T$ such that:

$$[a] = f \qquad [b'_1] = f'_1 \qquad [b'_2] = f'_2.$$

In particular, we have $I^{\mathbf{w}}(a) \equiv_{\Sigma'}^* b'_1 \star_i b'_2$. Using both Lemmas 2.3.4 and 2.3.6 as before, we get an element $b \in E_{\Sigma}^T$ such that:

$$a \equiv_{\Sigma}^* b \qquad I^{\mathbf{w}}(b) = b'_1 \star_i b'_2.$$

Since the image of $I^{\mathbf{w}}$ is closed by divisors, there exists $b_1, b_2 \in E_{\Sigma}^T$ such that $b = b_1 \star_i b_2$. Let $f_1 := [b_1]$ and $f_2 := [f_2]$; by construction we have:

$$I^{\mathbf{w}}(f_1) = f'_1 \qquad I^{\mathbf{w}}(f_2) = f'_2 \qquad f_1 \star_i f_2 = f.$$

The case of $I^{\mathbf{w}}(n)$ is identical, the only difference lying in the hypothesis needed to apply Lemma 2.3.6. $\square$

**Proposition 2.3.8.** Let $\Sigma$ and $\Gamma$ be two $(n, k)$-white-polygraphs and $I : \Sigma \to \Gamma$ be an injective morphism of $(n, k)$-polygraphs. Then for every $j \le k$ the functor $I_j^{\mathbf{w}} : \Sigma_j^{\mathbf{w}} \to \Gamma_j^{\mathbf{w}}$ is injective, and its image is closed by divisors.

Assume moreover that $I_0$ and $I_1$ are bijections, and that for every $j > k$ the application $I_j : \Sigma_j \to \Gamma_j$ is bijective. Then for every $j$ the functor $I_j^{\mathbf{w}}(k) : \Sigma_j^{\mathbf{w}}(k) \to \Gamma_j^{\mathbf{w}}(k)$ is injective, and its image is closed by divisors.

*Proof.* We reason by induction on $j$. The case $j = 0$ is true by hypothesis.

Let $1 \le j \le k$. By hypothesis, the application $I_j$ is injective, and by induction hypothesis, the functor $I_j^{\mathbf{w}}$ is injective with image closed by divisors. Hence $I_j$ satisfies the hypothesis of Lemma 2.3.7, and $I_j^{\mathbf{w}}$ is injective with image closed by divisors.

Let $j > k$. Again, using the hypothesis and induction hypothesis, we get that $I_j$ satisfies the hypotheses of Lemma 2.3.7. Hence $I_j^{\mathbf{w}}(k)$ is injective and its image is closed by divisors. $\square$

In what follows, we use the fact that the image of a functor generated by a morphism of polygraphs is closed by divisors in order to prove a characterisation of the image of such a functor.

**Definition 2.3.9.** Let $C, D$ be two $n$-white-categories, $F : C \to D$ be an $n$-functor and $f$ be an $n$-cell of $D$. We say that $F$ $k$-discriminates $f$ if the following are equivalent:

1. The $k$-source of $f$ is in the image of $F$.

2. The $k$-target of $f$ is in the image of $F$.

3. The $n$-cell $f$ is in the image of $F$.

Given a subset $D$ of $D_n$, we say that $F$ is $k$-discriminating on $D$ if for every $n$-cell $f$ in $D$, $F$ $k$-discriminates $f$.

**Lemma 2.3.10.** Assume that the image of $I$ is closed by divisors, that the application $I_n$ is injective, and that $I$ is $n$-discriminating on $\Sigma'$.

Then, $I^{\mathbf{w}}$ (resp. $I^{\mathbf{w}}(n)$) is $n$-discriminating on $L^{\mathbf{w}}(C', \Sigma')$ (resp. $L^{\mathbf{w}}(n)(C', \Sigma')$).

*Proof.* Let us start with $I^{\mathbf{w}}$. Let $E$ be the set all $(n+1)$-cells of $L^{\mathbf{w}}(C', \Sigma')$ which $I^{\mathbf{w}}$ discriminates. Let us show that $E = L^{\mathbf{w}}(C', \Sigma')$. Since $I^{\mathbf{w}}$ commutes with the source and target applications, the implications $(3) \Rightarrow (1)$ and $(3) \Rightarrow (2)$ hold for any cell in $L^{\mathbf{w}}(C', \Sigma')$. So in order to show that a cell is in $E$, it remains to show that it verifies the implications $(1) \Rightarrow (3)$ and $(2) \Rightarrow (3)$.
The set $E$ contains all units. Indeed, let $A' = 1_{f'}$, with $f' \in C'$. If $\mathbf{s}(A') = f'$ is in the image of $I^\mathbf{w}$, there exists $f \in C$ such that $I(f) = f'$. Let us define $A = 1_f \in L^\mathbf{w}(C, \Sigma)$: by construction we have $I^\mathbf{w}(A) = 1_{I(f)} = 1_{f'} = A'$, hence the implication (1) $\Rightarrow$ (3) holds for $A'$. Moreover since $\mathbf{t}(A') = \mathbf{s}(A')$, the implication (2) $\Rightarrow$ (3) also holds for $A$.

The set $E$ contains all cells of length 1. Indeed, given such a cell $A'$, there exist $f'_k, g'_k \in C'_k$ and $A'_0 \in \Sigma'$ such that

$$A' = f'_n \star_{n-1} (f'_{n-1} \star_{n-2} \dots \star_2 (f'_1 A'_0 g'_1) \star_2 \dots \star_{n-2} g'_{n-1}) \star_{n-1} g'_n.$$

Let $A'_k := f'_k \star_{k-1} (f'_{k-1} \star_{k-2} \dots \star_2 (f'_1 A'_0 g'_1) \star_2 \dots \star_{k-2} g'_{k-1}) \star_{k-1} g'_k$. Suppose that the source (resp. target) of $A'$ is in the image of $I$, and let us show that $A'$ is in the image of $I^\mathbf{w}$. Since the image of $I$ is closed by divisors, we get first that $f'_n, g'_n$ and $\mathbf{s}(A'_{n-1})$ (resp. $\mathbf{t}(A'_{n-1})$) are in the image of $I$. By iterating this reasoning, we get that, for all $i, f'_i, g'_i$ and $\mathbf{s}(A'_{i-1})$ (resp. $\mathbf{t}(A'_{i-1})$) are in the image of $I$. Since $I^\mathbf{w}$ discriminates $\Sigma'$, there exist $f_k, g_k \in C_k$ and $A_0 \in \Sigma$ such that:

$$I(f_k) = f'_k \qquad I(g_k) = g'_k \qquad I_{n+1}(A_0) = A'_0.$$

By induction on $k$ we show that $A_k := f_k \star_{k-1} A_{k-1} \star_{k-1} g_k$ is well defined and that $I^\mathbf{w}(A_k) = A'_k$. Indeed, assume that it is true at rank $k-1$. Then we have the equalities:

$$I(\mathbf{t}(f_k)) = \mathbf{t}(f'_k) = \mathbf{s}_{k-1}(A'_{k-1}) = I(\mathbf{s}_{k-1}(A_{k-1})) \qquad I(\mathbf{t}_{k-1}(A_{k-1})) = \mathbf{t}_{k-1}(A'_{k-1}) = \mathbf{s}(g'_k) = I(\mathbf{s}(g_k))$$

Using the injectivity of $I$ we get that $\mathbf{t}(f_k) = \mathbf{s}_{k-1}(A_{k-1})$ and $\mathbf{t}_{k-1}(A_{k-1}) = \mathbf{s}(g_k)$, which shows that $A_k$ is well defined, and finally:

$$I^\mathbf{w}(A_k) = f'_k \star_{k-1} A'_{k-1} \star_{k-1} g'_k = A'_k.$$

In particular, we have $A'_n = I^\mathbf{w}(A_n)$.

The set $E$ is stable by $n$-composition. Indeed let $A', B' \in E$, and assume that the source of $A' \star_n B'$ is in the image of $I$. Let us show that $A' \star_n B'$ is in the image of $I^\mathbf{w}$. The source of $A' \star_n B'$ is none other that the one of $A'$. Since $A'$ is in $E$, there exists $A \in \mathcal{L}^\mathbf{w}(C, \Sigma)$ such that $I^\mathbf{w}(A) = A'$. Hence the source of $B'$ is in the image of $I$, and since $B' \in E$, there exists $B \in \mathcal{L}^\mathbf{w}(C, \Sigma)$ such that $I^\mathbf{w}(B) = B'$. Moreover we have $I(\mathbf{t}(A)) = \mathbf{t}(A') = \mathbf{s}(B') = I(\mathbf{s}(B))$, so using the injectivity of $I$ we get $\mathbf{t}(A) = \mathbf{s}(B)$. Hence the cell $A \star_n B$ is well defined and satisfies:

$$I^\mathbf{w}(A \star_n B) = I^\mathbf{w}(A) \star_n I^\mathbf{w}(B) = A' \star_n B.$$

The case where the target of $A' \star_n B'$ is in the image of $I$ is symmetrical.

This concludes the proof for $I^\mathbf{w}$. Concerning $I^\mathbf{w}(n)$, the reasoning is the same except that we also have to show that $E$ is stable under inversion. Indeed let $A' \in E$ and assume that the source (resp. target) of $(A')^{-1}$ is in the image of $I$. Then the target (resp. source) of $A'$ is in the image of $I$ and since $A'$ is in $E$, there exists $A \in \mathcal{L}^\mathbf{w}(n)(C, \Sigma)$ such that $I^\mathbf{w}(n)(A) = A'$, and so $I^\mathbf{w}(n)(A^{-1}) = (A')^{-1}$. $\square$

**Proposition 2.3.11.** Let $\Sigma$ and $\Gamma$ be two $(n, k)$-white-polygraphs, and $I: \Sigma \to \Gamma$ be a morphism of polygraphs. Let $k_0$ such that for every $j > k_0$, $I_j$ is a bijection.

Assume that $I$ satisfies the hypothesis of Proposition 2.3.8, and that, for every $j > k_0$, $I_j$ is $k_0$-discriminating on $\Gamma_j$. Then for every $j \ge k_0$, $I_j^{\mathbf{w}(k)}$ is $k_0$-discriminating on $\Gamma_j^{\mathbf{w}(k)}$.

*Proof.* Since $I$ satisfies the hypotheses of Proposition 2.3.8, we know that for every $j$, the functor $I_j^{\mathbf{w}(k)}$ is injective, and that its image is closed by divisors.

We reason by induction on $j > k_0$. For $j = k_0 + 1$, the result is a direct application of Lemma 2.3.10.

Let $j > k_0 + 1$: let us show that $I_j^{\mathbf{w}(k)}$ is $(j-1)$-discriminating on $\Gamma_j$. Let $A \in \Gamma_j$. If $\mathbf{s}(A)$ (resp. $\mathbf{t}(A)$) is in the image of $I_j^{\mathbf{w}(k)}$ then in particular, the $k_0$-source (resp. $k_0$-target) of $A$ is in the image of $I_{k_0}^{\mathbf{w}(k)}$. Since $I_j^{\mathbf{w}(k)}$ is $k_0$-discriminating on $\Gamma_j$, $A$ is in the image of $I_j^{\mathbf{w}(k)}$. Hence we can use Lemma 2.3.10, and we get that $I_j^{\mathbf{w}(k)}$ is $(j-1)$-discriminating on $\Gamma_j^{\mathbf{w}(k)}$. Let $A \in \Gamma_j^{\mathbf{w}(k)}$. If its $k_0$-source (resp. $k_0$-target) is in the image of $I_{k_0}^{\mathbf{w}(k)}$ then, by induction hypothesis, the source (resp. target) of $A$ is in the image of $I_{j-1}^{\mathbf{w}(k)}$, and so $A$ is in the image of $I_j^{\mathbf{w}(k)}$, which proves that $I_j^{\mathbf{w}(k)}$ is $k_0$-discriminating. $\square$
# 3 Application to the coherence of pseudonatural transformations

We now study the coherence problem successively for bicategories, pseudofunctors and pseudonatural transformations. In Section 3.1, we start by recalling the usual definition of bicategories (see [2]). We then give an alternative description of bicategories in terms of algebras over a certain 4-polygraph **BiCat**[C], and show that the two definitions coincide. The coherence problem for bicategories is now reduced to showing the 3-coherence of **BiCat**[C], and we use the techniques introduced in the previous section (especially Theorems 1.2.4 and 1.4.4) to conclude. In Section 3.2 and 3.3, we apply the same reasoning to pseudofunctors and pseudonatural transformations. However in the case of pseudonatural transformations, we get a (4,3)-polygraph **PNTrans**[f, g] which is not 3-confluent, and so we cannot directly apply Theorem 1.4.4. The proof of the coherence theorem for pseudonatural transformations will take place in Section 4 and will make use of Theorem 1.4.9.

## 3.1 Coherence for bicategories

Let **Cat** be the category of (small) categories. We denote by $\top$ the terminal category in **Cat**. Let **sCat** be the 3-category with one 0-cell, (small) categories as 1-cells, functors as 2-cells, and natural transformations as 3-cells, where 0-composition is given by the cartesian product, 1-composition by functor composition, and 2-composition by composition of natural transformations.

**Definition 3.1.1.** A bicategory $\mathcal{B}$ is given by:

* A set $\mathcal{B}_0$.

* For every $a, b \in \mathcal{B}_0$, a category $\mathcal{B}(a, b)$. The objects and arrows of $\mathcal{B}(a, b)$ are respectively called the 1-cells $\mathcal{B}$ and 2-cells of $\mathcal{B}$.

* For every $a, b, c \in \mathcal{B}_0$, a functor $\star_{a,b,c} : \mathcal{B}(a, b) \times \mathcal{B}(b, c) \to \mathcal{B}(a, c)$.

* For every $a \in \mathcal{B}_0$, a functor $I_a : \top \to \mathcal{B}(a, a)$, that is to say a 1-cell $I_a : a \to a$.

* For every $a, b, c, d \in \mathcal{B}_0$, a natural isomorphism $\alpha_{a,b,c,d}$:

<figure><img src="image_15.png" /></figure>

of components $\alpha_{f,g,h} : (f \star g) \star h \Rightarrow f \star (g \star h)$, for every triple $(f, g, h) \in \mathcal{B}(a, b) \times \mathcal{B}(b, c) \times \mathcal{B}(c, d)$.

* For every $a, b \in \mathcal{B}_0$, natural isomorphisms $R_{a,b}$ and $L_{a,b}$:

<figure><img src="image_16.png" /></figure>

of components $L_f : I_a \star f \Rightarrow f$ and $R_f : f \star I_b \Rightarrow f$ for every 1-cell $f \in \mathcal{B}(a, b)$.

This data must also satisfy the following axioms:
• For every composable 2-cells $f, g, h, i$ in $\mathcal{B}$:

<figure><img src="image_17.png" /></figure>

• For every couple $(f, g) \in \mathcal{B}(a, b) \times \mathcal{B}(b, c)$:

<figure><img src="image_18.png" /></figure>

**Definition 3.1.2.** Let $\mathbf{C}$ be a set. Let us describe dimension by dimension a 4-polygraph $\mathbf{BiCat}[\mathbf{C}]$, so that bicategories correspond to algebras on $\mathbf{BiCat}[\mathbf{C}]$, that is to 4-functors from $\mathbf{BiCat}[\mathbf{C}]$ to $\mathbf{sCat}$ (see Proposition 3.1.4).

**Dimension 0:** Let $\mathbf{BiCat}[\mathbf{C}]_0$ be the set $\mathbf{C}$.

**Dimension 1:** The set $\mathbf{BiCat}[\mathbf{C}]_1$ contains, for every $a, b \in \mathbf{C}$, a 1-cell $a|_b : a \to b$.

**Dimension 2:** The set $\mathbf{BiCat}[\mathbf{C}]_2$ contains the following 2-cells:

• For every $a, b, c \in \mathbf{C}$, a 2-cell $\Uparrow_{a,b,c} : a|_b|_c \Rightarrow a|_c$.

• For every $a \in \mathbf{C}$, a 2-cell $\mathcal{Q}_a : 1_a \Rightarrow a|_a$.

Note that the indices are redundant with the source of a generating 2-cell. In what follows, we will therefore omit them when the context is clear. For example, the 2-cell $\Uparrow$ of source $a|_b|_c$ designates the composite $(a|_b\Uparrow_{b,c,d}) \star_1 \Uparrow_{a,b,d}$. We will use the same notation for higher-dimensional cells.

**Dimension 3:** The set $\mathbf{BiCat}[\mathbf{C}]_3$ contains the following 3-cells:

• For every $a, b, c, d \in \mathbf{C}$, a 3-cell $\Uparrow_{a,b,c,d} : \Uparrow \Uparrow \Uparrow \Uparrow$ of 1-source $a|_b|_c|_d$.

• For every $a, b \in \mathbf{C}$, 3-cells $\mathcal{D}_{a,b} : \mathcal{Q} \Uparrow \Uparrow \Uparrow \Uparrow \Rightarrow |$ and $\mathcal{D}_{a,b} : \mathcal{Q} \Uparrow \Uparrow \Uparrow \Uparrow \Rightarrow |$ of 1-source $a|_b$.
**Dimension 4:** The set $\mathbf{BiCat}[\mathbf{C}]_4$ contains the following 4-cells:

• For every $a, b, c, d, e \in \mathbf{C}$, a 4-cell $\mathcal{Y}_{a,b,c,d,e}$ of 1-source $a|b|c|d|e$.

<figure><img src="image_19.png" /></figure>

• For every $a, b, c \in \mathbf{C}$, a 4-cell $\mathcal{Y}_{a,b,c}$ of 1-source $a|b|c$.

<figure><img src="image_20.png" /></figure>

**Definition 3.1.3.** We denote by $Alg(\mathbf{BiCat})$ the set of all couples $(\mathbf{C}, \Phi)$:

• where $\mathbf{C}$ is a set,

• where $\Phi$ is a functor from $\overline{\mathbf{BiCat}}[\mathbf{C}]$ to $\mathbf{sCat}$.

**Proposition 3.1.4.** There is a one-to-one correspondence between (small) bicategories and $Alg(\mathbf{BiCat})$.

*Proof.* The correspondence between a bicategory $\mathcal{B}$ and an algebra $(\mathbf{C}, \Phi)$ over $\mathbf{BiCat}$ is given by:

• At the level of sets: $\mathbf{C} = \mathcal{B}_0$.

• For every $a, b \in \mathcal{B}_0$, $\Phi(a|b) = \mathcal{B}(a, b)$.

• For every $a, b, c \in \mathcal{B}_0$, $\Phi(\mathcal{Y}_{a,b,c}) = \star_{a,b,c}$.

• For every $a \in \mathcal{B}_0$, $\Phi(\mathcal{Q}_a) = I_a$.

• For every $a, b, c, d \in \mathcal{B}_0$, $\Phi(\mathcal{Y}_{a,b,c,d}) = \alpha_{a,b,c,d}$.

• For every $a, b \in \mathcal{B}_0$, $\Phi(\mathcal{P}_{a,b}) = R_{a,b}$ and $\Phi(\mathcal{D}_{a,b}) = L_{a,b}$.

• The axioms that a bicategory must satisfy correspond to the fact that $\Phi$ is compatible with the quotient by the 4-cells $\mathcal{Y}_{a,b,c,d}$ and $\mathcal{Q}_{a,b}$.

This correspondence between the structures of bicategory and of algebra over $\mathbf{BiCat}$ is summed up by the following table:
<table><thead><tr><th colspan="2">Bicategory</th><th colspan="2">Alg(BiCat)</th></tr></thead><tbody><tr><td>Sets</td><td>B<sub>0</sub></td><td>C</td><td>0-cells</td></tr><tr><td>Categories</td><td>B(<u>-</u>, <u>-</u>)</td><td>u, v, w</td><td>1-cells</td></tr><tr><td>Functors</td><td>&star;, I</td><td>u, v, w</td><td>2-cells</td></tr><tr><td>Natural transformations</td><td>&alpha;, L, R</td><td>u, v, w</td><td>3-cells</td></tr><tr><td>Equalities</td><td>(1) (2)</td><td>u, v, w</td><td>4-cells</td></tr></tbody></table>

<figure><img src="image_21.png" /></figure>

<figure><img src="image_22.png" /><figcaption>Table 1: Correspondence for bicategories</figcaption></figure>

<figure><img src="image_23.png" /></figure>

We are going to show the coherence theorem for bicategories, using Theorem 1.4.4.

**Proposition 3.1.5.** For every set $C$, the 4-polygraph $\mathbf{BiCat}[C]$ 3-terminates.

*Proof.* In order to apply Theorem 1.2.4 we construct two functors $X_C : \mathbf{BiCat}[C]_2^* \to \mathbf{sOrd}$ and $Y_C : (\mathbf{BiCat}[C]_2^*)^{\mathbf{co}} \to \mathbf{sOrd}$ by setting, for every $a, b \in C$:

$$X_C(a_b) = Y_C(a_b) = \mathbb{N}^*$$

and, for every $i, j \in \mathbb{N}^*$:

$$X_C(\Uparrow)[i, j] = i + j, \quad X_C(\varnothing) = 1, \quad Y_C(\Uparrow)[i] = (i, i).$$

We now define an $(X_C, Y_C, \mathbb{N})$-derivation $d_C$ on $\mathbf{BiCat}[C]_2^*$ by setting, for every $i, j, k \in \mathbb{N}^*$:

$$d_C(\Uparrow)[i, j, k] = i + k + 1, \quad d_C(\varnothing)[i] = i,$$

It remains to show that the required inequalities are satisfied. Concerning $X_C$ and $Y_C$, we have for every $i, j, k \in \mathbb{N}^*$:

$$X_C(\Uparrow)[i, j, k] = i + j + k \ge i + j + k = X_C(\Uparrow)[i, j, k]$$

$$X_C(\varnothing)[i] = i + 1 \ge i = X_C(\varnothing)[i] \quad X_C(\Uparrow)[i] = i + 1 \ge i = X_C(\varnothing)[i]$$

$$Y_C(\Uparrow)[i] = (i, i, i) \ge (i, i, i) = Y_C(\Uparrow)[i]$$

$$Y_C(\varnothing)[i] = i \ge i = Y_C(\varnothing)[i] \quad Y_C(\Uparrow)[i] = i \ge i = Y_C(\varnothing)[i].$$

Concerning $d_C$, we have for every $i, j, k, l \in \mathbb{N}^*$:

$$d_C(\Uparrow)[i, j, k, l] = 2i + j + 2l + 2 > i + j + 2l + 2 = d_C(\Uparrow)[i, j, k, l]$$

$$d_C(\varnothing)[i, j] = 2j + 2 > 0 = d_C(\varnothing)[i, j] \quad d_C(\Uparrow)[i, j] = i + 2j + 1 > 0 = d_C(\varnothing)[i, j].$$

<figure><img src="image_24.png" /></figure>

The following Theorem is a rephrasing of Mac Lane's coherence Theorem ([13]) in our setting.

**Theorem 3.1.6.** Let $C$ be a set.

The 4-polygraph $\mathbf{BiCat}[C]$ is 3-convergent and the free (4, 2)-category $\mathbf{BiCat}[C]^{*(2)}$ is 3-coherent.

*Proof.* We already know that $\mathbf{BiCat}[C]$ is 3-terminating. Using Proposition 1.3.8 and Theorem 1.4.4, it remains to show that every critical pair admits a filling.

There are five families of critical pairs, of sources:

<figure><img src="image_25.png" /></figure>

The first two families are filled by the 4-cells $\Uparrow$ and $\Uparrow \Uparrow$, whereas the last three are filled by 4-cells $\omega_i \in \mathbf{BiCat}[C]_4^{*(2)}$, which are constructed in a similar fashion as in the case of monoidal categories (see Proposition 3.5 in [7]).

<figure><img src="image_26.png" /></figure>
<figure><img src="image_27.png" /></figure>

**Definition 3.2.3.** Let Alg($\mathbf{PFonct}$) be the set of all tuples $(C, D, f, \Phi)$:

* where $C$ and $D$ are sets,

* where $f$ is an application from $C$ to $D$,

* where $\Phi$ is a functor from $\overline{\mathbf{PFonct}}[f]$ to $\mathbf{sCat}$ such that, for every $c \in C$ the following equality holds:

$$ \Phi(c|_{f(c)}) = \top $$

**Remark 3.2.4.** Let $f: C \to D$ be an application. Since $\mathbf{BiCat}[C]$ (resp. $\mathbf{BiCat}[D]$) is a sub-4-polygraph of $\mathbf{PFonct}[f]$, every functor $\Phi: \overline{\mathbf{PFonct}}[f] \to \mathbf{sCat}$ induces by restriction two functors:

$$ \Phi_O : \overline{\mathbf{BiCat}}[C] \to \mathbf{sCat} $$

$$ \Phi_\bullet : \overline{\mathbf{BiCat}}[D] \to \mathbf{sCat} $$

**Proposition 3.2.5.** *Pseudofunctors between (small) categories are in one to one correspondence with elements of Alg($\mathbf{PFonct}$).*

*Proof.* The proof is similar to the case of bicategories, using the following correspondence table:

<table><thead><tr><th colspan="2">Pseudofunctors</th><th>Alg(<b>PFonct</b>)</th></tr></thead><tbody><tr><td>Source and target</td><td><i>B</i> and <i>B'</i></td><td>(<i>C</i>, <i>Φ<sub>O</sub></i>) and (<i>D</i>, <i>Φ<sub>●</sub></i>)</td></tr><tr><td>Function</td><td><i>F</i><sub>0</sub></td><td><i>f</i></td></tr><tr><td>Functors</td><td><i>F</i></td><td></td></tr><tr><td>Natural transformations</td><td>ψ, φ</td><td>2-cells</td></tr><tr><td>Equalities</td><td>(3) (4) (5)</td><td>3-cells</td></tr><tr><td></td><td></td><td>4-cells</td></tr></tbody></table>

<figure><img src="image_28.png" /><figcaption>Table 2: Correspondence for pseudofunctors</figcaption></figure>

<figure><img src="image_29.png" /></figure>

**Proposition 3.2.6.** For every sets $C, D$ and every application $f: C \to D$, the 4-polygraph $\mathbf{PFonct}[f]$ 3-terminates.

*Proof.* In order to apply Theorem 1.2.4, we define functors $X_f: \mathbf{PFonct}[f]_2^* \to \mathbf{sOrd}$ and $Y_f: (\mathbf{PFonct}[f]_2^*)^{\mathrm{co}} \to \mathbf{sOrd}$ as extensions of the functors $X_C, X_D, Y_C$ and $Y_D$ from Proposition 3.1.5, and by setting for every $a \in C$:

$$ X_f(a|_{f(a)}) = Y_f(a|_{f(a)}) = \top, $$

where $\top$ is the terminal ordered set, and for every $i \in \mathbb{N}^*$:

$$ X_f(\Box_0^i)[i] = i \quad Y_f(\Box_0^i)[i] = 2i + 1. $$

We now define an $(X_f, Y_f, \mathbb{N})$-derivation $d_f$ on $\mathbf{PFonct}[f]_2^*$ as an extension of $d_C$, by setting for every $i, j, k \in \mathbb{N}^*$:

$$ d_f(\Box_0^i)[i, j, k] = i + k \quad d_f(\Box_0^j)[i] = i \quad d_f(\Box_0^k)[i, j] = i + j + 1 $$

It remains to show that the inequalities required to apply Theorem 1.2.4 are satisfied. Since $X_f$ (resp. $Y_f$) extends $X_C$ and $X_D$ (resp. $Y_C$ and $Y_D$), the only inequalities that need to be checked are those corresponding to the 3-cells $\Box_0^i$ and $\Box_0^j$. Indeed for every $i, j \in \mathbb{N}^*$, we have:

$$ X_f(\Box_0^i) = 1 \ge 1 = X_f(\Box_0^j) $$
$$
\begin{align*}
X_f(\text{[Diagram]})[i, j] &= i + j \geq i + j = X_f(\text{[Diagram]})[i, j] \\
Y_f(\text{[Diagram]})[i] &= (2i + 1, 2i + 1) \geq (2i + 1, 2i + 1) = Y_f(\text{[Diagram]})[i]
\end{align*}
$$

Concerning $d_f$, the 3-cells from **BiCat[C]** have already been checked in Proposition 3.1.5. For the other 3-cells, we have, for every $i, j, k \in \mathbb{N}^*$:

$$
d_f(\text{[Diagram]})[i, j] = 2j + 1 > 0 = d_f(\text{[Diagram]})[i, j] \qquad d_f(\text{[Diagram]})[i, j] = i + 2j > 0 = d_f(\text{[Diagram]})[i, j]
$$

$$
d_f(\text{[Diagram]})[i] = 3i + 2 > i = d_f(\text{[Diagram]})
$$

$$
d_f(\text{[Diagram]})[i, j, k] = 2i + j + 3k + 3 > 2i + j + 3k + 2 = d_f(\text{[Diagram]})[i, j, k].
$$

□

**Theorem 3.2.7.** Let C and D be sets, and f : C → D an application.

The 4-polygraph **PFonct**[f] is 3-convergent and the free (4,2)-category **PFonct**[f]⁽²⁾ is 3-coherent.

*Proof.* We have shown that it is 3-terminating, so using Proposition 1.3.8 and Theorem 1.4.4, it remains to show that every critical pair admits a filler in **PFonct**[f]₄.

There are thirteen families of critical pairs. Among them, ten come from **BiCat[C]** or **BiCat[D]**, and were already dealt with in Theorem 3.1.6. The remaining three have the following sources:

<figure><img src="image_30.png" /></figure>

and they are filled respectively by the 4-cells ≁, ≁ and ≁.

□

**3.3 Coherence for pseudonatural transformations**

**Definition 3.3.1.** A pseudonatural transformation $\tau$ consists of the following data:

• Two pseudofunctors $F, F' : \mathcal{B} \to \mathcal{B}'$, where $\mathcal{B}$ and $\mathcal{B}'$ are bicategories.

• For every $a \in \mathcal{B}_0$, a functor $\tau_a : \mathcal{T} \to \mathcal{B}'(F_0(a), F'_0(a))$, that is a 1-cell $\tau_a : F_0(a) \to F'_0(a)$ in $\mathcal{B}'$.

• For every $a, b \in \mathcal{B}_0$, a natural isomorphism $\sigma_{a,b}$:

<figure><img src="image_31.png" /></figure>

of components $\sigma_f : F(f) \star \tau_b \Rightarrow \tau_a \star F'(f)$, for every $f \in \mathcal{B}(a, b)$.

This data must satisfy the following axioms:
• For every $(f, g) \in \mathcal{B}(a, b) \times \mathcal{B}(b, c)$:

<figure><img src="image_32.png" /></figure>

• For every $a \in \mathcal{B}_0$:

<figure><img src="image_33.png" /></figure>

**Definition 3.3.2.** Let $\mathbf{C}$ and $\mathbf{D}$ be sets, and $\mathbf{f}, \mathbf{g}$ be applications from $\mathbf{C}$ to $\mathbf{D}$. Let us define dimension by dimension a (4, 2)-polygraph $\mathbf{PNTrans}[\mathbf{f}, \mathbf{g}]$. We will see in Proposition 3.3.5 that pseudonatural transformations correspond to algebras over $\mathbf{PNTrans}[\mathbf{f}, \mathbf{g}]$.

The polygraph $\mathbf{PNTrans}[\mathbf{f}, \mathbf{g}]$ contains the union of the polygraphs $\mathbf{PFonct}[\mathbf{f}]$ and $\mathbf{PFonct}[\mathbf{g}]$. In particular, the following cells are in $\mathbf{PNTrans}[\mathbf{f}, \mathbf{g}]$:

• the cells $\mathbf{f}$, $\mathbf{g}$, $\mathbf{h}$, $\mathbf{i}$, $\mathbf{j}$ and $\mathbf{k}$ coming from $\mathbf{BiCat}[\mathbf{C}]$,

• the cells $\mathbf{f}$, $\mathbf{g}$, $\mathbf{h}$, $\mathbf{i}$, $\mathbf{j}$ and $\mathbf{k}$ coming from $\mathbf{BiCat}[\mathbf{D}]$,

• the cells $\mathbf{f}$, $\mathbf{g}$, $\mathbf{h}$, $\mathbf{i}$, $\mathbf{j}$ and $\mathbf{k}$ coming from $\mathbf{PFonct}[\mathbf{f}]$,

• the cells $\mathbf{f}$, $\mathbf{g}$, $\mathbf{h}$, $\mathbf{i}$, $\mathbf{j}$ and $\mathbf{k}$ coming from $\mathbf{PFonct}[\mathbf{g}]$.

Together with the union of $\mathbf{PFonct}[\mathbf{f}]$ and $\mathbf{PFonct}[\mathbf{g}]$, $\mathbf{PNTrans}[\mathbf{f}, \mathbf{g}]$ contains the following cells:

**Dimension 2:** For every $a \in \mathbf{C}$, the set $\mathbf{PNTrans}[\mathbf{f}, \mathbf{g}]_2$ contains a 2-cell $\Box_{\tau_a} : a|_{\mathbf{g}(a)} \Rightarrow a|_{\mathbf{f}(a)}|_{\mathbf{g}(a)}$.

**Dimension 3:** For every $a, b \in \mathbf{C}$, the set $\mathbf{PNTrans}[\mathbf{f}, \mathbf{g}]_3$ contains a 3-cell: $\Box_{a,b} : \Box \Rightarrow \Box$ of 1-source $a|b|_{\mathbf{g}(b)}$.
**Dimension 4:** The set $PNTrans[f, g]_4$ contains the following 4-cells:

* For every $a \in C$, a 4-cell $\mathcal{A}_a$ of 1-source $a|_{g(a)}$

<figure><img src="image_34.png" /></figure>

* For every $a, b, c \in C$, a 4-cell $\mathcal{B}_{a,b,c}$ of 1-source $a|_{b|_{c|_{g(c)}}}$

<figure><img src="image_35.png" /></figure>

**Definition 3.3.3.** Let $Alg(PNTrans)$ be the set of tuples $(C, D, f, g, \Phi)$:

* where $C$ and $D$ are sets,

* where $f, g: C \to D$ are applications,

* where $\Phi$ is a functor from $\overline{PNTrans}[f, g]$ to $sCat$, such that for every $c \in C$, $d \in D$ and 1-cell $|: c \to d$:

$$ \Phi(c|_d) = \top $$

**Remark 3.3.4.** Since $PFonct[f]$ (resp. $PFonct[g]$) is a sub-4-polygraph of $PNTrans[f, g]$, every functor $\Phi: \overline{PNTrans}[f, g] \to sCat$ induces by restriction two functors

$$ \Phi_O: \overline{PFonct}[f] \to sCat $$

$$ \Phi_\bullet: \overline{PFonct}[g] \to sCat $$

**Proposition 3.3.5.** *Pseudonatural transformations between pseudofunctor s are in one to one correspondence with elements of Alg(PNTrans).*

*Proof.* The proof is similar to that of bicategories, using the following correspondence table:
<table><caption>Table 3: Correspondence for pseudonatural transformations</caption><thead><tr><th colspan="2">Pseudonatural transformations</th><th colspan="2">Alg(PNTrans)</th></tr></thead><tbody><tr><td>Source and target</td><td>F and F'</td><td rowspan="4" style="vertical-align: middle; text-align: center; padding: 5px; border: 1px solid black;">Φ<sub>O</sub> and Φ<sub>●</sub></td><td>Restrictions</td></tr><tr><td>Functors</td><td>τ</td><td>2-cells</td></tr><tr><td>Natural transformations</td><td>σ</td><td>3-cells</td></tr><tr><td>Equalities</td><td>(6) (7)</td><td>4-cells</td></tr></tbody></table>

<figure><img src="image_36.png" /></figure>

This result induces the following classification of the cells of the (4,2)-polygraph PNTrans[f, g], depending on which structure they come from. We also distinguish two types of cells: product cells and unit cells. Moreover, in the following table, every line corresponds to a dimension.

<table><caption>Table 4: Classification of the cells of PNTrans[f, g]</caption><thead><tr><th>Origin</th><th>Dimension</th><th>Product cells</th><th>Unit cells</th></tr></thead><tbody><tr><td rowspan="3">Source bicategory</td><td>2-cells</td><td rowspan="3" style="vertical-align: middle; text-align: center; padding: 5px; border: 1px solid black;">(Diagram: Two vertical lines meeting at a point, one with a circle in the middle)</td><td rowspan="3" style="vertical-align: middle; text-align: center; padding: 5px; border: 1px solid black;">(Diagram: Two circles meeting at a point, one with a circle in the middle)</td></tr><tr><td>3-cells</td></tr><tr><td>4-cells</td></tr><tr><td rowspan="3">Target bicategory</td><td>2-cells</td><td rowspan="3" style="vertical-align: middle; text-align: center; padding: 5px; border: 1px solid black;">(Diagram: A vertical line meeting a horizontal line, one with a circle in the middle)</td><td rowspan="3" style="vertical-align: middle; text-align: center; padding: 5px; border: 1px solid black;">(Diagram: A vertical line meeting a horizontal line, two circles in the middle)</td></tr><tr><td>3-cells</td></tr><tr><td>4-cells</td></tr><tr><td rowspan="3">Source pseudofunctor</td><td>2-cells</td><td rowspan="3" style="vertical-align: middle; text-align: center; padding: 5px; border: 1px solid black;">(Diagram: A horizontal line meeting a horizontal line, one with a circle in the middle)</td><td rowspan="3" style="vertical-align: middle; text-align: center; padding: 5px; border: 1px solid black;">(Diagram: Three circles meeting at a point, one with a circle in the middle)</td></tr><tr><td>3-cells</td></tr><tr><td>4-cells</td></tr><tr><td rowspan="3">Target pseudofunctor</td><td>2-cells</td><td rowspan="3" style="vertical-align: middle; text-align: center; padding: 5px; border: 1px solid black;">(Diagram: A horizontal line meeting a horizontal line, two circles in the middle)</td><td rowspan="3" style="vertical-align: middle; text-align: center; padding: 5px; border: 1px solid black;">(Diagram: Three circles meeting at a point, one with a circle in the middle)</td></tr><tr><td>3-cells</td></tr><tr><td>4-cells</td></tr><tr><td rowspan="3">Pseudonatural transformation</td><td>2-cells</td><td rowspan="3" style="vertical-align: middle; text-align: center; padding: 5px; border: 1px solid black;">(Diagram: A horizontal line meeting a vertical line, one with a circle in the middle)</td><td rowspan="3" style="vertical-align: middle; text-align: center; padding: 5px; border: 1px solid black;">(Diagram: A vertical line meeting a vertical line, two circles in the middle)</td></tr><tr><td>3-cells</td></tr><tr><td>4-cells</td></tr></tbody></table>

**Proposition 3.3.6.** Let $f,g: C \to D$ be two applications. The (4,2)-polygraph PNTrans[f,g] 3-terminates.

*Proof.* We apply Theorem 1.2.4. To construct the functors $X_{f,g}: PNTrans[f,g]_2^* \to sOrd$ and $Y_{f,g}: (PNTrans[f,g]_2)^{co} \to sOrd$, we extend the functors $X_f, X_g, Y_f$ and $Y_g$ from Proposition 3.2.6, by setting:

$$X_{f,g}(\text{Diagram: a cell in a square}) = 1$$

We now define an $(X_{f,g}, Y_{f,g}, \mathbb{N})$-derivation $d_{f,g}$ of the 2-category PNTrans[f,g]_2^*$ as the extension of $d_f$ satisfying, for every $i, j \in \mathbb{N}^*$:

$$d_{f,g}(\text{Diagram: a cell})[i, j] = i + j \qquad d_{f,g}(\text{Diagram: a cell})[i] = i$$

It remains to show that the required inequalities are satisfied. Since $X_{f,g}$ (resp. $Y_{f,g}$) is an extension $X_f$ and $X_g$ (resp. $Y_f$ and $Y_g$), it only remains to treat the case of the 3-cell $\text{Diagram: a cell}$. For every $i, j \in \mathbb{N}^*$, we have:

$$X_{f,g}(\text{Diagram: a cell})[i] = i + 1 \ge i + 1 = X_{f,g}(\text{Diagram: a cell})[i]$$

$$Y_{f,g}(\text{Diagram: a cell})[i] = 2i + 1 \ge 2i + 1 = Y_{f,g}(\text{Diagram: a cell})[i]$$

Concerning $d_{f,g}$, the 3-cells from PFonct[f] were already treated in Proposition 3.1.5. For the others we have, for every $i, j, k \in \mathbb{N}^*$:
$$d_{f,g}(\text{[Diagram]})[i, j, k] = 2i + j + 3k + 2 > 2i + j + 3k = d_{f,g}(\text{[Diagram]})[i, j, k]$$

$$d_{f,g}(\text{[Diagram]}) = 3i + 1 > i = d_{f,g}(\text{[Diagram]}) \qquad d_{f,g}(\text{[Diagram]})[i, j] = 2i + 3j + 1 > i + 3j + 1 = d_{f,g}(\text{[Diagram]})[i, j]$$

**Definition 3.3.7.** We define a *weight* application $w$ as the 1-functor from $PNTrans[f, g]_1^*$ to $\mathbb{N}$, defined as follows on $PNTrans[f, g]_1$:

* for all $a, b \in \mathbf{C}$, $w(a|_b) = 1$,

* for all $a, b \in \mathbf{D}$, $w(a|_b) = 1$,

* for all $a \in \mathbf{C}$ and $b \in \mathbf{D}$, $w(a|_b) = 0$.

**Theorem 3.3.8 (Coherence for pseudonatural transformations).** Let $\mathbf{C}$ and $\mathbf{D}$ be sets, and $f, g: \mathbf{C} \to \mathbf{D}$ applications.

Let $A, B \in PNTrans[f, g]_3^{*(2)}$ be two parallel 3-cells whose 1-target is of weight 1.

There is a 4-cell $\alpha: A \rightsquigarrow B \in PNTrans[f, g]_4^{*(2)}$.

This theorem will be proven in Section 4. Contrary to the case of bicategories and pseudofunctors, we cannot directly apply Theorem 1.4.4 to the (4, 2)-polygraph $PNTrans[f, g]$, because the following critical pair is not confluent:

<figure><img src="image_37.png" /></figure>

Theorem 1.4.9 will be used in order to avoid this difficulty.
# 4 Proof of the coherence for pseudonatural transformations

In this section we prove Theorem 3.3.8. We fix for the rest of this section two sets C and D, together with two applications f, g : C → D. Let A, B ∈ PNTrans[f, g]^{*(2)} be 3-cells whose 1-target is of weight 1. We want to build a 4-cell α : A ⋄ B ∈ PNTrans[f, g]^{*(2)}.

The 1-cells of weight 1 are of one of the following forms, with a, a' ∈ C and b, b' ∈ D:

$$a|a' \quad b|b' \quad a|a'|f(a') \quad a|a'|g(a') \quad a|a'|f(a') \quad a|a'|g(a)|b \quad a|f(a)|b$$

In Section 4.1, we show that if the common 1-target of A and B is not of the last form, then they are generated by a sub-4-polygraph PFonct[f, g] of PNTrans[f, g]. We then show using Theorem 1.4.4 that this 4-polygraph is coherent.

There remains to treat the case where the 1-target of A and B is of the last form. We define two sub-(4, 2)-polygraphs of PNTrans[f, g]: PNTrans^{++}[f, g] and PNTrans^{+}[f, g]. The (4, 2)-polygraph PNTrans^{++}[f, g] contains all the structure of pseudonatural transformations, except for the axioms concerning the units ⊙ and •, while PNTrans^{+}[f, g] is an intermediary between PNTrans^{++}[f, g] and PNTrans[f, g], which contains the 2-cells ⊙ and •. The inclusions between the (4, 2)-polygraphs can be seen as follows:

$$\mathrm{PNTrans}^{++}[f, g]_2 \subset \mathrm{PNTrans}^{+}[f, g]_2 = \mathrm{PNTrans}[f, g]_2$$

$$\mathrm{PNTrans}^{++}[f, g]_3 = \mathrm{PNTrans}^{+}[f, g]_3 \subset \mathrm{PNTrans}[f, g]_3$$

In Section 4.2 we show that PNTrans^{++}[f, g] satisfies the 2-Squier condition of depth 2, which allows us to apply Theorem 1.4.9. Since 1-cells of the form a|f(a)|b are normal forms for PNTrans^{++}[f, g], this concludes the case where A and B are in PNTrans^{++}[f, g].

We then define a sub-3-polygraph PNTrans^{u}[f, g] of PNTrans[f, g]. The rewriting system induced by the 3-cells PNTrans^{u}[f, g] corresponds to simplifying the units out.

Using the properties of this rewriting system, we extend the result of Section 4.2, first to 3-cells A and B in PNTrans^{+}[f, g] in Section 4.3, and finally to general A and B whose 1-target is a|f(a)|b in Section 4.4, thereby concluding the proof.

## 4.1 A convergent sub-polygraph of PNTrans[f, g]

**Definition 4.1.1.** Let PFonct[f, g] be the 4-polygraph containing every cell of PNTrans[f, g], except those corresponding to the pseudonatural transformation. Alternatively, PFonct[f, g] is the union of PFonct[f] and PFonct[g].

**Lemma 4.1.2.** For every h ∈ PNTrans[f, g]_2^*, one of the following holds:

$$\bullet \text{ The target of h is of the form} \qquad a_1|\cdots|a_i|f(a_i)|b_1|\cdots|b_j, \qquad (8)$$

where i and j are non-zero integers, the a_k are in C and the b_k are in D.

* The 2-cell h is in PFonct[f, g]_2^*.

**Proof.** Let us show first that the set of all 1-cells of the form (8) is stable when rewritten by PFonct[f, g]_2^*. To prove this, we examine the case of every cell of PFonct[f, g]_2^* of length 1:

$$a_1|\cdots|a_{k-1} \Uparrow a_{k+1}|\cdots|b_j : a_1|\cdots|a_i|f(a_i)|b_1|\cdots|b_j \Rightarrow a_1|\cdots|a_{k-1}|a_{k+1}|\cdots|b_j$$

$$a_1|\cdots|a_k \circled{a_k}|\cdots|b_j : a_1|\cdots|a_i|f(a_i)|b_1|\cdots|b_j \Rightarrow a_1|\cdots|a_k|a_k|\cdots|b_j$$

$$a_1|\cdots|b_{k-1} \Uparrow b_{k+1}|\cdots|b_j : a_1|\cdots|a_i|f(a_i)|b_1|\cdots|b_j \Rightarrow a_1|\cdots|b_{k-1}|b_{k+1}|\cdots|b_j$$

$$a_1|\cdots|b_k \circled{b_k}|\cdots|b_j : a_1|\cdots|a_i|f(a_i)|b_1|\cdots|b_j \Rightarrow a_1|\cdots|b_k|b_k|\cdots|b_j$$

$$a_1|\cdots|a_{i-1} \Uparrow f(a_i)|\cdots|b_j : a_1|\cdots|a_i|f(a_i)|b_1|\cdots|b_j \Rightarrow a_1|\cdots|a_{i-1}|f(a_{i-1})|f(a_i)|b_1|\cdots|b_j$$

Let us now prove the lemma: we reason by induction on the length of h. If h is of length 0, it is an identity, so h is in PFonct[f, g]^*.
If $h$ is of length 1 and $h$ is not in $\mathbf{PFonct}[f, g]^*$, then $h$ has to be of the form $|\cdots| \text{[}$\text{---}$|\cdots|$. So its target is of the form:

$$a_1|\cdots|a_k|f(a_k)|g(a_k)|b_2|\cdots|b_j$$

which is indeed of the form (8), with $b_1 = g(a_k)$.

Let now $h$ be of length $n > 1$. We can write $h = h_1 \star_1 h_2$, where $h_2$ is of length 1, and $h_1$ is strictly shorter than $h$. Let us apply the induction hypothesis to $h_2$. If the target of $h_2$ is of the form (8), then so is the target of $h$, since $t(h_2) = t(h)$. Otherwise, then $h_1 \in \mathbf{PFonct}[f, g]^*$, and we can apply the induction hypothesis to $h_2$. If $h_2$ also is in $\mathbf{PFonct}[f, g]^*$, then so is $h$.

It remains to treat the case where $t(h_1)$ is of the form (8), and $h_2$ is in $\mathbf{PFonct}[f, g]^*$. But we have shown that the 1-cells of the form (8) are stable when rewritten by $\mathbf{PFonct}[f, g]^*$. Thus the target of $h_2$ (which is the target of $h$) is of the form (8), which concludes the proof. $\square$

**Lemma 4.1.3.** For every $A \in \mathbf{PNTrans}[f, g]^*_{3}^{(2)}$, one of the following holds:

* The 1-target of $A$ is of the form (8).

* The 3-cell $A$ is in $\mathbf{PFonct}[f, g]^*_{3}^{(2)}$.

*Proof.* Let us start by the case where $A$ is a 3-cell of length 1 in $\mathbf{PNTrans}[f, g]^*_{3}$. If the 1-target of $A$ is not of the form (8) then, according to Lemma 4.1.2, the 2-source of $A$ is in $\mathbf{PFonct}[f, g]^*_{2}$. The only 3-cell in $\mathbf{PNTrans}[f, g]_{3}$ which is not in $\mathbf{PFonct}[f, g]_{3}$ is the 3-cell $\text{[}$\text{---}$|\text{---}|$, whose 2-source is not in $\mathbf{PFonct}[f, g]^*_{2}$. Thus $A$ is in $\mathbf{PFonct}[f, g]^*_{3}$.

Suppose now that $A = B^{-1}$, where $B$ is a 3-cell of $\mathbf{PNTrans}[f, g]^*_{3}$ of length 1. The 1-target of $B$ is the same as the one of $A$. If it is not of the form (8), $B$ is in $\mathbf{PFonct}[f, g]^*_{3}^{(2)}$, and so is $A$.

In the general case, $A$ is a composite of 3-cells of one of the two previous forms, and all of them have the same 1-target as $A$. Thus if the 1-target of $A$ is not of the form (8), all those 3-cells are in $\mathbf{PFonct}[f, g]^*_{3}^{(2)}$, and so is $A$. $\square$

**Lemma 4.1.4.** The 4-polygraph $\mathbf{PFonct}[f, g]$ is 3-coherent.

*Proof.* It is a sub-4-polygraph of $\mathbf{PNTrans}[f, g]$ which is 3-terminating, therefore it is also 3-terminating. Moreover, every critical pair in $\mathbf{PFonct}[f, g]$ arises from one either in $\mathbf{PFonct}[f]$ or $\mathbf{PFonct}[g]$. Since those 4-polygraphs are confluent and satisfy the Squier condition, so does $\mathbf{PFonct}[f, g]$.

Using Theorem 1.4.4, this means that $\mathbf{PFonct}[f, g]$ is 3-coherent. $\square$

**Proposition 4.1.5.** Let $f, g: C \to D$ be two applications.

For every parallel 3-cells $A, B \in \mathbf{PNTrans}[f, g]^{*(2)}$ whose 1-target is not of the form (8), there exists a 4-cell $\alpha: A \cong B \in \mathbf{PNTrans}[f, g]^*_{4}^{(2)}$.

In particular, for every parallel 3-cells $A, B \in \mathbf{PNTrans}[f, g]^{*(2)}$ whose 1-target is of weight 1 and is not of the form $a|_{f(a)}|b$, there exists a 4-cell $\alpha: A \cong B \in \mathbf{PNTrans}[f, g]^*_{4}^{(2)}$.

*Proof.* Let $A, B \in \mathbf{PNTrans}[f, g]^*_{3}^{(2)}$ whose 1-target is not of the form (8). We want to build a 4-cell $\alpha: A \cong B \in \mathbf{PNTrans}[f, g]^*_{4}^{(2)}$. According to Lemma 4.1.3, $A$ and $B$ are actually 3-cells in $\mathbf{PFonct}[f, g]^*_{3}^{(2)}$. In Lemma 4.1.4 we showed that $\mathbf{PFonct}[f, g]$ is 3-coherent, hence there exists a 4-cell $\alpha: A \cong B \in \mathbf{PFonct}[f, g]^*_{4}^{(2)} \subset \mathbf{PNTrans}[f, g]^*_{4}^{(2)}$.

Moreover, the only 1-cells of weight 1 and of the form (8) are the 1-cells $a|_{f(a)}|b$, which proves the second part of the Proposition. $\square$

## 4.2 A sub-polygraph of $\mathbf{PNTrans}[f, g]$ satisfying 2-Squier condition of depth 2

**Definition 4.2.1.** Let $\mathbf{PNTrans}^{++}[f, g]$ be the sub-(4, 2)-polygraph of $\mathbf{PNTrans}[f, g]$ containing every product cell from Table 4.

**Lemma 4.2.2.** The (4, 2)-polygraph $\mathbf{PNTrans}^{++}[f, g]$ satisfies the 2-Squier condition of depth 2.
Proof. The 2-Squier condition

Let us start by showing the 2-termination of the (4, 2)-polygraph PNTrans$^{++}$[f, g].

We define a functor $\tau: PNTrans[f, g]_1^* \to \mathbb{N}^3$, where compositions in $\mathbb{N}^3$ are given by component-wise addition, by defining:

* For all $a, b \in C$, $\tau(a|_b) = (1, 0, 0)$.

* For all $a \in C$, $\tau(a|_f(a)) = (0, 1, 0)$.

* For all $a \in C$, $\tau(a|_g(a)) = (0, 2, 0)$.

* For all $a, b \in D$, $\tau(a|_b) = (0, 0, 1)$.

The lexicographic order on $\mathbb{N}^3$ induces a noetherian ordering on $PNTrans[f, g]_1^*$. Moreover the 2-cells are indeed decreasing for this order:

$$ \tau(s(\text{Y})) = (2, 0, 0) > (1, 0, 0) = \tau(t(\text{Y})) \qquad \tau(s(\text{Y})) = (0, 0, 2) > (0, 0, 1) = \tau(t(\text{Y})) $$

$$ \tau(s(\text{X})) = (1, 1, 0) > (0, 1, 1) = \tau(t(\text{X})) \qquad \tau(s(\text{X})) = (1, 2, 0) > (0, 2, 1) = \tau(t(\text{X})) $$

$$ \tau(s(\text{C})) = (0, 2, 0) > (0, 1, 1) = \tau(t(\text{C})) $$

The following diagrams show both the 2-confluence of PNTrans$^{++}$[f, g] and the correspondence between critical pairs and 3-cells:

<figure><img src="image_38.png" /></figure>

<figure><img src="image_39.png" /></figure>

<figure><img src="image_40.png" /></figure>

<figure><img src="image_41.png" /></figure>

<figure><img src="image_42.png" /></figure>
The 2-Squier condition of depth 2

The following diagrams show the bijection between critical triples and 4-cells.

<figure><img src="image_43.png" /></figure>

<figure><img src="image_44.png" /></figure>

<figure><img src="image_45.png" /></figure>

<figure><img src="image_46.png" /></figure>
<figure><img src="image_47.png" /></figure>

<figure><img src="image_48.png" /></figure>
<figure><img src="image_49.png" /></figure>

**Proposition 4.2.3.** For every 3-cells $A, B \in \text{PNTrans}^{++}[f, g]^{*(2)}$ whose 1-target is of the form $a|f(a)|b$, there exists a 4-cell $\alpha : A \equiv B \in \text{PNTrans}[f, g]^{*(2)}$.

*Proof.* Thanks to Lemma 4.2.2, we can apply Theorem 1.4.9 to $\text{PNTrans}^{++}[f, g]^{*(2)}$, and there exists a 4-cell $\alpha : A \equiv B$ in $\text{PNTrans}^{++}[f, g]^{*(2)}$ for every 3-cells $A, B \in \text{PNTrans}^{++}[f, g]^{*(2)}$ whose 1-target is a normal form. In particular the 1-cells of the form $a|f(a)|b$ are normal forms. $\square$

## 4.3 Adjunction of the units 2-cells

**Definition 4.3.1.** Let $\text{PNTrans}^u[f, g]$ be the sub-3-polygraph of $\text{PNTrans}[f, g]$ containing the same 1- and 2-cells, and whose only 3-cells are the unit cells from Table 4.

A 2-cell $h \in \text{PNTrans}[f, g]_2^*$ is said *unitary* if it is generated by the sub-2-polygraph of $\text{PNTrans}[f, g]$ whose only 2-cells are $\emptyset$ and $\bullet$.
**Lemma 4.3.2.** Let $h \in \text{PNTrans}[\mathbf{f}, \mathbf{g}]_2^*$ whose target is of the form $a|_{\mathbf{f}(a)}|b$, where $a \in \mathbf{C}$ and $b \in \mathbf{D}$.

If there is a decomposition $h = h_1 \star_1 h_2$, where $h_1 \in \text{PNTrans}^u[\mathbf{f}, \mathbf{g}]^*$ and $h_2 \in \text{PNTrans}[\mathbf{f}, \mathbf{g}]^*$ are not identities, and $h_1$ is a unitary 2-cell, then there is a 3-cell $A \in \text{PNTrans}^u[\mathbf{f}, \mathbf{g}]_3^*$ of source $h$ which is not an identity.

*Proof.* Let us start with the case where $h_1$ is of length 1. We reason by induction on the length of $h_2$. If $h_2$ is of length 1, since the target of $h_2$ is of the form $a|_{\mathbf{f}(a)}|b$, $h_2$ is one of the following 2-cells:

<figure><img src="image_50.png" /></figure>

Hence $h$ is one of the following 2-cells:

<figure><img src="image_51.png" /></figure>

And all of these 2-cells are indeed the sources of 3-cells in $\text{PNTrans}^u[\mathbf{f}, \mathbf{g}]_3^*$.

In the general case, let us write $h_2 = h_0 \star_1 h_2'$, where $h_0$ is of length 1. Two cases can occur.

* If there exist 1-cells $u, u', v$ and $v'$ and 2-cells $h_0' : u \Rightarrow u' \in \text{PNTrans}^u[\mathbf{f}, \mathbf{g}]^*$ and $h_1' : v \Rightarrow v' \in \text{PNTrans}[\mathbf{f}, \mathbf{g}]^*$ such that $h_1 = h_1' \star_0 u$ (resp. $h_1 = u \star_0 h_1'$) and $h_0 = v' \star_0 h_0'$ (resp. $h_0 = h_0' \star_0 v'$). Then $h = (h_1' \star_0 h_0') \star_1 h_2'$ (resp. $h = (h_0' \star_0 h_1') \star_1 h_2'$), and we can apply the induction hypothesis to $(h_1' \star_0 u') \star_1 h_2'$ (resp. $(u' \star_0 h_1') \star_1 h_2'$).

* Otherwise, $h_1 \star_1 h_0$ is one of the following 2-cells,

<figure><img src="image_52.png" /></figure>

and all of them are sources of 3-cells in $\text{PNTrans}^u[\mathbf{f}, \mathbf{g}]^*$.

In the case general case where $h_1$ is of any length, let $h_1', h_1'' \in \text{PNTrans}[\mathbf{f}, \mathbf{g}]_2^*$ with $h_1''$ of length 1 such that $h_1 = h_1' \star_1 h_1''$. Then there is a non-empty 3-cell $A' \in \text{PNTrans}^u[\mathbf{f}, \mathbf{g}]_3^*$ of source $h_1'' \star_1 h_2$, and one can take the 3-cell $h_1' \star_1 A'$.

**Lemma 4.3.3.** Let $h$ be a 2-cell in $\text{PNTrans}[\mathbf{f}, \mathbf{g}]^*$ whose target is of the form $a|_{\mathbf{f}(a)}|b$, with $a \in \mathbf{C}$ and $b \in \mathbf{D}$.

If $h$ is a normal form for $\text{PNTrans}^u[\mathbf{f}, \mathbf{g}]$, then one of the following holds:

* The 2-cell $h$ equals the composite $|\bullet|$.

* The 2-cell $h$ is in $\text{PNTrans}^{++}[\mathbf{f}, \mathbf{g}]^*$.

*Proof.* We reason by induction on the length of $h$. If $h$ is of length 1, the cells of $\text{PNTrans}[\mathbf{f}, \mathbf{g}]_2^*$ of length 1 and of target $a|_{\mathbf{f}(a)}|b$ are:

<figure><img src="image_53.png" /></figure>

Otherwise, let us write $h = h_1 \star_1 h_2$, where $h_1$ is of length 1. We can apply the induction hypothesis to $h_2$, which leads us to distinguish three cases:

* If $h_2 = |\bullet|$, then $h_1$ is a 2-cell in $\text{PNTrans}[\mathbf{f}, \mathbf{g}]_2^*$ whose target is of the form $a|_{\mathbf{f}(a)}$. The only such cell is the identity, and $h = h_2 = |\bullet|$.

* If $h_1$ and $h_2$ are in $\text{PNTrans}^{++}[\mathbf{f}, \mathbf{g}]^*$, then $h$ is in $\text{PNTrans}^{++}[\mathbf{f}, \mathbf{g}]^*$.

* Lastly, if $h_2$ is in $\text{PNTrans}^{++}[\mathbf{f}, \mathbf{g}]^*$ and $h_1$ is in $\text{PNTrans}^u[\mathbf{f}, \mathbf{g}]^*$, then because of Lemma 4.3.2, $h$ is the source of a 3-cell in $\text{PNTrans}^u[\mathbf{f}, \mathbf{g}]^*$ of length 1, which is impossible since, by hypothesis, $h$ is a normal form for $\text{PNTrans}^u[\mathbf{f}, \mathbf{g}]$.

<figure><img src="image_54.png" /></figure>

**Definition 4.3.4.** Let $\text{PNTrans}^+[\mathbf{f}, \mathbf{g}]$ be the sub-4-polygraph of $\text{PNTrans}[\mathbf{f}, \mathbf{g}]$ containing $\text{PNTrans}^{++}[\mathbf{f}, \mathbf{g}]$, together with the 2-cells $\circled{0}$ and $\bullet$.

In particular a 3-cell in the free (3, 2)-category $\text{PNTrans}^+[\mathbf{f}, \mathbf{g}]^{*(2)}$ is in $\text{PNTrans}^{++}[\mathbf{f}, \mathbf{g}]^{*(2)}$ if and only if its 2-source is in $\text{PNTrans}^{++}[\mathbf{f}, \mathbf{g}]^{*(2)}$ too.
**Proposition 4.3.5.** For every parallel 3-cells $A, B \in \text{PNTrans}^+[f, g]^{*(2)}$ whose 1-target is of the form $[f(a)]_b$ and whose 2-source is a normal form for $\text{PNTrans}^u[f, g]$, there exists a 4-cell $\alpha : A \stackrel{\alpha}{\rightarrow} B \in \text{PNTrans}[f, g]^{*(2)}$.

*Proof.* Given such 3-cells $A$ and $B$, we use Lemma 4.3.3 to distinguish two cases:

If the source of $A$ and $B$ is $\bullet$, the only 3-cell in $\text{PNTrans}^+[f, g]^{*(2)}$ with source $\bullet$ is the identity.
So $A = B$ and we can take $\alpha = 1_A$.

Otherwise, the source of $A$ and $B$ lies in $\text{PNTrans}^{++}[f, g]_2^*$, so $A$ and $B$ lie in $\text{PNTrans}^{++}[f, g]_3^{*(2)}$.
Proposition 4.2.3 allows us to conclude. $\square$

## 4.4 Adjunction of the units 3-cells

In this section, we consider the rewriting system formed by the 3-cells of $\text{PNTrans}^u[f, g]$. Since it is a sub-3-polygraph of $\text{PNTrans}[f, g]$ (which 3-terminates by Proposition 3.3.6), $\text{PNTrans}^u[f, g]$ is 3-terminating. The fact that it is 3-confluent is a consequence of the following more general Lemma:

**Lemma 4.4.1.** Let $A \in \text{PNTrans}[f, g]_3^*$ and $B \in \text{PNTrans}^u[f, g]_3^*$. There exist 3-cells $A' \in \text{PNTrans}[f, g]_3^*$ and $B' \in \text{PNTrans}^u[f, g]_4^{*(2)}$ and a 4-cell $\alpha_{A,B} \in \text{PNTrans}[f, g]_4^{*(2)}$ of the following shape:

<figure><img src="image_55.png" /></figure>

*Proof.* Let us start by the case where $(A, B)$ is a critical pair of $\text{PNTrans}[f, g]_3$. If $A$ and $B$ are in $\text{PFonct}[f, g]_3^*$, the result holds because $\text{PFonct}[f, g]$ is 3-convergent. Otherwise, the only critical pair left is the following one:

<figure><img src="image_56.png" /></figure>

Let us now study the case where $(A, B)$ is a local branching of $\text{PNTrans}[f, g]_3$. We distinguish three cases depending on the shape of the branching:

* If $(A, B)$ is an aspherical branching, then one can take identities for $A'$ and $B'$, and $\alpha = 1_A$.

* If $(A, B)$ is a Peiffer branching, let $A'$ and $B'$ be the canonical fillers of the confluence diagram of $(A, B)$, and $\alpha$ be an identity.

* Lastly, if $(A, B)$ is an overlapping branching, let us write $(A, B) = (f \star_1 uA_1v \star_1 g, f \star_1 uB_1v \star_1 g)$, where $(A_1, B_1)$ is a critical pair. Let $A'_1, B'_1$ and $\alpha_1$ be the cells associated with $(A_1, B_1)$. We then define $A' := f \star_1 uA'_1v \star_1 g, B' := f \star_1 uB'_1v \star_1 g$ and $\alpha_1 := f \star_1 u\alpha_1v \star_1 g$.

In the general case, we reason by noetherian induction on $h = s(A) = s(B)$, using the 3-termination of $\text{PNTrans}[f, g]$.
* If $A$ or $B$ is an identity, then the result holds immediately.

* Otherwise, we write $A = A_1 \star_2 A_2$ and $B = B_1 \star_2 B_2$, where $A_1$ and $B_1$ are of length 1. We now build the following diagram:

<figure><img src="image_57.png" /></figure>

In this diagram, $\alpha_{A_1, B_1}$ is obtained thanks to our study of the local branchings. The existence of $\alpha_{A_2, B'_1}$ and $\alpha_{A'_1, B_2}$ (followed by $\alpha_{A'_2, B'_2}$) then follows from the induction hypothesis. $\square$

**Lemma 4.4.2.** Let $f, g$ be 2-cells of $\text{PNTrans}[f, g]^*$, and $A : f \Rightarrow g$ a 3-cell of $\text{PNTrans}^+[f, g]^*$. If $f$ is a normal form for $\text{PNTrans}^u[f, g]$, then so is $g$.

*Proof.* We prove this result by contrapositive. We are going to show that for any $A \in \text{PNTrans}^+[f, g]^*$ and $B \in \text{PNTrans}^u[f, g]^*$ two 3-cells of length 1 such that $t(A) = s(B)$, there exists $B' \in \text{PNTrans}^u[f, g]^*$ of length 1 and of source $s(A)$:

<figure><img src="image_58.png" /></figure>

Two cases can occur depending on the shape of the branching $(A^{-1}, B)$:

* If it is a Peiffer branching, then the required cell is provided by the canonical filling.

* If it is an overlapping branching, then it is enough to check the underlying critical pair.

It remains to examine those critical pairs:

<figure><img src="image_59.png" /></figure>
<figure><img src="image_60.png" /></figure>

<figure><img src="image_61.png" /></figure>

**Lemma 4.4.3.** Let $A \in \mathrm{PNTrans}[\mathbf{f}, \mathbf{g}]_3^*$. If the source of $A$ is a formal form for $\mathrm{PNTrans}^u[\mathbf{f}, \mathbf{g}]$, then $A$ is in $\mathrm{PNTrans}^+[\mathbf{f}, \mathbf{g}]_3^*$.

*Proof.* We reason by induction on the length of $A$:

* If $A$ is an identity, then it is in $\mathrm{PNTrans}^+[\mathbf{f}, \mathbf{g}]$.

* Otherwise, let us write $A = A_1 \star_2 A_2$, where $A_1$ is of length 1. Since the source of $A$ is a normal form for $\mathrm{PNTrans}^u[\mathbf{f}, \mathbf{g}]$, the 3-cell $A_1$ can only be in $\mathrm{PNTrans}^+[\mathbf{f}, \mathbf{g}]^*$.

According to Lemma 4.4.2, the normal forms for $\mathrm{PNTrans}^u[\mathbf{f}, \mathbf{g}]$ are stable when rewritten by $\mathrm{PNTrans}^+[\mathbf{f}, \mathbf{g}]^*$. Hence the source $A_2$ is a normal form for $\mathrm{PNTrans}^u[\mathbf{f}, \mathbf{g}]$, and by induction hypothesis, $A_2$ is in $\mathrm{PNTrans}^+[\mathbf{f}, \mathbf{g}]^*$. By composition, so is $A$.

<figure><img src="image_62.png" /></figure>

**Lemma 4.4.4.** Let $A$ be a 3-cell in $\mathrm{PNTrans}[\mathbf{f}, \mathbf{g}]^{*(2)}$. There exist $C_1, C_2 \in \mathrm{PNTrans}^u[\mathbf{f}, \mathbf{g}]_3^*$ whose target is a normal form for $\mathrm{PNTrans}^u[\mathbf{f}, \mathbf{g}]$, a 3-cell $A' \in \mathrm{PNTrans}^+[\mathbf{f}, \mathbf{g}]_3^{*(2)}$ and a 4-cell $\alpha \in \mathrm{PNTrans}[\mathbf{f}, \mathbf{g}]_4^{*(2)}$ of the following shape:

<figure><img src="image_63.png" /></figure>

*Proof.* Let us write $A = A_1^{-1} \star_2 B_1 \star_2 A_2^{-1} \dots \star_2 A_n^{-1} \star_2 B_n$, where the $A_i$ and $B_i$ are in $\mathrm{PNTrans}[\mathbf{f}, \mathbf{g}]_3^*$. For every $i \le n$, we chose a 3-cell $D_i \in \mathrm{PNTrans}^u[\mathbf{f}, \mathbf{g}]_3^*$ of source $\mathrm{s}(A_i) = \mathrm{s}(B_i)$ and of target a normal form for $\mathrm{PNTrans}^u[\mathbf{f}, \mathbf{g}]$.

According to Lemma 4.4.1, there exist for every $i$ some 3-cells $A'_i, B'_i$ in $\mathrm{PNTrans}[\mathbf{f}, \mathbf{g}]^*$, $D'_i \in \mathrm{PNTrans}^u[\mathbf{f}, \mathbf{g}]_3^*$ and $D''_i \in \mathrm{PNTrans}^u[\mathbf{f}, \mathbf{g}]_3^*$ and some 4-cells $\alpha_i$ and $\beta_i$ in $\mathrm{PNTrans}[\mathbf{f}, \mathbf{g}]^{*(2)}$ of the form:
<figure><img src="image_64.png" /></figure>

The following is a consequence of the target of $D_i$ being a normal form for $\text{PNTrans}^u[f, g]$:

• Using Lemma 4.4.3, $A'_i$ and $B'_i$ are in $\text{PNTrans}^+[f, g]^*$,

• Using Lemma 4.4.2, the target $A'_i$ and $B'_i$ (thus of $D'_i$ and $D''_i$) are normal forms for $\text{PNTrans}^u[f, g]$.

• Since $\text{PNTrans}^u[f, g]$ is 3-convergent, for any $i < n$, the cells $D''_i$ and $D'_{i+1}$ are parallel.

Since $\text{PNTrans}^u[f, g]$ is a sub-polygraph of $\text{PFonct}[f, g]$ which is 3-coherent, there exists, for every $i < n$, a 4-cell $\gamma_i : D''_i \cong D'_i$ in $\text{PFonct}[f, g]^*_{\mathbb{Z}_4}^{(2)}$.

We can now conclude the proof of this Lemma by taking $C_1 = D'_1$, $C_2 = D''_n$ and $A' = (A'_1)^{-1} \star_2 B'_2 \star_2 \dots \star_2 (A'_n)^{-1} \star_2 B'_n$, and by defining $\alpha$ as the following composite:

<figure><img src="image_65.png" /></figure>

□

We can now conclude the proof Theorem 3.3.8.

**Theorem 3.3.8** (Coherence for pseudonatural transformations). Let $C$ and $D$ be sets, and $f, g : C \to D$ applications.

Let $A, B \in \text{PNTrans}[f, g]^*_{\mathbb{Z}_3}^{(2)}$ be two parallel 3-cells whose 1-target is of weight 1.

There is a 4-cell $\alpha : A \stackrel{\alpha}{\rightleftharpoons} B \in \text{PNTrans}[f, g]^*_{\mathbb{Z}_4}^{(2)}$.

*Proof.* Let $A, B \in \text{PNTrans}[f, g]^*_{\mathbb{Z}_3}^{(2)}$ be two parallel 3-cells whose 1-target is $a|_{f(a)}|b$. We are going to build a 4-cell $\alpha : A \stackrel{\alpha}{\rightleftharpoons} B \in \text{PNTrans}[f, g]^*_{\mathbb{Z}_4}^{(2)}$.

According to Lemma 4.4.4, there exist $C_1, C_2, C'_1, C'_2 \in \text{PNTrans}^u[f, g]^*$ whose targets are normal forms for $\text{PNTrans}^u[f, g]$, $A', B' \in \text{PNTrans}^+[f, g]^{*(2)}$ and $\alpha_1, \alpha_2 \in \text{TPN}[f, g]^*_{\mathbb{Z}_4}^{(2)}$ such that we have the diagrams:

<figure><img src="image_66.png" /></figure>

The 3-cells $A$ and $B$ are parallel, and the 3-cells $C_1$ and $C_2$ (resp. $C'_1$ and $C'_2$) have the same source and have a normal form for $\text{PNTrans}^u[f, g]$ as target. Since $\text{PNTrans}^u[f, g]$ is 3-convergent, this implies that the 3-cells $C_1$ and $C_2$ (resp. $C'_1$ and $C'_2$) are parallel. This has two consequences:
• The critical pairs of $\mathbf{PNTrans}^u[f, g]$ already appeared in $\mathbf{PFonct}[f, g]$, and we showed that they admit fillers. Hence there exist cells $\beta_1 : C_1 \stackrel{\beta_1}{\rightleftharpoons} C_2$ and $\beta_2 : C'_1 \stackrel{\beta_2}{\rightleftharpoons} C'_2$ in $\mathbf{PNTrans}[f, g]_4^{*(2)}$.

• The 3-cells $A'$ and $B'$ are parallel, their 1-target is still $a|_{f(a)}b$, and their 2-source is a normal form for $\mathbf{PNTrans}^u[f, g]$. So by Proposition 4.3.5 there exists a 4-cell $\gamma : A' \stackrel{\gamma}{\rightleftharpoons} B'$.

To conclude, we define $\alpha$ as the following composite (where we omit the context of the 4-cells):

<figure><img src="image_67.png" /></figure>

<figure><img src="image_68.png" /></figure>
# 5 Transformation of a (4, 2)-polygraph into a (4, 3)-white-polygraph

The proof of Theorem 1.4.9 will occupy the rest of this article. We start with a (4, 2)-polygraph $\mathcal{A}$ satisfying the hypotheses of Theorem 1.4.9. Let $S_A$ be the set of all 2-cells in $\mathcal{A}_2^*$ whose target is a normal form. Then proving Theorem 1.4.9 consists in showing that $\mathcal{A}$ is $S_A$-coherent.

In this section we successively transform $\mathcal{A}$ four times, leading to five pointed (4, 3)-white-categories, namely $(\mathcal{A}^{*(2)}, S_A)$, $(\mathcal{B}^{(2)}, S_B)$, $(\mathcal{C}^{(3)}, S_C)$, $(\mathcal{D}^{(3)}, S_D)$ and $(\mathcal{E}^{(3)}, S_E)$, and we show each time that the new pointed (4, 3)-white-category is stronger than the previous one. A brief description of each pointed (4, 3)-white-category can be seen in Table 5. Finally in Section 5.5, we perform a number of Tietze-transformations on the 4-white-polygraph $\mathcal{E}$, leading to a 4-white-polygraph $\mathcal{F}$.

Thanks to Lemma 2.2.8 and Proposition 2.2.14, we know that in order to show that $\mathcal{A}^{*(2)}$ is $S_A$-coherent, it is enough to show that $\mathcal{F}^{(3)}$ is $S_E$-coherent. This will be done in Section 6.

<table><caption>Table 5: List of the successive transformations of $\mathcal{A}$.</caption><thead><tr><th>Name</th><th>Description</th><th>Commentary</th></tr></thead><tbody><tr><td>(<i>A</i><sup>*(2)</sup>, <i>S</i><sub><i>A</i></sub>)</td><td><i>A</i><sub>2</sub><br><i>A</i><sub>3</sub><br><i>A</i><sub>4</sub></td><td></td></tr><tr><td>(<i>B</i><sup><i>w</i>(2)</sup>, <i>S</i><sub><i>B</i></sub>)</td><td><i>A</i><sub>2</sub><br><i>A</i><sub>3</sub> &cup; <i>K</i><br><i>A</i><sub>4</sub> &cup; <i>L</i></td><td>Weakening of the<br>exchange law <sup>1</sup></td></tr><tr><td>(<i>C</i><sup><i>w</i>(3)</sup>, <i>S</i><sub><i>C</i></sub>)</td><td><i>A</i><sub>2</sub><br><i>A</i><sub>3</sub> &cup; <i>A</i><sub>3</sub><sup><i>op</i></sup> &cup; <i>K</i> &cup; <i>K</i><sup><i>op</i></sup><br><i>A</i><sub>4</sub> &cup; <i>L</i> &cup; {<i>&rho;</i><sub><i>A</i></sub>, <i>&lambda;</i><sub><i>A</i></sub>}</td><td>Weakening<br>of the invertibility<br>of 3-cells</td></tr><tr><td>(<i>D</i><sup><i>w</i>(3)</sup>, <i>S</i><sub><i>D</i></sub>)</td><td><i>A</i><sub>2</sub> &cup; <i>A</i><sub>2</sub><sup><i>op</i></sup><br><i>A</i><sub>3</sub> &cup; <i>A</i><sub>3</sub><sup><i>op</i></sup> &cup; <i>K</i> &cup; <i>K</i><sup><i>op</i></sup><br><i>A</i><sub>4</sub> &cup; <i>L</i> &cup; {<i>&rho;</i><sub><i>A</i></sub>, <i>&lambda;</i><sub><i>A</i></sub>}</td><td>Adjunction of<br>formal inverses<br>to 2-cells</td></tr><tr><td>(<i>E</i><sup><i>w</i>(3)</sup>, <i>S</i><sub><i>E</i></sub>)</td><td><i>A</i><sub>2</sub> &cup; <i>A</i><sub>2</sub><sup><i>op</i></sup><br><i>A</i><sub>3</sub> &cup; <i>A</i><sub>3</sub><sup><i>op</i></sup> &cup; <i>K</i> &cup; <i>K</i><sup><i>op</i></sup> &cup; {<i>&eta;</i><sub><i>f</i></sub>, <i>&epsilon;</i><sub><i>f</i></sub>}</td><td>Adjunction<br>of connections<br>between 2-cells</td></tr></tbody></table>

**Example 5.0.5.** We have already shown in Section 3 that for every sets **C**, **D** and for every applications **f**, **g**: **C** → **D**, the (4, 2)-polygraph PNTrans<sup>++</sup>[**f**, **g**] satisfies the hypothesis of Theorem 1.4.9.

In what follows, we will use as a running example the polygraph $\mathcal{A} = \text{Assoc}$ which consists of one 0-cell, one 1-cell $|$, one 2-cell $\triangleright: | \Rightarrow |$, one 3-cell $\triangleright: \triangleright \Rightarrow \triangleright$, and one 4-cell $\triangleright: \triangleright$:

<figure><img src="image_69.png" /></figure>

In particular, **Assoc** satisfies the 2-Squier condition of depth 2. The 2-category $\text{Assoc}_2^*$ is 2-convergent and its only normal form is the 1-cell $|$.

The corresponding set $S_A$ is then the set of 2-cells in $\text{Assoc}_2^*$ from any 1-cell $|\cdots|$ to $|$.

<footnote n="1">¹The sets $K$ and $L$ will be defined in Section 5.1</footnote>
## 5.1 Weakening of the exchange law

We construct dimension by dimension a (4, 2)-white-polygraph $\mathcal{B}$, together with a white-functor $F: \mathcal{B}^{w(2)} \to \mathcal{A}^{*(2)}$. We then define a subset $S_B$ of $\mathcal{B}^{w(2)}$ and show (Proposition 5.1.4) using $F$ that $(\mathcal{B}^{w(2)}, S_B)$ is stronger than $(\mathcal{A}^{*(2)}, S_A)$.

In low dimensions, we set $\mathcal{B}_i = \mathcal{A}_i$, for every $i \le 2$, and the functor $F$ is the identity on generators.

**Lemma 5.1.1.** The functor $F: \mathcal{B}^w \to \mathcal{A}^*$ is 2-surjective.

*Proof.* By construction, $\mathcal{A}_2^*$ is the quotient of $\mathcal{B}_2^w$ by the equivalence relation generated by:

$$ (f \star_0 v) \star_i (u' \star_0 g) = (u \star_0 g) \star_i (f \star_0 v'). $$

And $F$ is the canonical projection induced by the quotient.

In what follows, we suppose chosen a section $i: \mathcal{A}^* \to \mathcal{B}^w$ of $F$, which is possible thanks to Lemma 5.1.1.

We extend $\mathcal{B}$ into a 3-white-polygraph and $F: \mathcal{B}^w \to \mathcal{A}^*$ into a 3-white-functor by setting $\mathcal{B}_3 := \mathcal{A}_3 \cup K$:

* For every 3-cell $A \in \mathcal{A}_3$, the source and target of $A$ in $\mathcal{B}_2^w$ are respectively $\mathcal{S}^B(A) := i(\mathbf{s}^A(A))$ and $\mathbf{t}^B(A) := i(\mathbf{t}^A(A))$.

* The set $K$ is the set of 3-cells $A_{fv,ug}$, of shape:

<figure><img src="image_70.png" /></figure>

for every strict Peiffer branching $(fv, ug)$, where $f: u \to u'$ and $g: v \to v'$ are rewriting steps.

The image of a cell of $\mathcal{B}_3$ under $F$ is defined as follows:

* For every strict Peiffer branching $(fv, ug)$, $F(A_{fv,ug}) := 1_{f \star_0 g}$

* For every 3-cell $A$ in $\mathcal{A}_3$, $F(A) := A$.

**Lemma 5.1.2.** Let $f, g \in \mathcal{B}_2^w$. There exists a 3-cell $A: f \Rightarrow g$ in $K_3^{w(2)}$ if and only if the equality $F(f) = F(g)$ holds in $\mathcal{A}_2^*$.

*Proof.* Let $f, g \in \mathcal{B}_2^w$. The image of any cell in $K_3^{w(2)}$ by $F$ is an identity. So if there exists a 3-cell $A: f \Rightarrow g$ in $K_3^{w(2)}$, necessarily $F(f) = F(g)$.

Conversely, the set $\mathcal{A}_2^*$ is the quotient of $\mathcal{B}_2^w$ by the equivalence relation generated by:

$$ fs(g) \star_1 t(f)g = s(f)g \star_1 ft(g), $$

for $f, g \in \mathcal{B}_2^w$. The 3-cells $A_{fu,vg}$, where $(fu, vg)$ is a strict Peiffer branching, generate this relation, and they are in $K$. Hence the result.

**Lemma 5.1.3.** The functor $F: \mathcal{B}^{w(2)} \to \mathcal{A}^{w(2)}$ is 3-surjective.

*Proof.* Let $E$ be the set of 3-cells $A \in \mathcal{A}_3^{*(2)}$ such that, for every $f, g \in \mathcal{B}_2^w$ in the preimage of $s(A)$ and $t(A)$ under $F$, there exists a 3-cell $B: f \Rightarrow g \in \mathcal{B}_3^{w(2)}$ satisfying $F(B) = A$. Let us show that $E = \mathcal{A}_3^*$. We already know that $E$ contains the identities thanks to Lemma 5.1.2.

The 3-cells of length 1 in $\mathcal{A}_3^*$ are in $E$. Indeed, let $A \in \mathcal{A}_3^*$ be a 3-cell of length 1, and $f, g \in \mathcal{B}_2^w$ such that $F(f) = s(A)$ et $F(g) = t(A)$. There exist $u, v \in \mathcal{A}_1^*, f', g' \in \mathcal{A}_2^*, \text{ and } A' \in \mathcal{A}_3$ such that

$$ A = f' \star_1 (uA'v) \star_1 g'. $$
Let $\tilde{u}, \tilde{v}, \tilde{f}, \tilde{g}$ be in the preimages respectively of $u, v, f', g'$ under $F$ (they exist thanks to Lemma 5.1.1), and let $B_1 := \tilde{f} \star_1 (\tilde{u}A'\tilde{v}) \star_1 \tilde{g} \in \mathcal{B}_3^{\mathbf{w}^{(2)}}$. By construction, $F(B_1) = A$, which leads to the equalities:

$$F(\mathbf{s}(B_1)) = F(f) \qquad F(\mathbf{t}(B_1)) = F(g).$$

Thus, according to Lemma 5.1.2, there exist 3-cells $C_1 : f \Rightarrow \mathbf{s}(B_1) \in K_3^{\mathbf{w}^{(2)}}$ and $C_2 : \mathbf{t}(B_1) \Rightarrow g \in K_3^{\mathbf{w}^{(2)}}$. Let $B := C_1 \star_2 B_1 \star_2 C_2$: by construction, $B$ has the required source and target, and moreover:

$$F(B) = F(C_1) \star_2 F(B_1) \star_2 F(C_2) = 1_{F(f)} \star_2 A \star_2 1_{F(g)} = A.$$

The set $E$ is stable under composition. Indeed let $A_1, A_2 \in E$ such that $\mathbf{t}(A_1) = \mathbf{s}(A_2)$, and $f, g \in \mathcal{B}_2^{\mathbf{w}}$ satisfying $F(f) = \mathbf{s}(A_1)$ and $F(g) = \mathbf{t}(A_2)$. Since $F$ is 2-surjective, there exists $h \in \mathcal{B}_2^{\mathbf{w}}$ in the inverse image of $\mathbf{t}(A_1)$ under $F$. Since $A_1$ (resp. $A_2$) is in $E$, there exists a cell $B_1$ (resp. $B_2$) in $\mathcal{B}_3^{\mathbf{w}^{(2)}}$ such that $F(B_1) = A_1$ (resp. $F(B_2) = A_2$), $\mathbf{s}(B_1) = f$ (resp. $\mathbf{s}(B_2) = h$) and $\mathbf{t}(B_1) = h$ (resp. $\mathbf{t}(B_2) = g$). Let $B := B_1 \star_2 B_2$: we get:

$$\mathbf{s}(B) = f \qquad F(B) = A_1 \star_2 A_2 \qquad \mathbf{t}(B) = g$$

The set $E$ is stable under 2-composition. Indeed let $A \in E$ and $f, g \in \mathcal{B}_2^{\mathbf{w}}$ such that $F(f) = \mathbf{s}(A^{-1})$ and $F(g) = \mathbf{t}(A^{-1})$. There exists $B \in \mathcal{B}^{\mathbf{w}^{(2)}}$ such that:

$$\mathbf{s}(B) = g \qquad F(B) = A \qquad \mathbf{t}(B) = f.$$

Hence the cell $B^{-1}$ satisfies the required property. $\square$

We now extend $\mathcal{B}$ into a (4,2)-white-polygraph and $F : \mathcal{B}^{\mathbf{w}^{(2)}} \to \mathcal{A}^{*(2)}$ into a 4-white-functor by setting $\mathcal{B}_4 = \mathcal{A}_4 \cup L$:

* For every 3-cell $A \in \mathcal{A}_4$, the source and target of $A$ in $\mathcal{B}_3^{\mathbf{w}^{(2)}}$ are respectively $\mathbf{s}^{\mathcal{B}}(A) := i(\mathbf{s}^{\mathcal{A}}(A))$ and $\mathbf{t}^{\mathcal{B}}(A) := i(\mathbf{t}^{\mathcal{A}}(A))$, where $i$ is a chosen section of the application $F_3 : \mathcal{B}_3^{\mathbf{w}^{(2)}} \to \mathcal{A}_3^{\mathbf{w}^{(2)}}$ (which exists since $F$ is 3-surjective). And we set $F(A) := A$.

* For every 3-fold strict Peiffer branching $(f, g, h)$, the set $L$ contains a 4-cell $A_{f,g,h}$, whose shape depends on the form of the branching $(f, g, h)$. If $(f, g, h) = (f'v, g'v, uh')$, with $(f', g')$ a critical pair, and $h' : v \Rightarrow v'$ then $A_{f,g,h}$ is of the following shape:

<figure><img src="image_71.png" /></figure>

where $A$ and $B$ are in $K_3^{\mathbf{w}^{(2)}}$. And we define $F(A_{f,g,h}) := 1_{A_{f',g'\star0,h'}}$.

If $(f, g, h) = (f'v, ug', uh')$, with $(g, h)$ a critical pair, and $f' : u \Rightarrow u'$ then $A_{f,g,h}$ is of the following shape:

<figure><img src="image_72.png" /></figure>

where $A$ and $B$ are in $K_3^{\mathbf{w}^{(2)}}$. And we define $F(A_{f,g,h}) := 1_{f'\star0A_{g',h'}}$.
If $(f, g, h) = (f'vw, ug'w, uh'w)$, then $A_{f,g,h}$ is of the following shape, where A and B are in $K_3^{w(2)}$:

<figure><img src="image_73.png" /></figure>

And we define $F(A_{f,g,h}) := 1_{f'\star_0 g'\star_0 h'}$.

Let now $S_B$ be the set of all 2-cells in $\mathcal{B}^w$ whose 1-target is a normal form.

**Proposition 5.1.4.** *The pointed (4,3)-white-category $(\mathcal{B}^{w(2)}, S_B)$ is stronger than $(A^{*(2)}, S_A)$.*

*Proof.* The functor $F$ sends normal forms on normal forms. Hence by restriction it induces a 2-functor $F|_{S_B}: \mathcal{B}^{w(2)}|_{S_B} \to A^{*(2)}|_{S_A}$.

Lemmas 5.1.1 and 5.1.3 show that it is $k$-surjective for every $k < 2$. Hence we can conclude using Lemma 2.2.8. □

**Example 5.1.5.** In the case where $\mathcal{A} = \text{Assoc}$, the set $K$ contains in particular the following 3-cells, associated respectively to the strict Peiffer branchings ($\Uparrow$ $|$ $|$, $|$, $|\Uparrow$) and ($\Uparrow$ $|$, $|$, $|$, $|\Uparrow$):

<figure><img src="image_74.png" /></figure>

In $L$, the 4-cell associated to the strict Peiffer branching ($\Uparrow$ $|$, $|$, $|$, $|\Uparrow$), $|$, $|$, $|$, $|\Uparrow$) is the following:

<figure><img src="image_75.png" /></figure>

## 5.2 Weakening of the invertibility of 3-cells

We construct dimension by dimension a 4-white-polygraph $\mathcal{C}$, together with a 3-white-functor $G: \mathcal{C}^{w(3)} \to \mathcal{B}^{w(2)}$. We then define a subset $S_C$ of $\mathcal{C}^{w(3)}$ and show (Proposition 5.2.2) using $G$ that $(\mathcal{C}^{w(3)}, S_C)$ is stronger than $(\mathcal{B}^{w(2)}, S_B)$.

In low dimensions, we set $C_i = \mathcal{B}_i$ for $i \le 2$, with the functor $G$ being the identity.

We extend $\mathcal{C}$ into a 3-white-polygraph by setting $C_3 := \mathcal{B}_3 \cup \mathcal{B}_3^{op}$, where the set $\mathcal{B}_3^{op}$ contains, for every $A \in \mathcal{B}_3$, a cell denoted by $A^{op}$, whose source and target are given by the equalities:

$$ \mathbf{s}(A^{op}) = \mathbf{t}(A) \quad \mathbf{t}(A^{op}) = \mathbf{s}(A) $$

And the functor $G: \mathcal{C}^{w} \to \mathcal{B}^{w(2)}$ is defined as follows for every $A \in \mathcal{B}_3$:

$$ G(A) = A \quad G(A^{op}) = A^{-1}. $$
**Lemma 5.2.1.** The functor $G: C^{w(3)} \to B^{w(2)}$ is 3-surjective.

*Proof.* By definition, $B_3^{w(2)}$ is the quotient of $C_3^w$ by the relations $A^{op} \star_2 A = 1$ and $A \star_2 A^{op} = 1$, and $G$ is the corresponding canonical projection. □

We extend $\mathcal{C}$ into a 4-white-polygraph by setting $C_4 := B_4 \cup \{\rho_A, \lambda_A | A \in B_3\}$, where the applications source and target $s, t: C_4 \to C_3^w$ are defined as follows:

* For $A \in B_4$, the cell $s^C(A)$ (resp. $t^C(A)$) is any cell in the preimage of $s^B(A)$ under $G$, which is non-empty thanks to Lemma 5.2.1. And we set $G(A) := A$.

* For every $A \in B_3$, the cells $\rho_A$ and $\lambda_A$ have the following shape:

<figure><img src="image_76.png" /></figure>

And we set $G(\rho_A) := 1_{s(A)}$ and $G(\lambda_A) := 1_{t(A)}$.

Let $S_C$ be the set of all 2-cells in $C^w$ whose 2-target is a normal form.

**Proposition 5.2.2.** *The pointed (4,3)-white-category $(C^{w(3)}, S_C)$ is stronger than $(B^{w(2)}, S_B)$.*

*Proof.* The functor $G$ restricts into a functor $G|_{S_C}: C^{w(3)}|_{S_C} \to B^{w(2)}|_{S_B}$, which is $i$-surjective for $i < 2$ thanks to Lemma 5.2.1. Hence we can conclude thanks to Lemma 2.2.8. □

**Example 5.2.3.** In the case where $\mathcal{A} = \text{Assoc}$, let $A = \text{Assoc}$. The set $C_3$ contains the following 3-cell:

<figure><img src="image_77.png" /></figure>

And the following cells lie in $C_4$, where $A = \text{Assoc}$:

<figure><img src="image_78.png" /></figure>

## 5.3 Adjunction of formal inverses to 2-cells

Let $\mathcal{D}$ be the 4-white-polygraph defined as follows:

$$ \text{for every } i \neq 2, \quad D_i := C_i \qquad D_2 := C_2 \cup \bar{C}_2, $$

where for every $f \in C_2$, the set $\bar{C}_2$ contains a cell $\bar{f}$ with source $t(f)$ and with target $s(f)$. Let $S_D$ be the set of all 2-cells of the sub-2-white-category $C_2^w$ of $\mathcal{D}^w$ whose target is a normal form.

**Notation 5.3.1.** The application $C_2 \to \bar{C}_2$ extends into an application $C_2^w \to \bar{C}_2^w$ which exchanges the source and targets of the 2-cells.

We denote a 2-cell $f$ by $\underset{\leftarrow}{f} \Rightarrow$ if $f$ is in $B_2^w$, by $\underset{\Rightarrow}{f} \leftarrow$ if $\bar{f}$ is in $B_2^w$, and by $\underset{\leftarrow}{\overleftarrow{f}} \Rightarrow$ if $f$ is any cell in $C_2^w$.

**Proposition 5.3.2.** *The pointed (4,3)-white-category $(\mathcal{D}^{w(3)}, S_D)$ is stronger than $(C^{w(3)}, S_C)$.*
*Proof.* Let us show that $\mathcal{D}^{w^{(3)}}|_{S_D} = \mathcal{C}^{w^{(3)}}|_{S_C}$. Let $\iota: \mathcal{C}^{w^{(3)}} \to \mathcal{D}^{w^{(3)}}$ be the canonical inclusion functor. Since the only cells added are in dimension 2, $\iota$ satisfies the hypotheses of Proposition 2.3.8, thus $\mathcal{C}^w$ is a sub-4-white-category of $\mathcal{D}^w$, which gives us an inclusion $\mathcal{C}^{w^{(3)}}|_{S_C} \subseteq \mathcal{D}^{w^{(3)}}|_{S_D}$.

Let us show the reverse inclusion. Let $f \in \mathcal{D}^{w^{(3)}}$ be an $i$-cell ($i \ge 2$), and suppose that $f$ is in $\mathcal{D}^{w^{(3)}}|_{S_D}$. In particular $\mathbf{t}_2(f)$ and $\mathbf{s}_2(f)$ are in $\mathcal{C}_2^w$. Since $\iota$ also satisfies the hypotheses of Proposition 2.3.11, with $k_0 = 2$, it is 2-discriminating on $\mathcal{D}_i^{w^{(3)}}$. Thus $f$ is in $\mathcal{C}^{w^{(3)}}$, and in $\mathcal{C}^{w^{(3)}}|_{S_C}$ since its 1-target is a normal form. $\square$

**Example 5.3.3.** In the case where $\mathcal{A} = \text{Assoc}$, the set $\mathcal{D}_2$ contains one additional 2-cell:

$$ \mathcal{A} := \bar{\mathcal{A}} $$

And the following cells are composites in $\mathcal{D}^w$:

<figure><img src="image_79.png" /></figure>

Note that the equality $\mathcal{D}^{w^{(3)}}|_{S_D} = \mathcal{C}^{w^{(3)}}|_{S_C}$ implies that none of these composites belongs to $\mathcal{D}^{w^{(3)}}|_{S_D}$.

## 5.4 Adjunction of connections between 2-cells

Let $\mathcal{E}$ be the following 4-white-polygraph:

* For $i = 0, 1, 2$, $\mathcal{E}_i = \mathcal{D}_i$,

* For $i = 3$, $\mathcal{E}_3 = \mathcal{D}_3 \cup \{\eta_f, \epsilon_f | f \in \mathcal{C}_2\}$.

* For $i = 4$, $\mathcal{E}_4 = \mathcal{D}_4 \cup \{\tau_f, \sigma_f | f \in \mathcal{C}_2\}$.

The cells $\eta_f$, $\epsilon_f$, $\tau_f$ and $\sigma_f$ have the following shape:

$$ \bullet \quad \epsilon_f : \bar{f} \star_1 f \Rightarrow 1_{\mathbf{t}(f)} $$

$$ \bullet \quad \eta_f : 1_{\mathbf{s}(f)} \Rightarrow f \star_1 \bar{f} $$

<figure><img src="image_80.png" /></figure>

$$ \bullet \quad \tau_f : (\bar{f} \star_1 \eta_f) \star_2 (\epsilon_f \star_1 \bar{f}) \Rightarrow 1_{\bar{f}} $$

<figure><img src="image_81.png" /></figure>

$$ \bullet \quad \sigma_f : (\eta_f \star_1 f) \star_2 (f \star_1 \epsilon_f) \Rightarrow 1_f $$

<figure><img src="image_82.png" /></figure>
**Notation 5.4.1.** Let us denote by $\cup$ the 3-cell $\epsilon_f$ and $\cap$ the 3-cell $\eta_f$. In a similar fashion, we denote by $\text{⊙}$ for $\sigma_f$ and $\text{⊙}$ for $\tau_f$:

<figure><img src="image_83.png" /></figure>

Let $\mathcal{R} := \{\sigma_f, \tau_f\}$, and $\mathcal{R}^w$ (resp. $\mathcal{R}^{w^{(3)}}$) be the sub-4-white-category (resp. sub-(4,3)-white-category) of $\mathcal{E}^{w^{(3)}}$ generated by the cells in $\mathcal{R}$. A 4-cell of length 1 in $\mathcal{R}^w$ is called an $\mathcal{R}$-rewriting step.

Let $S_{\mathcal{E}}$ be the set of all 2-cells of the sub-2-white-category $C_2^w$ of $\mathcal{E}_2^w$ whose target is a normal form. Using properties of the rewriting system induced by $\mathcal{R}^w$, we are going to define a functor $K : \mathcal{E}^{w^{(3)}}|_{S_{\mathcal{E}}} \to \mathcal{D}^{w^{(3)}}|_{S_{\mathcal{D}}}$.

**Lemma 5.4.2.** Let $\alpha \in \mathcal{E}_4^w$ and $\beta \in \mathcal{R}^w$ of length 1 with the same source. There exist $\alpha' \in \mathcal{E}_4^w$ and $\beta' \in \mathcal{R}^w$ of maximum length 1, such that:

<figure><img src="image_84.png" /></figure>

*Proof.* The result holds whenever $(\alpha, \beta)$ is a Peiffer or aspherical branching.

If $(\alpha, \beta)$ is an overlapping branching, then the source of $\alpha$ must contain an $\eta_f$ or an $\epsilon_f$. The only cells of length 1 in $\mathcal{E}_4^w$ that satisfy this property are those in $\mathcal{R}^w$. Hence $\alpha$ is in $\mathcal{R}^w$. Thus the branching $(\alpha, \beta)$ is one of the following two, and both of them satisfy the required property:

<figure><img src="image_85.png" /></figure>

<figure><img src="image_86.png" /></figure>

**Lemma 5.4.3.** The rewriting system generated by $\mathcal{R}$ is 4-convergent.

*Proof.* Using Lemma 5.4.2, the rewriting system generated by $\mathcal{R}$ is locally 4-confluent. Moreover, the cells $\sigma_f$ and $\tau_f$ decrease the length of the 3-cells, hence the 4-termination. $\square$

<figure><img src="image_87.png" /></figure>

Let $A \in \mathcal{E}_3^w$: we denote by $\hat{A} \in \mathcal{E}_3^w$ its normal form for $\mathcal{R}$. Remark in particular that if $A$ is in $\mathcal{D}_3^w$, then $\hat{A} = A$.

**Lemma 5.4.4.** Let $A$ be a 3-cell of $\mathcal{E}_3^w$ whose target is in $C_2^w$.

* If the source of $A$ is in $C_2^w$, then $\hat{A}$ is in $\mathcal{D}_3^w$.

* Otherwise, for every factorization of $A$ into $f_1 \star_1 \bar{f} \star_1 f_2$, where $f$ is a rewriting step, there exists a factorisation of $A$ into:

<figure><img src="image_88.png" /></figure>
*Proof.* We reason by induction on the length of $A$. If $A$ is of length 0, then the source of $A$ is in $C_2^w$, and $\hat{A} = A$ is in $D_3^w$.

If $A$ is of length $n > 0$, let us write $A = B_1 \star_1 B_2$, where $B_1$ is of length 1. We can then apply the induction hypothesis to $B_2$. We distinguish three cases:

* If both the sources of $A$ and $B_2$ are in $C_2^w$, then $B_1$ is in $D_3^w$, and so is $\hat{A} = B_1 \star_2 \hat{B}_2$.

* If the source of $A$ is in $C_2^w$ but not that of $B_2$, then $B_1$ is of the form $g_1 \star_1 \eta_f \star_1 g_2$. There hence exists a factorisation $(g_1 \star_1 f) \star_1 \bar{f} \star_1 g_2$ of the source of $B_2$. Applying the induction hypothesis to $B_2$, we deduce the following factorisation of $A$:

<figure><img src="image_89.png" /></figure>

In particular, $A$ is the source of an $\mathcal{R}$-rewriting step. Let $A'$ be its target, which is thus of length smaller than $A$. Applying the induction hypothesis to $A'$, we get that $\hat{A} = \hat{A}'$ is in $D_3^w$.

* There remains the case where the source of $A$ is not an element of $C_2^w$.

In order to treat this last case, let us fix a factorisation $f_1 \star_1 \bar{f} \star_1 f_2$ of the source of $A$, where $f$ is of length 1. We distinguish three cases depending on the form of $B_1$.

* If $B_1 = f_1 \star_1 \bar{f} \star_1 B_1'$, where $B_1'$ is a 3-cell of length 1 from $f_2$ to $g_2 \in D_2^w$, then we get a factorisation of the source of $B$ into $f_1 \star_1 \bar{f} \star_1 g_2$. Let us apply the induction hypothesis to $B_2$: there exist $A_1', A_2' \in \mathcal{E}_3^w$ and $g_2' \in D_2^w$ such that:

$$B_2 = (f_1 \star_1 \bar{f} \star_1 A_1') \star_2 (f_1 \star_1 \epsilon_f \star_1 g_2') \star_2 A_2'$$

Thus $A$ factorises as follows, which is of the required form by setting $A_1 = B_1' \star_2 A_1'$ and $A_2 = A_2'$:

<figure><img src="image_90.png" /></figure>

* If $B_1 = B_1' \star_1 \bar{f} \star_1 f_2$, where $B_1'$ is a 3-cell of length 1 from $f_1$ to $g_1 \in D_2^w$. Then the source of $B$ factorises into $g_1 \star_1 \bar{f} \star_1 f_2$. Applying the induction hypothesis to $B_2$, there exist $A_1', A_2' \in \mathcal{E}_3^w$ and $f_2' \in D_2^w$ such that:

$$B_2 = (g_1 \star_1 \bar{f} \star_1 A_1') \star_2 (g_1 \star_1 \epsilon_f \star_1 f_2') \star_2 A_2'$$

We get the required factorisation of $A$ by setting $A_1 = A_1'$ and $A_2 = (B_1' \star_1 f_2') \star_2 A_2'$.

<figure><img src="image_91.png" /></figure>
• Otherwise, we have $B_1 = f_1 \star_1 \epsilon_f \star_1 f'_2$, with $f_2 = f \star_1 f'_2$. We then get the required factorisation of $A$ by setting $A_1 = 1_{f'_2}$ and $A_2 = B_2$.

<figure><img src="image_92.png" /></figure>

□

**Lemma 5.4.5.** Let $\beta \in \mathbb{R}^w$, and $\alpha$ be a 4-cell $\mathcal{E}_4^w$ of same source. There exist $\alpha' \in \mathcal{E}_4^w$ and $\beta' \in \mathbb{R}^w$ of maximum length that of $\beta$ such that we have the following square:

<figure><img src="image_93.png" /></figure>

*Proof.* We reason using a double induction on the lengths of $\beta$ and $\alpha$. If $\beta$ (resp. $\alpha$) is an identity, then the result holds by setting $\alpha' = \alpha$ (resp. $\beta' = \beta$).

Otherwise, let us write $\alpha = \alpha_1 \star_3 \alpha_2$ and $\beta = \beta_1 \star_3 \beta_2$, where $\alpha_1$ and $\beta_1$ are of length 1. We can then construct the following diagram:

<figure><img src="image_94.png" /></figure>

The 4-cells $\alpha'_1$ and $\beta'_1$ exist thanks to Lemma 5.4.2. We can then apply the induction hypothesis to the 4-cells $\alpha_2$ and $\beta'_1$ (resp. $\alpha'_1$ and $\beta_2$) and we construct this way the cells $\alpha'_2$ and $\beta''_1$ (resp. $\alpha''_1$ and $\beta'_2$). Lastly, we apply the induction hypothesis to $\alpha'_2$ et $\beta'_2$ in order to construct $\alpha''_2$ and $\beta''_2$. $\square$

**Lemma 5.4.6.** The application $A \mapsto \hat{A}$ extends into a 1-functor $K : \mathcal{E}^{w(3)}|_{S_\mathcal{E}} \to \mathcal{D}^{w(3)}|_{S_\mathcal{D}}$, which is the identity on objects.

*Proof.* The application $A \mapsto \hat{A}$ does not change the source or target. Moreover, given a 3-cell $A \in \mathcal{E}^{w(3)}$, if $A$ is in $\mathcal{E}^{w(3)}|_{S_\mathcal{E}}$ then in particular the source and target of $A$ are in $C_2^w$. Thus $\hat{A}$ is in $\mathcal{D}_3^w|_{S_\mathcal{D}}$ (Lemma 5.4.4).

Let $A, B$ be 3-cells in $\mathcal{E}^{w(3)}$ which belong to $\mathcal{E}^{w(3)}|_{S_\mathcal{E}}$. We just showed that $\hat{A}$ and $\hat{B}$ are in $\mathcal{D}_3^w|_{S_\mathcal{D}}$, hence so is $\hat{A} \star_2 \hat{B}$. So $\hat{A} \star_2 \hat{B}$ is a normal form for $\mathcal{R}$ which is attainable from $A \star_2 B$. Since $\mathcal{R}$ is 4-convergent, this means that $\hat{A} \star_2 \hat{B} = \hat{A} \star_2 \hat{B}$. So $A \mapsto \hat{A}$ does indeed define a functor. $\square$

**Proposition 5.4.7.** The pointed (4,3)-category $(\mathcal{E}, S_\mathcal{E})$ is stronger than $(\mathcal{D}, S_\mathcal{D})$.
Proof. Let us first start by showing that, for every non-aspherical 3-fold minimal symmetrical branching $b$, there exists a representative $(f, g, h)$ of $b$ for which the property holds. If $b$ is an overlapping branching then, using the fact that $\mathcal{A}$ satisfies the 2-Squier condition of depth 2, the cell $A_{f,g,h}$ exists for some representative $(f, g, h)$ of $b$. Otherwise $b$ is a Peiffer branching, and we conclude using the cells defined in Section 5.1.

It remains to show that the set of all branchings satisfying the property is closed under the action of the symmetric group.

* If $(f_1, f_2, f_3)$ satisfies the property, then so does $(f_3, f_2, f_1)$. Indeed, let $A := A_{f_1, f_2, f_3}$, and let us denote its source by $s$ and its target by $t$, all we need to construct is a 4-cell from $s^{op}$ to $t^{op}$. This is given by the following composite:

$$ \begin{tikzcd} s^{op} \arrow[r, "t^{op} \star_2 \lambda_t^{-1}"] \arrow[d, "s^{op} \star_2 \lambda_t^{-1}"] & t^{op} \star_2 t \star_2 s^{op} \arrow[r, "t^{op} \star_2 A^{-1} \star_2 s^{op}"] \arrow[d, "t^{op} \star_2 \rho_s"] & t^{op} \star_2 s \star_2 s^{op} \arrow[r, "t^{op} \star_2 \rho_s"] \arrow[d, "t^{op} \star_2 \lambda_s^{-1}"] & s^{op} \end{tikzcd} $$

* If $(f_1, f_2, f_3)$ satisfies the property, then so does $(f_2, f_1, f_3)$. Indeed, given a cell $A_{f_1, f_2, f_3}$, we can construct the following composite:

<figure><img src="image_95.png" /></figure>

Since the transpositions (1 2) and (1 3) generate the symmetric group, the set of all branchings satisfying the property is closed under the action of the symmetric group. $\square$

We are now going to apply a series of Tietze-transformations to $\mathcal{E}$ in order to mimic a technique known as *reversing*. Reversing is a combinatorial tool to study presented monoids [4]. Reversing is particularly adapted to monoids whose presentation contains no relation of the form $su = sv$, where $s$ is a generator and $u$ and $v$ words in the free monoid, and at most one relation of the form $su = s'v$, for $s$ and $s'$ generators. The (4, 2)-polygraph $\mathcal{A}$ satisfies those properties, but only up to a dimensional shift: there are no 3-cell in $\mathcal{A}_3$ of the form $f \star_2 g \Rightarrow f \star_2 h$, where $f$ is of length 1 and $g$ and $h$ are in $\mathcal{A}_2^w$, and there is at most one 3-cell in $\mathcal{A}_3$ of the form $f \star_2 g \Rightarrow f' \star_2 h$, where $f$ and $f'$ are of length 1. Hence we adapt this method to our higher-dimensional setting.
**Adjunction of 3-cells $C_{f,g}$ with its defining 4-cell $X_{f,g}$.** For every non-aspherical branching $(f,g)$, we add a 3-cell $C_{f,g}$ of the following shape:

<figure><img src="image_96.png" /></figure>

using as defining 4-cell a cell $X_{f,g}$ whose target is $C_{f,g}$ and whose source is the composite:

<figure><img src="image_97.png" /></figure>

**Adjunction of a superfluous 4-cell $Y_{f,g}$.** We add a 4-cell $Y_{f,g}$ of target $A_{g,f}$, parallel to the following 4-cell (where the second step consists in the parallel application of $\sigma_f$ and $\sigma_{g'}$):

<figure><img src="image_98.png" /></figure>
**Removal of the superfluous 4-cell $X_{f,g}$.** We remove the 4-cell $X_{f,g}$, using the fact that it is parallel to the following composite:

<figure><img src="image_99.png" /></figure>

**Removal of the 3-cell $A_{g,f}$ with its defining 4-cell $Y_{f,g}$.** This last step is possible because $A_{g,f}$ is the target of $Y_{f,g}$ and does not appear in its source.

We denote by $\mathcal{F}$ the 4-white-polygraph obtained after performing this series of Tietze-transformations for every non-aspherical branching $(f,g)$, and $\Pi: \mathcal{E}^{w^{(3)}} \to \mathcal{F}^{w^{(3)}}$ the 3-white-functor induced by the Tietze-transformations. We still denote by $A_{g,f}$ the composite in $\mathcal{F}_4^{w^{(3)}}$, image by $\Pi$ of $A_{f,g} \in \mathcal{E}_4$.

**Example 5.5.3.** In the case where $\mathcal{A} = \text{Assoc}$, the cells $\overleftarrow{\mathcal{A}}$ and $\overleftarrow{\mathcal{A}}^{op}$ respectively associated to the branchings $(\mathcal{Y} | , | \mathcal{Y})$ and $(| \mathcal{Y} , \mathcal{Y} |)$ have been replaced by cells of the following shape:

<figure><img src="image_100.png" /></figure>
# 6 Proof of Theorem 1.4.9

This Section concludes the proof of Theorem 1.4.9. We keep the notations from Section 5. In Section 6.1, we study the 4-cells of the (4, 3)-white-category $\mathcal{F}^{w^{(3)}}$, and in particular study the consequences of $\mathcal{A}$ satisfying the 2-Squier condition of depth 2.

In Section 6.2, we define a well-founded ordering on $N[\mathcal{F}_1^w]$, the free commutative monoid on $\mathcal{F}_1^w$. Using this ordering together with two applications $\mathbf{p}: \mathcal{F}_2^w \to N[\mathcal{F}_1^w]$ and $\mathbf{w}_\eta: \mathcal{F}_3^w \to N[\mathcal{F}_1^w]$, we proceed to complete the proof by induction in Section 6.3.

## 6.1 Local coherence

**Definition 6.1.1.** We extend the notation $C_{f,g}$ from Section 5.5 by defining, for every local branching $(f,g)$ of $\mathcal{B}_2^w$, a 3-cell of the form $C_{f,g}: \bar{f} \star_1 g \Rightarrow f' \star_1 \bar{g}' \in \mathcal{F}_3^w$, where $f'$ and $g'$ are in $\mathcal{B}_2^w$.

* If $(f,g)$ is a minimal overlapping or Peiffer branching, then $C_{f,g}$ is already defined.

* If $(f,g)$ is aspherical, then we set $C_{f,g} = \epsilon_f$.

* If $(f,g)$ is not minimal, then let us write $(f,g) = (u\tilde{f}v, u\tilde{g}v)$, with $(\tilde{f}, \tilde{g})$ a minimal branching, and we set $C_{f,g} := uC_{\tilde{f},\tilde{g}}v$.

**Definition 6.1.2.** We say that a 3-fold local branching $(f,g,h)$ of $\mathcal{A}_2$ is coherent if there exists a 4-cell $C_{f,g,h} \in \mathcal{F}_4^{w^{(3)}}$ of the following shape, where $A$ and $B$ are 4-cells in $\mathcal{F}_3^w$.

<figure><img src="image_101.png" /></figure>

**Lemma 6.1.3.** Every 3-fold local branching of $\mathcal{B}_2^w$ is coherent.

*Proof.* Let $(f,g,h)$ be a minimal local branching. We first treat the case where $(f,g,h)$ is an aspherical branching. If $f = g$, then $C_{f,g} = \epsilon_f$, and the following cell shows that the branching is coherent:

<figure><img src="image_102.png" /></figure>

The case where $g = h$ is symmetrical. Assume now $g \neq f, h$ and $f = h$. Then $(f,g)$ is either an overlapping or a Peiffer branching. In any case there exists either a cell $A_{f,g}$ or $A_{g,f}$ in $\mathcal{E}_3^w$. In the former case, we can construct the following cell in $\mathcal{F}_4^{w^{(3)}}$.
<figure><img src="image_103.png" /></figure>

In the latter, we can construct the same cell, only replacing $\Pi(\rho_{A_{f,g}})$ by $\Pi(\lambda_{A_{f,g}})$.

Suppose now that $(f, g, h)$ is not aspherical. Using the cell $A_{f,g,h}$ described in Lemma 5.5.2, we build the following composite in $\mathcal{F}_4^{w^{(3)}}:$

<figure><img src="image_104.png" /></figure>

Finally, if $(f, g, h)$ is not aspherical, then there exists a 3-fold minimal branching $(\tilde{f}, \tilde{g}, \tilde{h})$ of $\mathcal{B}_1^w$ and 1-cells $u, v \in \mathcal{B}_1^w$ such that $(f, g, h) = (u\tilde{f}v, u\tilde{g}v, u\tilde{h}v)$. Then the cell $uC_{\tilde{f}, \tilde{g}, \tilde{h}}v$ shows that $(f, g, h)$ is coherent. $\square$
## 6.2 Orderings on the cells of $\mathcal{F}^w$

**Definition 6.2.1.** Let $E$ be a set. The set of all finite multi-sets on $E$ is $\mathbb{N}[E]$, the free commutative monoid over $E$. For every $e \in E$, let $\mathbf{v}_e : \mathbb{N}[E] \to \mathbb{N}$ be the morphism of monoids that sends $e$ to 1 and every other elements of $E$ to 0.

If $E$ is equipped with a strict ordering $>$, we denote by $>_{m}$ the strict ordering on $\mathbb{N}[E]$ defined as follows: for every $f, g \in \mathbb{N}[E]$, one has $f >_{m} g$ if

* $f \neq g$

* For every $e \in E$, if $\mathbf{v}_e(f) < \mathbf{v}_e(g)$, then there exists $e' > e$ such that $\mathbf{v}_{e'}(f) > \mathbf{v}_{e'}(g)$.

**Lemma 6.2.2.** Let $E$ be a set and $a \in E$. The set of all $f \in \mathbb{N}[E]$ such that $f < a$ is equal to the set of all $f \in \mathbb{N}[E]$ satisfying the following implication for every $b \in E$:

$$ \mathbf{v}_b(f) > 0 \Rightarrow b < a. $$

In particular, this set is a sub-monoid of $\mathbb{N}[E]$.

*Proof.* Let $f \in \mathbb{N}[E]$ such that for every $b \in E$ the implication $\mathbf{v}_b(f) > 0 \Rightarrow b < a$ is verified. Let us prove that $f <_{m} a$. Necessarily $\mathbf{v}_a(f) = 0$, otherwise we would have $a < a$. Thus in particular $f \neq a$. Moreover, let $b \in E$ such that $\mathbf{v}_b(f) > \mathbf{v}_b(a) \geq 0$. By definition of $f$ this implies that $b < a$, and since $0 = \mathbf{v}_a(f) < \mathbf{v}_a(a) = 1$ we get that $f < m_a$.

Conversely, let $f <_{m} a$. Let us show by contradiction that $\mathbf{v}_a(f) = 0$. If $\mathbf{v}_a(f) \neq 0$, we distinguish two cases:

* If $\mathbf{v}_a(f) = 1$, then since $f \neq a$, there exists $b \neq a \in E$ such that $\mathbf{v}_b(f) > 0$. Thus because $f < a$, there exists $c > b \in E$ such that $\mathbf{v}_c(f) < \mathbf{v}_c(a)$. So we necessarily have $\mathbf{v}_c(a) \geq 1$, which implies that $c = a$. The condition $\mathbf{v}_c(f) < \mathbf{v}_c(a)$ thus becomes $\mathbf{v}_a(f) < 1$, which contradicts the hypothesis that $\mathbf{v}_a(f) = 1$.

* If $\mathbf{v}_a(f) > 1$, then there exists $b > a$ such that $\mathbf{v}_b(a) > \mathbf{v}_b(f)$, which is impossible.

Hence necessarily $\mathbf{v}_a(f) = 0$.

Let $b \in E$ such that $\mathbf{v}_b(f) > 0$, and let us show that $b < a$. We just showed that $b \neq a$, and so $\mathbf{v}_b(f) > \mathbf{v}_b(a)$. Thus there exists $c > b$ such that $\mathbf{v}_c(a) > \mathbf{v}_c(f)$. In particular this implies $\mathbf{v}_c(a) > 0$. So $c = a$ and finally $a > b$. $\square$

**Lemma 6.2.3.** Let $(E, <)$ be a set equipped with a strict ordering. The relation $>_{m}$ is compatible with the monoidal structure on $\mathbb{N}(E)$, that is, for every $f, f', g \in \mathbb{N}(E)$, if $f >_{m} f'$, then $f + g >_{m} f' + g$.

*Proof.* Let $f, f', g \in \mathbb{N}(E)$, and suppose that $f >_{m} f'$. Let us show that $f + g >_{m} f' + g$. Firstly, $f \neq f'$, hence $f + g \neq f' + g$.

Let $e \in E$ such that $\mathbf{v}_e(f + g) < \mathbf{v}_e(f' + g)$. Since $\mathbf{v}_e$ is a morphism of monoids, this implies that $\mathbf{v}_e(f) < \mathbf{v}_e(f')$. Hence there exists $e' > e$ such that $\mathbf{v}_{e'}(f) > \mathbf{v}_{e'}(f')$, and so $\mathbf{v}_{e'}(f + g) > \mathbf{v}_{e'}(f' + g)$ $\square$

The proof of the following theorem can be found in [1].

**Theorem 6.2.4.** Let $(E, >)$ be a set equipped with a strict ordering. Then $>_{m}$ is a well-founded ordering if and only if $>$ is.

Since $\mathcal{A}$ is 2-terminating, the set $\mathcal{A}_1^*$ is equipped with a well-founded ordering $\Rightarrow$. This induces a well founded ordering $\Rightarrow_m$ on $\mathbb{N}[\mathcal{A}_1^*]$. We now define two applications $\mathbf{p} : \mathcal{F}_2^w \to \mathbb{N}[\mathcal{A}_1^*]$ and $\mathbf{w}_\eta : \mathcal{F}_3^w \to \mathbb{N}[\mathcal{A}_1^*]$. Using $\Rightarrow_m$, those applications induce well-founded orderings on $\mathcal{F}_2^w$ and $\mathcal{F}_3^w$. We then show a number of properties of these applications in preparation for Section 2.2.

**Definition 6.2.5.** We define an application $\mathbf{p} : \mathcal{F}_2^w \to \mathbb{N}[\mathcal{A}_1^*]$:

* for every $f \in \mathcal{F}_2^w$ of length 1, we set $\mathbf{p}(f) := \mathbf{s}(f) + \mathbf{t}(f)$,

* for every composable $f_1, f_2 \in \mathcal{F}_2^w$, we set $\mathbf{p}(f_1 \star_1 f_2) := \mathbf{p}(f_1) + \mathbf{p}(f_2)$.

For every $f, g \in \mathcal{F}_2^w$, we set $f > g$ if $\mathbf{p}(f) \Rightarrow_m \mathbf{p}(g)$. The relation $>$ is a well-founded ordering of $\mathcal{F}_2^w$.
**Definition 6.2.6.** We define an application $\mathbf{w}_\eta : \mathcal{F}_3^\mathbf{w} \to \mathbb{N}[\mathcal{A}_1^*]$ by setting:

* For every $f \in \mathcal{B}_2^\mathbf{w}$ of length 1, $\mathbf{w}_\eta(\eta_f) = \mathbf{s}(f)$.

* For every 3-cell $A \in \mathcal{F}_3$ and $u, v \in \mathcal{A}_1^*$, if $A$ is not an $\eta_f$ then $\mathbf{w}_\eta(uAv) = 0$.

* For every $f_1, f_2 \in \mathcal{F}_2^\mathbf{w}$ and $A \in \mathcal{F}_3^\mathbf{w}$, $\mathbf{w}_\eta(f_1 \star_1 A \star_1 f_2) = \mathbf{w}_\eta(A)$.

* For every $A_1, A_2 \in \mathcal{F}_3^\mathbf{w}$, $\mathbf{w}_\eta(A_1 \star_2 A_2) = \mathbf{w}_\eta(A_1) + \mathbf{w}_\eta(A_2)$.

**Definition 6.2.7.** A product of the form $\bar{f} \star_1 g \in \mathcal{F}_2^\mathbf{w}$, where $f$ and $g$ are nonempty cells in $\mathcal{B}_2^\mathbf{w}$ is called a *cavity*. It is a *local cavity* if $f$ and $g$ are of length 1. Let $C_\mathcal{F}$ be the set of all cavities.

**Lemma 6.2.8.** Let $f, g \in \mathcal{B}_2^\mathbf{w}$. Suppose $f$ is not an identity and $\mathbf{t}(f) = \mathbf{s}(g)$. The following inequality holds:

$$ \mathbf{s}(f) > \mathbf{p}(g) $$

*Proof.* We reason by induction on the length of $g$. If $g$ is empty, then $\mathbf{p}(g) = 0 < \mathbf{s}(f)$.

Otherwise, let us write $g = g_1 \star_1 g_2$, with $g_1$ of length 1. Then $\mathbf{p}(g) = \mathbf{p}(g_1) + \mathbf{p}(g_2)$ and by induction hypothesis $\mathbf{p}(g_2) < \mathbf{s}(f \star_1 g_1) = \mathbf{s}(f)$. Moreover we have $f : \mathbf{s}(f) \Rightarrow \mathbf{s}(g_1)$ and $f \star_1 g_1 : \mathbf{s}(f) \Rightarrow \mathbf{t}(g_1)$. Hence $\mathbf{s}(f) > \mathbf{p}(g_1)$, $\mathbf{s}(g_2)$, $\mathbf{t}(g_2)$ and, by Lemma 6.2.2, we get $\mathbf{s}(f) > \mathbf{p}(g_1) + \mathbf{s}(g_2) + \mathbf{t}(g_2) = \mathbf{p}(g)$. $\square$

**Lemma 6.2.9.** Let $f_1, f_2, g_1, g_2 \in \mathcal{B}_2^\mathbf{w}$, with $f_1$ and $f_2$ non-empty and of same source $u$. For every 3-cell $A : \bar{f}_1 \star_1 f_2 \Rightarrow g_1 \star_1 \bar{g}_2 \in \mathcal{F}_3^\mathbf{w}$, the following inequalities hold:

$$ \mathbf{p}(\mathbf{s}(A)) > u > \mathbf{p}(\mathbf{t}(A)). $$

In particular for every cell $C_{f,g}$, we have $\mathbf{s}(C_{f,g}) > \mathbf{t}(C_{f,g})$.

*Proof.* Considering the first inequality, we have $\mathbf{p}(\mathbf{s}(A)) = \mathbf{p}(f_1) + \mathbf{p}(g_2) \geq 2u > u$.

Considering the second one, using Lemma 6.2.8, we have the inequalities $u = \mathbf{s}(f_1) > \mathbf{p}(g_1)$ and $u = \mathbf{s}(f_2) > \mathbf{p}(g_2)$. By 6.2.2, we then have $u > \mathbf{p}(g_1) + \mathbf{p}(g_2) = \mathbf{p}(\mathbf{t}(A))$. $\square$

**Definition 6.2.10.** Let $h \in \mathcal{F}_2^\mathbf{w}$. A factorisation $h = h_1 \star_1 \bar{f}_1 \star_1 f_2 \star_1 h_2$ of $h$, with $f_1, f_2 \in \mathcal{B}_2^\mathbf{w}$ of length 1 and $h_1, h_2 \in \mathcal{F}_2^\mathbf{w}$ is called a *cavity-factorisation* of $h$. Thus a cavity-factorisation is represented as follows:

<figure><img src="image_105.png" /></figure>

**Lemma 6.2.11.** Let $h \in \mathcal{F}_2^\mathbf{w}$ be a 2-cell which is not an identity, and whose source and target are a normal form for $\mathcal{A}_2$. Then there exists a cavity-factorisation of $h$.

*Proof.* By definition of $\mathcal{F}_2^\mathbf{w}$, there exist $n \in \mathbb{N}^*$ and $g_1, \dots, g_{2n} \in \mathcal{B}_2^\mathbf{w}$ all not identities, except possibly $g_1$ or $g_{2n}$, such that $h = \bar{g}_1 \star_1 g_2 \star_1 \dots \star_1 \bar{g}_{2n-1} \star_1 g_{2n}$.

Let us show that $g_1$ and $g_{2n}$ are not identities:

* If $g_1$ is an identity, then since $h$ isn't, either $n \geq 2$ or $n = 1$ and $g_{2n}$ is not an identity. In both cases $g_2$ is of length at least 1, and has $\mathbf{s}(h)$ as target, which contradicts the fact that $\mathbf{s}(h)$ is a normal form for $\mathcal{A}_2$.

* The case where $g_{2n}$ is an identity is symmetric.

Therefore the 2-cells $g_1$ and $g_2$ are of length at least 1. So we can write $g_1 = f_1 \star_1 g'_1$ and $g_2 = f_2 \star_1 g'_2$, with $f_1, f_2 \in \mathcal{B}_2^\mathbf{w}$ of length 1. Let $h_1 := \bar{g}'_1$ and $h_2 := g'_2 \star_1 \bar{g}_3 \star_1 g_4 \star_1 \dots \star_1 \bar{g}_{2n-1} \star_1 g_{2n}$. We finally get: $h = h_1 \star_1 \bar{f}_1 \star_1 f_2 \star_1 h_2$. $\square$

**Lemma 6.2.12.** Let $h \in \mathcal{F}_2^\mathbf{w}$ be a 2-cell of source and target $\hat{u}$, a normal form for $\mathcal{A}_2$. There exists a 3-cell $A : h \Rightarrow 1_{\hat{u}}$ such that $\mathbf{w}_\eta(A) = 0$.
**Proof.** We reason by induction on $h$ using the ordering $>$. If $h$ is minimal, then $h = 1_{\hat{u}}$ and we can set $A := 1_h$.

Otherwise by Lemma 6.2.11 there exists a cavity-factorisation $h = h_1 \star_1 f_1 \star_1 f_2 \star_1 h_2$ of $h$. Let $A_1 := C_{f_1, f_2}$: we have $w_\eta(A_1) = 0$ and by Lemma 6.2.9, $s(A_1) > t(A_1)$. Since the ordering is compatible with composition, we get $h > h_1 \star_1 t(A_1) \star_1 h_2$. By induction hypothesis, there exists a 3-cell $A_2 : h_1 \star_1 t(A_1) \star_1 h_2 \Rightarrow 1_{\hat{u}} \in \mathcal{F}_3^w$ such that $w_\eta(A_2) = 0$.

Let $A := (h_1 \star_1 A_1 \star_1 h_2) \star_1 A_2$. We have $w_\eta(A) = w(h_1 \star_1 A_1 \star_1 h_2) + w(A_2) = w(A_1) + 0 = 0$. $\square$

**Lemma 6.2.13.** Let $h \in \mathcal{F}_2^w$ of source and target $\hat{u}$ a normal form for $A_2$, and $A : h \Rightarrow 1_{\hat{u}} \in \mathcal{F}_3^w$. For every cavity-factorisation $h = h_1 \star_1 \bar{f}_1 \star_1 f_2 \star_1 h_2$, there exists a factorisation of $A = (h_1 \star_1 A_1 \star_1 h_2) \star_2 A_2$, with $A_1, A_2 \in \mathcal{F}_3^w$, and either $A_1 = C_{f_1, f_2}$ or $A_1 = \bar{f}_1 \star_1 \eta_{f_3} \star_1 f_2$, with $f_3 \in \mathcal{B}_2^w$ of length 1.

**Proof.** We reason by induction on the length of $A$. If $A$ is of length 0, then there is no cavity-factorisation of $h = 1_{\hat{u}}$ and the result holds.

If $A$ is not of length 0, let $h = h_1 \star_1 \bar{f}_1 \star_1 f_2 \star_1 h_2$ be a cavity-factorisation of $h$. Let us write $A = B \star_1 C$, where $B$ is of length 1. If $B$ is not of the required form, then either $B = B' \star_1 \bar{f}_1 \star_1 f_2 \star_1 h_2$, or $B = h_1 \star_1 \bar{f}_1 \star_1 f_2 \star_1 B'$. Let us treat the first case, the second being symmetrical. The source of $C$ admits a cavity-factorisation $s(C) = t(B') \star_1 \bar{f}_1 \star_1 f_2 \star_1 h_2$. By induction hypothesis, we can factorise $C$ as follows:

$$C = (h'_1 \star_1 A_1 \star_1 h_2) \star_2 C'$$

with $A_1 = C_{f_1, f_2}$ or $A_1 = \bar{f}_1 \star_1 \eta_{f_3} \star_1 f_2$. Let $A_2 := (B'_1 \star_1 t(A_1) \star_1 h_2) \star_2 C_2$: we then have $A = (h_1 \star_1 A_1 \star_1 h_2) \star_2 A_2$.

<figure><img src="image_106.png" /></figure>

$\square$

**Lemma 6.2.14.** Let $h \in \mathcal{F}_2^w$ and $u \in A_1^*$ such that $u > \mathbf{p}(h)$, $u > \mathbf{s}(h)$ and $u > \mathbf{t}(h)$. For every 3-cell $A \in \mathcal{F}_3^w$ of source $h$, the inequality $u > w_\eta(A)$ holds.

**Proof.** We reason by induction on the length of $A$. If $A$ is of length 0, $w_\eta(A) = 0$ and the result holds.

Otherwise, let us write $A = A_1 \star_2 A_2$, with $A_1$ of length 1. We distinguish two cases depending on the shape of $A_1$.

* If $A_1 = h_1 \star_1 \eta_f \star_1 h_2$, with $h_1, h_2 \in \mathcal{F}_2^w$ and $f \in \mathcal{B}_2^w$ of length 1.

If $h_1$ and $h_2$ are empty, then $s(A_2) = f \star_1 \bar{f}$. Thus $\mathbf{p}(s(A_2)) = 2\mathbf{s}(f) + 2\mathbf{t}(f) \le 4\mathbf{s}(f) = 4\mathbf{s}(h)$. Since $\mathbf{s}(h) < u$, using Lemma 6.2.2, we get that $\mathbf{p}(s(A_2)) < u$. Applying the induction hypothesis to $A_2$, we get $w_\eta(A_2) < u$. Moreover, $w_\eta(A) = w_\eta(A_1) + w_\eta(A_2) = \mathbf{s}(f) + \mathbf{w}(A_2)$, and we showed that $\mathbf{w}(A_2) < u$ and $\mathbf{s}(f) = \mathbf{s}(h) < u$. Thus according to Lemma 6.2.2, we get $w_\eta(A) < u$.

Otherwise, suppose for example that $h_1$ is not an identity (the case where $h_2$ is not an identity being symmetrical). Then we have $\mathbf{v}_{\mathbf{t}(h_1)}(\mathbf{p}(h_1)) > 0$, so $\mathbf{v}_{\mathbf{t}(h_1)}(\mathbf{p}(h)) > 0$. Since $\mathbf{p}(h) < u$, we have by Lemma 6.2.2 that $\mathbf{s}(f) = \mathbf{t}(h_1) < u$. So $\mathbf{p}(s(A_2)) = \mathbf{p}(h_1) + \mathbf{p}(h_2) + 2\mathbf{s}(f) + 2\mathbf{t}(f) < \mathbf{p}(h) + 4\mathbf{s}(f) < u$. By induction hypothesis, we thus have $w_\eta(A_2) < u$, and finally $w_\eta(A) = \mathbf{s}(f) + w_\eta(A_2) < u$.

* Otherwise, we have on the one hand that $w_\eta(A_1) = 0$, and on the other hand that $s(A_2) = t(A_1) < s(A_1) = h < u$ by Lemma 6.2.9. Thus $w_\eta(A) = w_\eta(A_2) < u$.

$\square$

**Lemma 6.2.15.** Let $(f_1, f_2, f_3)$ be a 3-fold local branching, $u \in A_1^*$, and $A, B \in \mathcal{F}_3^w$ two 3-cells such that there exists a 4-cell:

$$C_{f_1, f_3, f_2} : \bar{f}_1 \star_1 \eta_{f_3} \star_1 f_2 \star_2 (C_{f_1, f_3} \star_1 C_{f_3, f_2}) \star_2 A \underset{\sim}{\Rightarrow} C_{f_1, f_2} \star_2 B.$$

Then $w_\eta(A), w_\eta(B) < u$.
Proof. Using Lemma 6.2.9, we have $\mathbf{p}(\mathbf{t}(C_{f_1, f_2})), \mathbf{p}(\mathbf{t}(C_{f_2, f_3})), \mathbf{p}(\mathbf{t}(C_{f_1, f_3})) < u$. So $\mathbf{p}(\mathbf{s}(A)) = \mathbf{p}(\mathbf{t}(C_{f_1, f_2})+\mathbf{p}(\mathbf{t}(C_{f_2, f_3})) < u$ and $\mathbf{p}(\mathbf{s}(B)) = \mathbf{p}(\mathbf{t}(C_{f_1, f_3})) < u$, and using 6.2.14, we get $\mathbf{w}_\eta(A), \mathbf{w}_\eta(B) < u$.

## 6.3 Partial coherence of $\mathcal{F}^{\mathbf{w}^{(3)}}$

**Proposition 6.3.1.** For every 2-cell $h \in \mathcal{F}_2^\mathbf{w}$ with source and target $\tilde{u}$ a normal form for $A_2$, and for every 3-cells $A, B: h \Rightarrow 1_\tilde{u} \in \mathcal{F}_3^\mathbf{w}$, there exists a 4-cell $\alpha: A \stackrel{\alpha}{\rightleftharpoons} B \in \mathcal{F}_4^{\mathbf{w}^{(3)}}$.

*Proof.* We reason by induction on the couple $(\mathbf{w}_\eta(A) + \mathbf{w}_\eta(B), \mathbf{p}(h))$, using the lexicographic order. If $h = 1_{\tilde{u}}$, then $A = B = 1_h$. Thus setting $\alpha = 1_A = 1_B$ shows that the property is verified.

Suppose now that $h$ is not an identity. Using Lemma 6.2.11, there exists a cavity-factorisation $h = h_1 \star_1 \tilde{f}_1 \star_1 f_2 \star_1 h_2$. By Lemma 6.2.13, there exist $A_1, A_2, B_1, B_2 \in \mathcal{F}_3^\mathbf{w}$, such that $A = (h_1 \star_1 A_1 \star_1 h_2) \star_2 A_2$ and $B = (h_1 \star_1 B_1 \star_1 h_2) \star_2 B_2$. Using this Lemma, we distinguish four cases depending on the shape of $A_1$ and $A_2$.

If $A_1 = B_1 = C_{f_1, f_2}$. Then in particular we have:

$$ \mathbf{s}(A_2) = \mathbf{s}(B_2) \quad \mathbf{w}_\eta(A) = \mathbf{w}_\eta(A_2) \quad \mathbf{w}_\eta(B) = \mathbf{w}_\eta(B_2) \quad \mathbf{t}(A_1) < \mathbf{s}(A_1), $$

where the last inequality is a consequence of Lemma 6.2.9. Hence we get $\mathbf{p}(\mathbf{s}(A_2)) = \mathbf{p}(h_1) + \mathbf{p}(\mathbf{t}(A_1)) + \mathbf{p}(h_2) < \mathbf{p}(h_1) + \mathbf{p}(\mathbf{s}(A_1)) + \mathbf{p}(h_2) = \mathbf{p}(h)$, and finally $(\mathbf{w}_\eta(A_2) + \mathbf{w}_\eta(B_2), \mathbf{p}(\mathbf{s}(A_2))) < (\mathbf{w}_\eta(A) + \mathbf{w}_\eta(B), h)$. Using the induction hypothesis there exists $\alpha: A_2 \stackrel{\alpha}{\rightleftharpoons} B_2 \in \mathcal{F}_4^{\mathbf{w}^{(3)}}$, and by composition we construct $A_1 \star_2 \alpha: A \to B$.

If $A_1 = \tilde{f}_1 \star_1 \eta_{f_3} \star_1 f_2$ and $B_1 = C_{f_1, f_2}$. We are going to construct the following composite:

<figure><img src="image_107.png" /></figure>

According to Lemma 6.1.3, there exists a 4-cell

$$ C_{f_1, f_3, f_2} : \tilde{f}_1 \star_1 \eta_{f_3} \star_1 f_2 \star_2 (C_{f_1, f_3} \star_1 C_{f_3, f_2}) \star_2 D'_1 \stackrel{\alpha}{\rightleftharpoons} C_{f_1, f_2} \star_2 D'_2, $$

with $D'_1, D'_2 \in \mathcal{F}_4^{\mathbf{w}^{(3)}}$. Let us define $D_1 := h_1 \star_1 (C_{f_1, f_3} \star_1 C_{f_3, f_2}) \star_2 D'_1 \star_1 h_2$, $D_2 := h_1 \star_1 D'_2 \star_1 h_2$, and $\alpha_1 := h_1 \star_1 C_{f_1, f_3, f_2} \star_1 h_2$. The existence of $D_3$ is guaranteed by Lemma 6.2.12, which also proves that we can choose $D_3$ such that $\mathbf{w}_\eta(D_3) = 0$.

In order to construct the 4-cells $\alpha_1$ and $\alpha_2$, let us show that we can apply the induction hypothesis to the couples $(A_2, D_1 \star_2 D_3)$ and $(D_2 \star_2 D_3, B_2)$. Let $v$ be the common source of $f_1$ and $f_2$.

* Using Lemma 6.2.15, $\mathbf{w}_\eta(D_1 \star_2 D_3) = \mathbf{w}_\eta(D_1) = \mathbf{w}_\eta(D'_1) < v$, and so:

$$ \mathbf{w}_\eta(A_2) + \mathbf{w}_\eta(D_1 \star_2 D_3) < \mathbf{w}_\eta(A_2) + \mathbf{w}(\eta_3) = \mathbf{w}_\eta(A) \le \mathbf{w}_\eta(A) + \mathbf{w}_\eta(B). $$
• As previously $\mathbf{w}_{\eta}(D_2 \star_2 D_3) = \mathbf{w}_{\eta}(D_2) = \mathbf{w}_{\eta}(D_2') < v$, and so:

$$ \mathbf{w}_{\eta}(B_2) + \mathbf{w}_{\eta}(D_2 \star_2 D_3) < \mathbf{w}_{\eta}(B_2) + \mathbf{w}(\eta_3) \leq \mathbf{w}_{\eta}(B) + \mathbf{w}_{\eta}(A). $$

If $A_1 = C_{f_1, f_2}$ and $B_1 = \bar{f}_1 \star_1 \eta_{f_3} \star_1 f_2$. This case is similar to the previous one, only using $C_{f_1, f_3, f_2}^{-1}$ rather than $C_{f_1, f_3, f_2}$.

If $A_1 = \bar{f}_1 \star_1 \eta_{f_3} \star_1 f_2$ and $B_1 = \bar{f}_1 \star_1 \eta_{f_4} \star_1 f_2$. We are going to construct the following composite:

<figure><img src="image_108.png" /></figure>

Let us set

$$ D_1 := h_1 \star_1 \bar{f}_1 \star_1 f_3 \star_1 \bar{f}_3 \star_1 \eta_{f_4} \star_1 f_2 \star_1 h_2 $$

$$ D_2 := h_1 \star_1 \bar{f}_1 \star_1 \eta_{f_3} \star_1 f_4 \star_1 \bar{f}_4 \star_1 f_2 \star_1 h_2. $$

We then have

$$ (h_1 \star_1 A_1 \star_1 h_2) \star_2 D_1 = h_1 \star_1 \bar{f}_1 \star_1 \eta_{f_3} \star_1 \eta_{f_4} \star_1 f_2 \star_1 h_2 = (h_1 \star_1 B_1 \star_1 h_2) \star_1 D_2. $$

Hence we define $\alpha_1$ as an identity. Let now $D_3$ be as in Lemma 6.2.12, with $\mathbf{w}_{\eta}(D_3) = 0$, and $v$ be the common source of $f_1, f_2, f_3$ and $f_4$. We then have the inequalities:

$$ \mathbf{w}_{\eta}(A_2) + \mathbf{w}_{\eta}(D_1) + \mathbf{w}_{\eta}(D_3) = \mathbf{w}_{\eta}(A_2) + v < \mathbf{w}_{\eta}(A_2) + \mathbf{w}_{\eta}(B_2) + 2v = \mathbf{w}_{\eta}(A) + \mathbf{w}_{\eta}(B), $$

$$ \mathbf{w}_{\eta}(B_2) + \mathbf{w}_{\eta}(D_2) + \mathbf{w}_{\eta}(D_3) = \mathbf{w}_{\eta}(B_2) + v < \mathbf{w}_{\eta}(B_2) + \mathbf{w}_{\eta}(A_2) + 2v = \mathbf{w}_{\eta}(A) + \mathbf{w}_{\eta}(B). $$

Hence we can apply the induction hypothesis to the couples $(A_2, D_1 \star_2 D_3)$ and $(D_2 \star_2 D_3, B_2)$, which provides $\alpha_2$ and $\alpha_3$. $\square$

**Proposition 6.3.2.** The (4, 3)-white-category $\mathcal{F}^{w(3)}$ is $S_{\mathcal{E}}$-coherent.

*Proof.* Let $A, B : f \Rightarrow h \in \mathcal{F}_3^w$ whose 1-target is a normal form $\hat{u}$, with $f, g \in \mathcal{B}_2^w$.

The 3-cells $(\bar{h} \star_1 A) \star_2 \epsilon_h$ and $(\bar{h} \star_1 B) \star_2 \epsilon_h$ are parallel, and their target is $1_{\hat{u}}$. In particular they verify the hypothesis of Proposition 6.3.1. So there exists $\alpha : (\bar{h} \star_1 A) \star_2 \epsilon_h \Rightarrow (\bar{h} \star_1 B) \star_2 \epsilon_h$. Then the following composite is the required cell from $A$ to $B$:
<figure><img src="image_109.png" /></figure>

□

We can now complete the proof of Theorem 1.4.9. Indeed we showed that $\mathcal{F}^{w^{(3)}}$ is $S_{\mathcal{E}}$-coherent. Using Proposition 2.2.14, that means that $\mathcal{E}^{w^{(3)}}$ is $S_{\mathcal{E}}$-coherent, and finally using Lemma 2.2.8 that $\mathcal{A}^{*(2)}$ is $S_{\mathcal{A}}$-coherent, that is that for every 3-cells $A, B \in \mathcal{A}_3^{*(2)}$, whose 1-target is a normal form, there exists a 4-cell $\alpha : A \stackrel{\tau_h}{\rightleftharpoons} B \in \mathcal{A}_4^{*(2)}$.
## References

[1] Franz Baader and Tobias Nipkow. *Term rewriting and all that*. Cambridge university press, 1999.

[2] Jean Bénabou. Introduction to bicategories. In *Reports of the Midwest Category Seminar*, pages 1–77. Springer, 1967.

[3] Albert Burroni. Higher-dimensional word problems with applications to equational logic. *Theoretical computer science*, 115(1):43–62, 1993.

[4] Patrick Dehornoy. The subword reversing method. *International Journal of Algebra and Computation*, 21(1-2):71–118, 2011.

[5] Stéphane Gaussent, Yves Guiraud, and Philippe Malbos. Coherent presentations of artin monoids. *Compositio Mathematica*, 151(05):957–998, 2015.

[6] Yves Guiraud and Philippe Malbos. Higher-dimensional categories with finite derivation type. *Theory and Applications of Categories*, 22(18):420–478, 2009.

[7] Yves Guiraud and Philippe Malbos. Coherence in monoidal track categories. *Mathematical Structures in Computer Science*, 22(06):931–969, 2012.

[8] Yves Guiraud and Philippe Malbos. Higher-dimensional normalisation strategies for acyclicity. *Advances in Mathematics*, 231(3):2294–2351, 2012.

[9] Gregory Maxwell. Kelly. Coherence theorems for lax algebras and for distributive laws. In *Category seminar*, pages 281–375. Springer, 1974.

[10] Gregory Maxwell. Kelly and Saunders MacLane. Closed coherence for a natural transformation. In *Coherence in categories*, pages 1–28. Lecture Notes in Math., Vol. 281. Springer, Berlin, 1972.

[11] Roger C Lyndon and Paul E Schupp. *Combinatorial group theory*. Springer, 2015.

[12] Saunders Mac Lane. Natural associativity and commutativity. *Rice University Studies*, 49(4):28–46, 1963.

[13] Saunders Mac Lane and Robert Paré. Coherence for bicategories and indexed categories. *Journal of Pure and Applied Algebra*, 37(1):59–80, 1985.

[14] François Métayer. Cofibrant objects among higher-dimensional categories. *Homology, Homotopy and Applications*, 10(1):181–203, 2008.

[15] Anthony Power. A general coherence result. *Journal of Pure and Applied Algebra*, 57(2):165–173, 1989.

[16] Craig C. Squier, Friedrich Otto, and Yuji Kobayashi. A finiteness condition for rewriting systems. *Theoretical Computer Science*, 131(2):271–294, 1994.

[17] Ross Street. Limits indexed by category-valued 2-functors. *Journal of Pure and Applied Algebra*, 8(2):149–181, 1976.

[18] Ross Street. The algebra of oriented simplexes. *Journal of Pure and Applied Algebra*, 49(3):283–335, 1987.

[19] Ross Street. Categorical structures. *Handbook of algebra*, 1:529–577, 1996.