1. Introduction
In recent years, there has been considerable study of diagrammatic reasoning in higher categories with substantial new work on higher-dimensional rewriting (Bonchi et al. (Reference Bonchi, Gadducci, Kissinger, Sobocinski and Zanasi2022); Ara et al. (Reference Ara, Burroni, Guiraud, Malbos, Métayer and Mimram2025); Mimram (Reference Mimram2014); Guiraud (Reference Guiraud2019)), new studies of higher categorical diagrams (Forest (Reference Forest2022); Hadzihasanovic (Reference Hadzihasanovic2024); Hadzihasanovic and Kessler (Reference Hadzihasanovic and Kessler2023, Reference Hadzihasanovic and Kessler2024)), and new applications including homotopy type theory (van den Berg and Garner (Reference van den Berg and Garner2007); Angiuli et al. (Reference Angiuli, Harper and Wilson2017); Awodey and Harper (Reference Awodey and Harper2015); Licata and LeFanu Lumsdaine (Reference Licata and Peter LeFanu2021); Chanavat and Hadzihasanovic (Reference C. Chanavat and Hadzihasanovic2024)). Previously, there had been thorough development of the theory of two-dimensional categories, which primarily means 2-categories and bicategories, over the last 60 years reaching back to Kelly-Street (Kelly and Street (Reference Kelly and Street1974)) and Benabou (Benabou (Reference Benabou1967)). However, several subtleties first arise at dimension three and have not yet been studied in depth even there, let alone at arbitrary dimensions. Specifically, the notion of composition, which is of fundamental, foundational importance, is not yet fully understood at dimension three. We explain the situation in this paper.
The central notion of composition in a 2-category, or in a bicategory, every bicategory being biequivalent to a 2-category (Gordon et al. (Reference Gordon, Power and Street1995)), that one uses in practice is that of pasting (Johnson (Reference Johnson1989); Power (Reference Power1990)). There have been by now many formulations of the idea, some combinatorial and some geometric, but all of those of which we are aware are equivalent to each other, and the notion seems stable. A typical pasting diagram is:
Pasting for the above picture is understood as follows: We note first that
$\alpha$
and
$\beta$
, viewed as 2-cells inside triangles as shown, share a common face, and that that face is in the codomain of
$\alpha$
and the domain of
$\beta$
. We say that
$\alpha$
and
$\beta$
have been pasted along that face. This situation is typical, but we can also past 2-cells along several (adjacent) faces, or indeed along no faces (in the latter case the pasting takes place along a 0-cell rather than a 1-cell). In a 2-category, there are two fundamental notions of composition, usually referred to as vertical (composing 2-cells when the one-dimensional codomain of one agrees with the one-dimensional domain of the other) and horizontal (when the zero-dimensional codomain of one agrees with the zero-dimensional domain of the other). So, the pasting shown needs to be explained in terms of vertical and horizontal compositions. To vertically compose
$\alpha$
and
$\beta$
the codomain of
$\alpha$
must be equal to the domain of
$\beta$
, and that can be achieved by using horizontal composition to add to the codomain of
$\alpha$
the rest of the domain of
$\beta$
, in this case just the left-most North-East pointing arrow, and to add to the domain of
$\beta$
the rest of the codomain of
$\alpha$
, in this case just the right-most North-East pointing arrow. Thus, the pasting shown represents two horizontal compositions, also called whiskerings, to make
$\alpha$
’s codomain match
$\beta$
’s domain, followed by the vertical composition of the extended
$\alpha$
and the extended
$\beta$
.
More generally, a pasting diagram might consist of multiple pastings such as
in which there are choices about the order of pasting (
$\gamma$
can be pasted onto
$\alpha$
before or after
$\beta$
for example), and there are pasting theorems (Johnson (Reference Johnson1989); Power (Reference Power1990)) that ensure that the order of pasting does not affect the overall result. Pasting will be explained in more detail in the body of this paper.
Moving up to dimension three, not every tricategory is triequivalent to a 3-category, rather just to a Gray-category (Gordon et al. (Reference Gordon, Power and Street1995)), so we cannot routinely extend from pasting in a 3-category to pasting in a tricategory. The possible meaning of a two-dimensional pasting in a Gray-category has been considered in Di Vittorio (Reference Di Vittorio2023) and has also been treated in Hadzihasanovic (Reference Hadzihasanovic2021) and Forest and Mimram (Reference Forest and Mimram2022). More profoundly, it is possible for two three-dimensional cells to be both above and below each other, as for instance in the following sketch of folded arms. Ignore the upper arms which are included for context, and note that the right forearm (e.g.,) is both above and below the left forearm. If each of those forearms were a 3-cell-oriented downwards, then the crossed forearms cannot be included within the definition of a three-dimensional pasting, as they do not yield a meaningful composite of 3-cells.
One of the contributions of this paper will be to present a (relatively) simple example that demonstrates how such an invalid pasting diagram can arise inside a perfectly valid pasting composition, and this has implications for the meaning of associativity in higher dimensions which we will return to in the concluding section.
The paper is written largely to be expository. Through the course of the paper, we recall the central definitions, constructs, and results about two-dimensional pasting; we explain the examples in detail; and we give a definition of three-dimensional pasting, together with a pasting theorem, lightly revised and improved for the three-dimensional case from the third author’s paper Power (Reference Power1991), to the effect that every pasting diagram has a unique composite, while noting that not every “bracketing” of a three-dimensional pasting diagram will necessarily lead to that final composite (deadlock can arise!).
2. Pasting, Informally
We begin with an informal treatment of pasting at each of dimensions one, two, and three. In the latter half of the paper, we will formalize the notions in order to prove the 3-categorical pasting theorem. We describe here pasting schemes, the shapes of diagrams that are used to specify legitimate compositions at each dimension, and pasting diagrams, pasting schemes appropriately labeled with arrows from a category so that a computation of a legitimate composition can take place, and we discuss associativity at each dimension.
2.1 One-dimensional pasting
In a 1-category (also called simply a category), the only legitimate compositions arise from a succession of arrows joined head to tail.
The 1D-pasting schemes are chains of arrows joined head to tail.
The 1D-pasting diagrams in a category are 1D-pasting schemes labeled with arrows from the category such that two successive labels have the codomain of the first equal to the domain of the second.
A computation in a 1-category is the evaluation of the compositions specified in a 1D-pasting diagram for that category. The associativity of composition ensures that the pairwise compositions can be taken in any order, and
-
(i) the rest of the computation can still be completed, and
-
(ii) the same answer will be obtained in any case
These consequences of the associativity condition could also be called “the 1-category pasting theorem.”
2.2 Two-dimensional pasting
In a 2-category, the legitimate specifications of compositions are rather more complicated. First, there are vertical and horizontal compositions, each of which satisfies an associativity condition
$(\gamma \beta ) \alpha = \gamma (\beta \alpha )$
:
for horizontal composition
and for vertical composition
Furthermore, the two compositions interact satisfying what has been called the middle four interchange
which says that horizontally composing
$\beta \alpha$
with
$\delta \gamma$
gives the same result as vertically composing the horizontal composite of
$\alpha$
and
$\gamma$
with the horizontal composite of
$\beta$
and
$\delta$
. That is,
\begin{align*} \delta \gamma \circ \beta \alpha = (\delta \circ \beta )(\gamma \circ \alpha ) \end{align*}
(writing
$\circ$
for horizontal composition and juxtaposition for vertical composition).
But furthermore, and very importantly in practice, legitimate compositions can be expressed using 2D pasting, as briefly described above, as introduced in Johnson (Reference Johnson1989) and Power (Reference Power1990), and as formally defined below. Informally, such 2D-pasting schemes are decompositions of the oriented plane into finitely many polygonal regions, satisfying conditions that ensure that the technique described in Section 1 above (using horizontal composites to extend suitably chosen 2-cells so that the domains and codomains of the extended 2-cells agree and hence permit vertical composition) will be valid.
The 2D-pasting diagrams in a 2-category are 2D-pasting schemes labeled with arrows and 2-cells from the 2-category such that the domains and codomains of the 2-cells agree with the computation of the 1D-pasting diagrams shown at their domain and codomain in the 2D-pasting diagram.
A computation in a 2-category is the evaluation of the compositions specified in a 2D-pasting diagram for that category. The associativity of compositions along with the middle four interchange ensure that the pasting compositions can be taken in any order, and
-
(i) (2D) the rest of the computation can still be completed, and
-
(ii) (2D) the same answer will be obtained in any case
This is a consequence of the 2D-pasting theorem (Johnson (Reference Johnson1989) and Power (Reference Power1990)).
Perhaps it is worth clarifying what “in any order” means when we’re talking about 2D pasting. For 1D pasting, we were in the familiar situation of rebracketing a given string of arrows – we can take any two adjacent arrows and compose them, replacing their positions in the string by the resulting composite. For 2D pasting, the specification is now two-dimensional, and there are many possible pasteable pairs, including in some cases cells that are not immediately adjacent. So, what might be called a partial bracketing of a 2D-pasting diagram is the identification of a 2D-sub-pasting diagram (some of the arrows and some of the two cells satisfying the conditions to be a 2D-pasting diagram themselves). Completing the computation of the 2D-sub-pasting diagram and substituting the answer in place of the 2D-sub-pasting diagram yields another 2D-pasting diagram, and its computation can then be completed (analogous to replacing the two arrows in the 1D string by their composite in the 1D-pasting case).
Arguably what we are describing here is two-dimensional associativity. The associativity conditions are those for vertical and horizontal composition along with the middle four interchange, while associativity itself, the fact that a 2D-pasting diagram can be rebracketed and computed in any order, follows from the 2D-pasting theorem.
2.3 Three-dimensional pasting
In a 3-category, there are three different fundamental compositions: the composition of two 3-cells with a common 2-cell as one’s codomain and the other’s domain, often called “vertical” composition; the composition of 2-cells either through a common 1-cell as one’s codomain and the other’s domain, sometimes called “horizontal” composition (despite being called vertical composition when the 2-cells in question are viewed as part of a 2-category) or via 2D pasting as described already; and the composition of 1-cells through a common 0-cell as one’s codomain and the other’s domain. Together, and very importantly in practice, these compositions permit the specification of legitimate 3-categorical compositions via 3D pasting (Johnson (Reference Johnson1989); Power (Reference Power1991)).
Informally, 3D-pasting schemes are decompositions of oriented 3-space into finitely many effectively polyhedral regions, satisfying conditions that ensure that a technique similar to that described in Section 1 (though using horizontal pasting to extend chosen adjacent 3-cells so that the domains and codomains of the extended 3-cells agree and permit vertical composition) will be valid.
The 3D-pasting diagrams in a 3-category are 3D-pasting schemes labeled with 3-cells, 2-cells, and 1-cells from the 3-category consistent with the domains and codomains indicated by the diagram.
A computation in a 3-category is the evaluation of the compositions specified in a 3D-pasting diagram for that category. Once again, compositions can be taken in any order, but
-
(i) (3D) the rest of the computation may not be able to be completed – deadlock can arise! Nevertheless
-
(ii) (3D) the same answer will be obtained in any case in which the computation can be completed
The second statement, (ii) (3D), is the 3-category pasting theorem. The explanation and clarification of the first statement (i) (3D) is one of the main purposes of this paper, and it is demonstrated by the study of the following example.
3. Three-Dimensional Example with Possible Deadlock
This is a new example related to Example 3.11 of Power (Reference Power1991) and the crossed arms of Section 1. Other examples related to Example 3.11 of Power (Reference Power1991) have been presented in Example 3.23 of Hadzihasanovic (Reference Hadzihasanovic2021) and importantly in string diagram rewriting terms in Example 45 of Bonchi et al. (Reference Bonchi, Gadducci, Kissinger, Sobocinski and Zanasi2022a). The growing importance of these kinds of “obstructions” has motivated the following detailed and simplified presentation.
Because it is quite hard to visualize three-dimensional pasting diagrams, we will introduce separately the four 3-cells, then explain how they are connected to form a 3D-pasting scheme, and finally talk about the composition of different sub-pasting schemes and how some will result in deadlock.
Our main purpose in this section is to give concrete examples of (i) (3D) above. Note first that (i) (3D) was expressed in terms of the computation of compositions in a 3-category – after all, that is where the failure is most dangerous. But the failure doesn’t arise from some pathology about a particular 3-category. Rather it is a consequence of the basic geometry of oriented 3-space, so we can illustrate it at the level of schemes. (Any legitimate labeling of the schemes we show here will suffer the same failure.)
3.1 A pillow
We begin with a “pillow” as illustrated below. The quadrilateral
$ADEB$
gives the edges of the pillow (with
$AD$
bisected into two arrows for reasons we will soon see). The pillow puffs “up” as indicated by the curved arrow
$CB$
and down as indicated by the curved dotted arrow on its underside
$CE$
.
Whenever possible, we avoid showing too many higher-dimensional cells in this and the following pictures to avoid cluttering up the visualization. It may be helpful to know that in almost all cases, our 1-cells are oriented downwards (from the top of the page and towards the bottom of the page), our 2-cells are oriented leftwards (from the right-hand side of the page and towards the left-hand side of the page), and our 3-cells are oriented into the page from a surface imagined to be on or above the page, and to a surface imagined to be below or on the page. Thus, in the picture of the pillow above, noticing that the upper face
$ADEB$
is divided into a triangle
$ACB$
and a remaining trapezoid
$CDEB$
, there are also two 2-cells on the top surface, not shown, one from
$AB$
to
$ACB$
(leftwards as promised) and the other from
$CBE$
to
$CDE$
(again leftwards, as promised). Similarly, on the bottom face of the pillow, there is a 2-cell from
$ABE$
to
$ACE$
and another from
$CE$
to
$CDE$
. The pillow has a single 3-cell from the top face, the 2-cell in
$ACB$
pasted onto the 2-cell in
$CDEB$
, to the bottom face (the other two 2-cells pasted together).
The two triangular 2-cells, one on the top and one on the bottom of the pillow, will be used soon to paste on other shapes that have a matching triangular face.
Imagine halving a solid cone with a cut from its vertex to a diameter of its base. This would give two semi-cones, each of which has a triangular face (the cut surface), along with a semicircular face (half of the base) and a curved face (half of the curved face of the original cone).
3.2 Top semi-cone
Picture now one of those semi-cones as shown below. We intend, soon, to paste it on the top of the pillow, so we call it the top semi-cone and its triangular face is labeled
$ACB$
. Once the pillow and the semi-cone are pasted together, the vertices
$A$
,
$C$
, and
$B$
will be identified, the edges between them (in the case of the semi-cone shown using the dotted arrow from
$A$
to
$C$
) will be identified, and the 2-cells, undrawn in the pillow, and drawn dotted in the semi-cone, will be identified. The two pictures will be pasted along the triangle
$ACB$
.
The 2-cell in that triangle is shown as dotted because it is on the underside of the semi-cone, in the plane of the page. The other 2-cell shown in the picture is also dotted because it too is obscured by the curved face of the semi-cone which rises out of the page and has a 2-cell, not shown, from
$AB$
to the solid arrow
$AC$
followed by the arrow
$CB$
.
It will help in future pastings if one imagines the semicircular base of the semi-cone as not rising out of the page perpendicularly, but rather doing so at a 45-degree angle to the page leaning towards the top of the page as shown.
3.3 Bottom semi-cone
A second semi-cone, shown below, will ultimately be pasted on the bottom of the pillow, pasted along the triangle
$CDE$
. It is similar to the semi-cone just discussed, but we will still talk about it in some detail to aid the reader’s visualization.
This time, the 2-cells shown are solid because they are visible on the surface we are looking at, with the triangle
$CDE$
in the plane of the page and the curved surface of the semi-cone, along with its undrawn 2-cell, curving under the page and obscured this time by the triangle and the semicircle. The 3-cell in this semi-cone, also not drawn, goes from the two 2-cells shown to the curved face underneath (again, 3-cells are oriented into the page in these pictures).
The arrow
$CE$
has been drawn curved in this picture – this is an inessential feature but is intended to help the reader to associate that arrow with the slightly curved arrow
$CE$
on the underside of the pillow.
Once again, it will be helpful to imagine the semicircle
$CD$
not as going out of the bottom of the page perpendicularly to the page, but rather as oriented at about 45 degrees to the surface of the page, under the page, and tilted from perpendicular so that its bottom (curved arrow) is closer to the top of the page as shown.
3.4 The connector
Finally, we have a piece that is intended to connect the bases of the two semi-cones, so we call it the connector. This piece is not a particularly familiar shape, so it might take a few minutes to visualize.
Notice that the semicircle
$AC$
is drawn with solid lines. It is part of the top of this piece and could best be imagined as coming out of the page at 45 degrees. That would make it possible for the base of the top semi-cone to meet it exactly, and indeed, they will be pasted together.
The rest of the top of this connector piece is the “triangle”
$ACD$
(but two of its edges are curved arrows) shown by the solid (undotted) arrows and using the curved arrow from
$A$
to
$C$
. It is filled by a 2-cell oriented from
$ACD$
to
$AD$
. The straight arrows
$AC$
and
$CD$
and the curved arrow
$AD$
are all in the plane of the page, but the rest of the two surfaces just described, including the curved arrow
$AC$
, are above the page.
Similarly, there is a semicircle
$CD$
and a “triangle” with curved faces
$CD$
(dotted) and
$AD$
and straight face
$AC$
under the page and with an undrawn 2-cell in the “triangle.” If the semicircle is imagined as going out of the bottom of the page at a 45 degree angle, then it is easy to imagine it meeting up with the semicircle
$CD$
of the bottom semi-cone, and indeed the two shapes will be pasted together along that semicircle.
Finally, there is a 3-cell from the top two faces to the bottom two faces.
It should be noted that we have deviated from our standard directions somewhat in this picture. Originally, the picture was oriented 30 degrees counterclockwise to its current image, giving downward pointing arrows and leftwards pointing 2-cells, but some readers found it harder to interpret the shape when it was presented at that orientation.
3.5 Putting it all together: A 3D-pasting scheme
Now imagine those four pieces pasted together along the common faces. Here are the four pieces:
The pillow is in the middle; the two semi-cones on either side of it; and the connector above and slightly to the left.
Pasting them together: The two semi-cones are pasted onto the pillow at the common triangles
$ACB$
and
$CDE$
; the connector is pasted to the two semi-cones along the semicircles
$AC$
and
$CD$
; the pillow and the connector meet only along the two straight arrows
$AC$
and
$CD$
. Here, they are almost joined up (separating them a little makes it easier to see how they fit together).
The whole agglomeration is consistently oriented in three space with the 3-cells all pointing into the page; the 2-cells across the top, bottom, and the intermediate faces (the two triangles used to paste on the semi-cones and the two semicircles used to paste on the connector) all pointing from right to left (even in the connector which is now oriented 30 degrees counterclockwise of its drawn version to fit onto the two semi-cones and share arrows
$AC$
and
$AD$
with the pillow); and the 1-cells all oriented consistently from top to bottom of the page. This is important because a specification of three-dimensional composition, a 3D-pasting scheme, is more than just apparently composable 3-cells and needs to be consistently oriented at all dimensions.
The agglomeration is a 3D-pasting scheme.
4. Computations in the Three-Dimensional Example
We now turn to imagine computations we might carry out with that pasting scheme. As noted before, we don’t need to specify a particular 3-category to do the computations in because the surprising result, (i)(3D), arises from the geometry of oriented 3-space. Instead, we just look at sub-pasting schemes, imagine computing their composites and replacing the subpasting scheme with the result, and explore whether the computation can continue. We are exploring the “in any order” part of higher-dimensional associativity.
4.1 A global computation
To start with an easy case, we can take the top semi-cone (2) and paste it onto the pillow (1) (in other words, we are considering first the subpasting scheme consisting of just those two pieces). Then we might consider pasting the connector (4) onto the result (a further choice of bracketing). All of this is easy, and can be carried out, analogously to the process described in Section 1, by pasting on two-dimensional parts of domains and codomains to make them match and then using vertical composition of 3-cells. The resulting piece is a single 3-cell with domain the top surface of the whole agglomeration (the curved face of the top semi-cone, pasted as a 2-cell onto the trapezoidal top face of the pillow, pasted across the common arrows
$AC$
and
$AD$
with the top “triangular” face of the connector – we are just describing the top surface that the reader can see in the picture above (ignoring the small gap where one can see the bottom semi-cone peeking through)). The codomain of the single 3-cell made out of those three pieces is the codomain of the connector’s 3-cell (a semicircle and a “triangle”) pasted along the common arrows
$AC$
and
$CD$
with the codomain of the pillow (a trapezoid and a triangle). It is now easy to complete the computation by composing with the bottom semi-cone which agrees with semicircle and triangle just mentioned, so it can be extended by pasting on the trapezoid and the connector’s “triangle” and then composed vertically. Again that is shown in the picture above, again noting that in the actual composition there would be no small gaps to see through – all the edges would line up perfectly and the bottom semi-cone would be completely unseen when viewed from this angle.
There are many more easy cases. But we aim to illustrate some obstructions to computations.
4.2 A non-associative case
To demonstrate a basic non-associativity and describe it in algebraic terms, let’s denote the upper semi-cone by
$S$
, the connector by
$C$
, and the pillow by
$P$
, and we write
$*$
for in-fix pasting – normally we might subscript it with the details of which surface(s) the pasting takes place along, but that is not necessary here because the pasting surfaces have already been established for this example. We consider
\begin{align*} S * (C * P) \end{align*}
The internal bracket,
$C*P$
, is one of the easiest computations to contemplate and is sometimes described as doing
$C$
and
$P$
in parallel. Their only commonalities are the oriented edges
$AC$
and
$CD$
and to paste them along those edges one simply whiskers one of them, say
$P$
with the domain of the other
$dom\,C$
, and whiskers the other,
$C$
, with the codomain of the first
$cod\,P$
, and then they can be vertically composed. The result is a single 3-cell whose domain is the 2D-pasting of the domains of
$C$
and
$P$
along the arrows
$AC$
and
$CD$
.
If instead one began by whiskering
$C$
with
$dom\,P$
and then continued, the result would be the same by three-dimensional middle four interchange (Section 2).
And now pasting
$S$
onto
$C*P$
is easy – the codomain of
$S$
is a part of the domain of
$C*P$
, so the only whiskering required is to paste the rest of the domain of
$C*P$
, the quadrilateral
$CDEB$
, and the “triangle”
$ACD$
, onto the side of
$S$
. At that point, the codomain of the whiskered
$S$
matches the domain of
$C*P$
, and they can be composed vertically. The result is visible in the last photograph above if one ignores the bottom semi-cone peeking through (the bottom semi-cone is not involved in this subsection at all).
Now suppose instead we contemplate
\begin{align*} (S * C) * P \end{align*}
The internal bracket in this case is
$S*C$
, and that presents us with a problem. Both the domain and codomain of
$S$
include the arrow
$CB$
oriented from
$C$
to
$B$
. Both the domain and codomain of
$C$
include the arrow
$CD$
oriented from
$C$
to
$D$
. These two arrows, both issuing forth from
$C$
, cannot co-exist in a pasting diagram along with
$A$
. In short,
\begin{align*} S * (C * P) \neq (S * C) * P \end{align*}
because the right-hand side is undefined.
Note that this doesn’t contradict the general associativity derived from the pasting theorem – (ii)(3D) tells us that the results will be the same provided that both can be completed.
4.3 A deadlock case
The deadlock case we wish to illustrate begins with some easy compositions: As before, consider the subpasting scheme made up of the top semi-cone and the pillow and compute their composition – replace the two of them with a single 3-cell. The bottom semi-cone can be pasted onto this 3-cell because the 3-cell has as part of its codomain the triangle on the bottom of the pillow. To actually do that composition, one needs to extend the 3-cell by the 2D pasting of the semicircle of the bottom semi-cone and extend the bottom semi-cone by the 2D pasting of the bottom trapezoid of the pillow, and then the domain and codomain match and vertical composition completes the job. The result can be seen in the picture above as the right-hand three pieces – just take the connector (top left piece) away from the picture mentally.
But here’s the crisis: The resulting pasting scheme has one 3-cell resulting from the composition of the three pieces just discussed (the two semi-cones and the pillow) and another 3-cell in the connector. How can we complete the computation of the original agglomeration now that we have reached this state? There are two cases of possible vertical composition to consider.
The domain of the connector has a semicircle which can be pasted onto the base of the top semi-cone, and a “triangle” (with curved sides) which does not appear anywhere in the other 3-cell. So if we are to ultimately vertically compose the other 3-cell followed by the the connector, then that “triangle” needs to be pasted onto the other 3-cell and we can’t do that because the two-dimensional domain of the result would include both the “triangle” 2-cell oriented out of arrow
$CD$
and the semicircle oriented out of arrow
$CD$
– that can never happen in a well-formed 2D-pasting scheme. In the picture above, the two contradictory 2-cells that we are talking about can be seen as the visible top of the connector and the semicircular base of the bottom semi-cone that is just peeking through the gap. Trying to post-compose the connector onto the other 3-cell cannot work. There is no way to prepare the two pieces for a valid vertical composition.
Alternatively, if we aim to vertically pre-compose the connector with the other 3-cell, then the codomain of the connector includes a “triangle” which would need to be pasted onto the other 3-cell, before vertical composition would be possible. But again that leads to a contradiction, this time with two different 2-cells issuing forth from the arrow
$AC$
.
The two pieces – (a) the connector and (b) the composite of the pillow and the two semi-cones – cannot be vertically composed in either order (neither composite piece followed by connector nor connector followed by composite piece). Perhaps the reader can see the relationship here to the crossed arms pictured in Section 1 – the composite piece is both above and below the connector. No further vertical compositions are possible, and we are in deadlock.
We will return to consider the implications of this in the concluding section, but first we review this example in rewriting terms in the next section, and then in the following sections we turn to establishing (ii) (3D), the 3-category pasting theorem.
5. The Example via Rewriting
The main goal of this paper has been to induce an understanding of the three-dimensional geometry that can lead to deadlock. Hence, the detailed example, with pictures, presented above. Nevertheless, some readers prefer to analyze higher-dimensional pasting in algebraic or in rewriting terms, so in this brief section we will rework the main points from the example describing the 3-cells as rewrites of two-dimensional pasting diagrams. We begin with some notation.
We have already used the letter
$S$
,
$C$
, and
$P$
for the upper semi-cone, the connector, and the pillow, respectively. In this section, we will use those letters to stand for the three cell rewrites in the middle of those shapes, and we will use
$L$
to stand for the 3-cell rewrite in the middle of the lower semi-cone.
We need to label the 2-cells on the boundaries of
$S$
,
$C$
,
$P$
, and
$L$
. To do that with a minimum of fuss, we subscript each of those letters with
$t$
for top (domain) and
$b$
for bottom (codomain) and numbers 1 or 2 to distinguish multiple 2-cells in the domains or codomains. Writing pasting, two-dimensional pasting this time, as infix
$*$
, we can then treat the four 3-cells as rewrites of two-dimensional pasting schemes as follows:
\begin{align*} S_{t,1} \longrightarrow ^S \quad S_{b,1} * S_{b,2} \\[-28pt] \nonumber \end{align*}
\begin{align*} C_{t,1} * C_{t,2} \longrightarrow ^C \quad C_{b,1} * C_{b,2} \\[-28pt] \nonumber \end{align*}
\begin{align*} P_{t,1} * P_{t,2} \longrightarrow ^P \quad P_{b,1} * P_{b,2} \quad \mbox{and} \\[-28pt] \nonumber \end{align*}
\begin{align*} L_{t,1} * L_{t,2} \longrightarrow ^L \quad L_{b,1} \\[-12pt] \nonumber \end{align*}
We note also that
$S_{b,1} = P_{t,1}$
(triangle
$ACB$
),
$S_{b,2} = C_{t,1}$
(semicircle with diameter
$AC$
),
$C_{b,1} = L_{t,2}$
(semicircle with diameter
$CD$
), and
$P_{b,2} = L_{t,1}$
(triangle
$CDE$
).
With that notation, the entire pasting scheme of Section 3 can be seen as rewrites applied to the two-dimensional pasting scheme
$S_{t,1} * P_{t,2} * C_{t,2}$
. We now review the compositions discussed in Section 4.
What was called A global computation in Section 4 is, when viewed as a rewrite of
$S_{t,1} * P_{t,2} * C_{t,2}$
, the sequence of rewrites
\begin{align*} S_{t,1} * P_{t,2} * C_{t,2} \longrightarrow ^S \quad S_{b,1} * S_{b,2} * P_{t,2} * C_{t,2} = P_{t,1} * C_{t,1} * P_{t,2} * C_{t,2} \longrightarrow ^P \quad \\[-28pt] \nonumber \end{align*}
\begin{align*} P_{b,1} * C_{t,1} * P_{b,2} * C_{t,2} \longrightarrow ^C \quad P_{b,1} * C_{b,1} * P_{b,2} * C_{b,2} = \\[-28pt] \nonumber \end{align*}
\begin{align*} P_{b,1} * L_{t,2} * L_{t,1} * C_{b,2} \longrightarrow ^L \quad P_{b,1} * L_{b,1} * C_{b,2} \end{align*}
Next, we turn to what was called a non-associative case in Section 4. The interesting part of that is
$S * C$
, and an attempt to write it as a rewrite of 2-cells might begin
\begin{align*} S_{t,1} * C_{t,2} \longrightarrow ^S \quad \end{align*}
In fact, we could continue and write it as a reasonable looking sequence of rewrites, but we need to stop here. On careful inspection,
$S_{t,1} * C_{t,2}$
is not a legitimate two-dimensional pasting scheme. That stops, as noted above,
$S$
and
$C$
from being pasted together in isolation. The contradictory arrangement of 1-cells is the problem and is contrary to what we noted at the end of Section 3: “a 3D-pasting scheme, is more than just apparently composable 3-cells, and needs to be consistently oriented at all dimensions.” Here, the orientations of the 1-cells are not consistent.
It is worth noting that we could instead begin that sequence of rewrites from
$S_{t,1} * P_{t,2} * C_{t,2}$
– the presence of
$P_{t,2}$
“completes” the two-dimensional pasting scheme, allowing the rewrite
$S$
to be applied, followed then by
$C$
(or indeed by
$P$
as above). Usually when we think of 3-cells as rewrites, we start with the entire two-dimensional pasting scheme, that is, the global domain. But this paper is about pasting, and pasting operations are usually built up from basic components or alternatively computed by calculating the pastings of identified subcomponents like
$S$
and
$C$
. This paper focuses on the computation of pastings.
Finally, let’s consider a deadlock case as described in Section 4. In that case, there were two pieces, the connector,
$C$
, and the pasting composite of
$S$
,
$P$
, and
$L$
. The latter, in rewrite terms, is
\begin{align*} S_{t,1} * P_{t,2} * C_{b,1} \longrightarrow ^S \quad S_{b,1} * S_{b,2} * P_{t,2} * C_{b,1} = P_{t,1} * C_{t,1} * P_{t,2} * L_{t,2} \longrightarrow ^P \quad \\[-28pt] \nonumber \end{align*}
\begin{align*} P_{b,1} * C_{t,1} * P_{b,2} * L_{t,2} = P_{b,1} * C_{t,1} * L_{t,1} * L_{t,2} \longrightarrow ^L \quad P_{b,1} * C_{t,1} * L_{b,1} \end{align*}
Of course, we could attempt to add the rewrite
$C$
to the sequence above, or indeed to “insert” the 3-cell
$C$
into the gap in the pasting scheme, but the problem is that we cannot paste
$C$
onto the cell we have just described. As explained in Section 4, doing so would require extending the pasting scheme just described by the rest of the domain of
$C$
, or by the rest of the codomain of
$C$
, and that would result in illegitimate pasting schemes due to the presence of
$C_{t,2}$
and
$C_{b,1}$
in the first case and of
$C_{t,1}$
and
$C_{b,2}$
in the second case. Similarly, the proposed rewrite addition fails because
$C_{t,2}$
needs to be added to the 2-cells being rewritten, but
$C_{t,2}$
and
$C_{b,1}$
cannot coexist in a legitimate two-dimensional pasting scheme.
Now, having reviewed the main example both in pasting and in rewriting terms, we turn to establishing the promised three-dimensional pasting theorem including a more formal treatment of pasting. We provide in the following sections a simplified presentation of the results from Power (Reference Power1991), restricted to the case
$n=3$
.
6. One-Dimensional Pasting: Composition in Ordinary Categories
A 1-computad is a finite directed graph; a 1-computad morphism is a map of directed graphs (i.e., a natural transformation in the presheaf category of directed graphs).
A 1-pasting scheme is a finite non-empty set
$G$
together with an embedding
$g$
of
$G$
into the oriented line. We identify
$G$
with its image, and we call the elements of
$G$
0-cells.
$G$
partitions the rest of the line into a finite number of disconnected open intervals and two rays. We call the open intervals 1-cells, and we define the domain and codomain of a 1-cell
$f$
to be its endpoints, written
$dom f$
and
$cod\, f$
, with
$dom f \lt cod\, f$
in the order determined by the orientation of the line. The domain of the pasting scheme, denoted
$dom\, G$
, is the least element of
$G$
in the order determined by the orientation of the line; dually, the codomain of
$(G,g)$
, denoted
$cod\, G$
, is the greatest element. The 0-cells and 1-cells of
$(G,g)$
together with the domain and codomain functions form a directed graph, which we call the underlying 1-computad of
$(G,g)$
, and which we denote by
$C(G)$
.
A 1-pasting diagram in a 1-computad
$H$
consists of a 1-pasting scheme
$(G,g)$
together with a 1-computad morphism
$h:C(G)\rightarrow H$
. The domain of a 1-pasting diagram
$((G,g),h)$
is
$dom\, G$
together with the restriction of
$h$
to
$C(dom\, G)$
; dually for codomain. A 1-pasting diagram
$((G,g),h)$
is called simply a 1-pasting scheme in
$H$
if
$h$
is a monomorphism in the category of directed graphs.
Every 1-pasting scheme with at least two 0-cells is called spherical. A 1-computad is locally spherical if each 1-cell together with its domain and codomain is a spherical 1-pasting scheme, that is, if every 1-cell has its domain and codomain different 0-cells.
A 1-subpasting scheme of a 1-pasting scheme
$(G,g)$
is a subset
$J$
of
$G$
for which given
$j\lt g\lt j'$
with
$j$
and
$j'$
in
$J$
and
$g$
in
$G$
, it follows that
$g$
lies in
$J$
.
A labeling of a 1-pasting scheme
$(G,g)$
in a category
$A$
is a 1-pasting diagram
$((G,g),a)$
in
$A$
. A 1-pasting composite of a labeled 1-pasting scheme in a category
$A$
is the composite in
$A$
of the sequence of arrows determined by the diagram. A pasting composite may also be called a computation.
7. Two-Dimensional Pasting: Composition in Two-Dimensional Categories
We recall definitions and a few results for
$n=2$
, from Power (Reference Power1990), but with an improvement to the main definition, that of 2-pasting scheme, suggested to us by Alex Simpson.
Definition 7.1.
A 2-computad consists of a directed graph
$G$
, together with a set
$G_2$
and two functions
$dom,cod:G_2\rightarrow path(G)$
, where
$path(G)$
is the set of directed paths in
$G$
, such that
$dom\, dom = dom\, cod$
and
$ cod\, dom = cod\, cod$
. A 2-computad morphism from
$(G_2,G,dom,cod)$
to
$(H_2,H,dom,cod)$
consists of a map of directed graphs
$f:G\rightarrow H$
and a function
$f_2:G_2\rightarrow H_2$
such that
$dom\, f_2 = f\, dom$
and
$cod\, f_2 = f\, cod$
. The category
$2$
-
$Computad$
is the category of 2-computads and 2-computad morphisms, with the evident composition.
Definition 7.2.
A 2-pasting scheme consists of a (non-empty) connected finite directed graph
$G$
together with an embedding
$g$
of
$G$
into the oriented plane subject to the following conditions. The image of
$G$
divides the rest of 2-space into finitely many disconnected regions, called faces.
-
(1) The boundary of each interior face
$F$
is of the form
$\sigma (F)(\tau (F))^{-1}$
for directed paths
$\sigma (F)$
and
$\tau (F)$
in
$G$
of non-zero length, if moving clockwise around the boundary;
-
(2) there are a source
$s(G)$
and a target
$t(G)$
in the exterior face;
-
(3) no vertex other than
$s(G)$
and
$t(G)$
is either a source or a target of
$G$
.
Using the notation of Definition 7.2, the interior faces
$F$
of
$(G,g)$
are called 2-cells, and
$dom F$
and
$cod F$
are defined to be
$\sigma (F)$
and
$\tau (F)$
, respectively.
The first condition of Definition 7.2 is required in order to assign a domain and a codomain sensibly to each 2-cell of a 2-pasting scheme. In order to understand the second and third conditions, we shall consider a few examples of embeddings of connected finite directed graphs into the oriented plane that satisfy the first condition but are not 2-pasting schemes.
Example 7.3. Consider the following diagram:
There is no candidate for
$s(G)$
, which by definition must lie in the exterior face of a 2-pasting scheme, contradicting the second condition. It is unclear what a composite of such a diagram might mean.
The next example shows both how the formal definition might be violated, breaking condition (3), and more informally how two 2-cells pasted along a 1-cell in the codomain of one and the domain of the other might not be pasteable in the manner outlined in Section 1.
Before treating the example formally, we note here why it’s not pasteable.
According to the process outlined in Section 1 and used multiple times in the example in Section 4, the arrows in the domain of the lower 2-cell need to be added to the upper 2-cell, and the arrows in the codomain of the upper 2-cell need to be added to the lower 2-cell. But in neither case can they be added – the resulting graphs are not legitimate 2-pasting schemes. The extra arrow is necessarily in both the domain and the codomain of the purported pasting schemes, and that violates the requirement that the domain and codomain themselves are 1-pasting schemes (chains of arrows joined head to tail). The forking arrows emmanating from the right-hand middle 0-cell are the problem.
Example 7.4. Consider the following diagram:
It is not a 2-pasting scheme as there is more than one target, contradicting the third condition. It does not yield a composable diagram as the two 2-cells are not composable.
Proposition 7.5.
If
$(G,g)$
is a 2-pasting scheme, then
$G$
has no directed cycle.
Proof. This follows by induction on the number of faces enclosed by any potential directed cycle, using the third condition and the fact that, by the first condition, an interior face cannot be a loop.
Proposition 7.6.
If
$(G,g)$
is a 2-pasting scheme, then for any vertex
$v$
in
$G$
, there are paths from
$s(G)$
to
$v$
and from
$v$
to
$t(G)$
.
Proof.
This follows from Proposition 7.5 applied to the finiteness of the number of vertices in
$G$
and the fact that
$s(G)$
and
$t(G)$
are the only source and target of
$G$
.
Proposition 7.7.
If a pasting scheme
$(G,g)$
has at least one interior face, then there exists an interior face
$F$
such that
$dom F$
lies entirely on
$dom G$
.
Proof. This follows from Proposition 7.6 and induction on the number of interior faces.
Proposition 7.7 is the key geometric result required to prove the pasting theorem: it is existence rather the unicity of a composite that was the main challenge to prove.
Remark 7.8.
In Power (Reference Power1990), it was assumed in the definition of 2-pasting scheme that
$s(G)$
and
$t(G)$
are distinct, but that assumption was inessential to the argument. If they are the same, then the 2-pasting scheme must be trivial. More substantially, the third condition was replaced by the conclusion of Proposition 7.6
.
Every pasting scheme
$(G,g)$
has an underlying 2-computad given by the graph
$G$
and the 2-cells of
$(G,g)$
; we denote this 2-computad by
$C(G)$
. It also follows that the exterior face
$E$
also has boundary of the form
$\sigma (E)(\tau (E))^{-1}$
for directed paths
$\sigma (E)$
and
$\tau (E)$
of non-zero length, if moving around the boundary with
$E$
always on one’s right side; these are called
$cod G$
and
$dom G$
, respectively.
Definition 7.9.
A 2-pasting diagram in a 2-computad
$H$
consists of a 2-pasting scheme
$(G,g)$
together with a 2-computad morphism
$h:C(G)\rightarrow H$
. A labeling of a 2-pasting scheme
$(G,g)$
in a 2-category
$A$
is a 2-pasting diagram
$((G,g),a)$
in
$A$
.
Theorem 7.10 (A 2-categorical pasting theorem). Every labeling of a 2-pasting scheme has a unique composite.
Proof. The existence of a composite follows from Proposition 7.7 by induction on the number of interior faces; unicity also follows directly by induction.
Remark 7.11. Pasting composition describes all possible composites of a set of 2-cells. This is evident because a horizontal composite of labeled 2-pasting schemes is a labeled 2-pasting scheme, and a vertical composite of labeled 2-pasting schemes is a labeled 2-pasting scheme.
In order to study the third dimension, we add the following definitions. The domain of a 2-pasting diagram
$((G,g),h)$
in a 2-computad
$H$
is
$dom G$
together with the restriction of
$h$
to
$C(dom G)$
; dually for codomain. A 2-pasting diagram
$((G,g),h)$
is called simply a 2-pasting scheme in
$H$
if
$h$
is a monomorphism in
$2$
-
$Computad$
, that is, if
$h$
is injective on k-cells for k = 0 to 2. A 2-pasting scheme is called spherical if
$dom G\cup cod G$
is homeomorphic to the 1-sphere, that is, to a circle. A 2-computad
$G$
is called locally spherical if each 2-cell in it is a spherical 2-pasting scheme containing just one 2-cell. A 2-pasting inclusion into a 2-pasting scheme
$(G,g)$
is a directed graph inclusion
$j$
into
$G$
such that the composite
$gj$
is a 2-pasting scheme for which every 2-cell is a 2-cell of
$(G,g)$
. A 2-subpasting scheme is an equivalence class of 2-pasting inclusions under the evident equivalence.
8. Three-Dimensional Pasting: Composition in Three-Dimensional Categories
This section is devoted to defining the terms 3-computad and 3-pasting scheme. We refer the reader back to Section 3 for a detailed example of a 3-pasting scheme.
Generalizing the situation for
$n=2$
, a 3-computad will have
$k$
-cells for
$k=0$
to 3, with an orientation assigned to each
$k$
-cell, subject to some axioms. Each 3-cell will have a domain and a codomain, each of which will be a 2-pasting scheme. A 3-pasting scheme will consist of a 2-computad embedded in 3-space. A 3-pasting scheme
$(G,g)$
will be called spherical if its domain and codomain, which will be subcomputads of
$G$
, are spherical 2-pasting schemes and if
$dom G \cup cod G$
is homeomorphic to the 2-sphere. A 3-computad will be called locally spherical if for each 3-cell, the subcomputad generated by taking its domain and codomain is a spherical 3-pasting scheme with only one 3-cell in it. Given a 3-pasting scheme
$(G,g)$
, it will generate a 3-computad by taking the embedding and the region enclosed by it; this 3-computad will be denoted by
$C(G)$
. A 3-pasting diagram in a 3-computad
$H$
will be a 3-pasting scheme
$(G,g)$
together with a 3-computad morphism
$h:C(G)\rightarrow H$
.
Definition 8.1.
A 3-computad consists of a 2-computad
$G_2$
, a set
$G_3$
, and two functions
$dom,cod:G_3\rightarrow diags(G_2)$
, where
$diags(G_2)$
is the set of 2-pasting diagrams (see Definition 7.9) in
$G_2$
, such that
$dom\, dom = dom\, cod$
and
$cod\, dom = cod\, cod$
. A 3-computad morphism from
$(G_3,G_2,dom,cod)$
to
$(H_3,H_2,dom,cod)$
consists of a 2-computad morphism
$f_2:G_2\rightarrow H_2$
and a function
$f_3:G_3\rightarrow H_3$
such that
$dom\, f_3 = f_2\, dom$
and
$cod\, f_3 = f_2\, cod$
. The category
$3$
-
$Computad$
is the category of 3-computads and 3-computad morphisms, with the evident composition.
Proposition 8.2.
Let
$(G,g)$
be a locally spherical 2-computad
$G$
together with an embedding
$g$
of
$G$
into oriented 3-space. Then the orientation of 3-space determines an orientation for each 2-cell of
$G$
, giving it a “left-hand side” and a “right-hand side.”
Proof.
Since
$G$
is locally spherical, every 2-cell in
$G$
is given by an inclusion of a 2-pasting scheme with just one 2-cell into
$G$
, and so composing this inclusion with
$g$
gives a piecewise linear embedding of a 2-ball into oriented 3-space. So the orientation of 2-space specifies an orientation for the embedded 2-cell.
Definition 8.3.
Given a finite locally spherical 2-computad
$G$
together with an embedding
$g$
of
$G$
into 3-space, the image of
$G$
divides the rest of 3-space into finitely many disconnected regions. For each such region
$F$
, we write
$in F$
for the set of 2-cells of
$G$
that are incident to
$F$
and with orientation into
$F$
, as given by Proposition 8.2
. Dually, we write
$out F$
for the set of 2-cells of
$G$
that are incident to
$F$
and with orientation out of
$F$
. We shall call the interior regions 3-cells of
$(G,g)$
. Let the exterior region determined by such an embedding be denoted by
$E$
.
Definition 8.4.
A 3-embedding is a (non-empty) connected, finite, locally spherical 2-computad
$G$
together with an embedding
$g$
of
$G$
into 3-space subject to the following conditions:
-
(i) if
$F$
is an interior region, then
$F$
is homeomorphic to the 3-ball, and
$in F$
and
$out F$
, together with their domains and codomains, each forms a spherical 2-pasting scheme, denoted
$dom F$
and
$cod F$
, respectively, such that
$dom F \cup cod F$
is the boundary of
$F$
;
$dom (dom F) = dom (cod F)$
; and
$cod (dom F) = cod (cod F)$
. -
(ii) there exist 2-pasting schemes
$dom G$
and
$cod G$
in
$G$
such that the 2-cells of
$dom G$
are precisely the elements of
$out E$
; the 2-cells of
$cod G$
are precisely the elements of
$in E$
;
$dom (dom G) = dom (cod G)$
;
$cod (dom G) = cod (cod G)$
; and
$dom G \cup cod G$
is the boundary of
$E$
. Moreover,
$dom G$
extends to a 2-sphere
$S(dom G)$
such that
$G-dom G$
lies strictly inside
$S(dom G)$
.
Definition 8.5.
Given a 3-embedding
$(G,g)$
, we shall denote
$dom (dom G)$
by
$S$
and
$cod (dom G)$
by
$T$
, and we shall denote the region enclosed by
$S(dom G)$
by
$B(dom G)$
. Observe, more generally, that if
$X$
is any 2-pasting scheme in
$G$
with domain
$S$
and codomain
$T$
, then
$X$
together with
$S(dom G) - dom G$
forms a 2-sphere. We shall denote this 2-sphere by
$S(X)$
, and we shall denote the region it encloses by
$B(X)$
. Note that every 2-cell of
$X$
is an element of
$in (B(X))$
. If
$F$
is a 3-cell of
$(G,g)$
, we shall denote by
$d(F)$
the union over all
$k\leq 2$
of the set of those
$k$
-cells of
$G$
that lie on the boundary of
$F$
but not on
$cod F$
. In Johnson (Reference Johnson1987), this set was called the “beginnings” of
$F$
: it is equally the set of those
$k$
-cells in the interior of
$dom F$
. Dually, we shall denote by
$c\,(F)$
the union over all
$k\leq 2$
of the set of those
$k$
-cells of
$G$
that lie on the boundary of
$F$
but not on
$dom F$
. In Johnson (Reference Johnson1987), this set was called the “ends” of
$F$
. The 2-computad
$G$
, the set of regions it encloses, and
$dom$
and
$cod$
as defined above, yield a 3-computad, which we shall denote by
$C(G)$
.
Definition 8.6.
A 3-embedding
$(G,g)$
satisfies the 2-cell extension condition if every 2-cell
$x$
extends to a 2-pasting scheme
$X$
in
$G$
with
$dom X = S$
and
$cod X = T$
.
Remark 8.7.
A 2-embedding that satisfies the 1-cell extension condition is exactly a 2-pasting scheme as defined in Section 7: that a 2-pasting scheme is a 2-embedding that satisfies 1-cell extension follows from Proposition 7.6
; the converse is trivial. However, a 3-embedding that satisfies 2-extension does not seem to suffice to determine what we require of a 3-pasting scheme. The reason is that such a 3-embedding will have a “topmost” 3-cell
$F$
, and for any such, if
$d(F)$
is removed from
$G$
, we want the domain of the new 3-embedding to be a 2-pasting scheme embedded in 3-space. That does not seem to be the case in general for
$n=3$
, although we do not have a counterexample. So we require a further definition.
Definition 8.8.
A 3-embedding
$(G,g)$
satisfies interiority if, given any 0-cell or 1-cell
$x$
of
$G$
, the cell
$x$
appears in
$c(F)$
for at most one interior region
$F$
of
$(G,g)$
; and if
$x$
appears on
$dom G$
, then it appears in
$c(F)$
for no interior region of
$(G,g)$
.
Definition 8.9. A 3-pasting scheme is a 3-embedding that satisfies the 2-cell extension condition and interiority.
We will later need a few more definitions as follows.
Definition 8.10.
A 3-pasting diagram
$((G,g),h)$
in a 3-computad
$H$
is a 3-pasting scheme
$(G,g)$
together with a 3-computad morphism
$h:C(G)\rightarrow H$
. The domain of a 3-pasting diagram
$((G,g),h)$
is given by
$dom G$
and the restriction of
$h$
to
$dom G$
; dually for the codomain. We shall call a 3-pasting diagram
$((G,g),h)$
simply a 3-pasting scheme in
$H$
if
$h$
is a monomorphism in the category
$3$
-
$Computad$
, that is, if
$h$
is injective on
$k$
-cells for all
$k=0$
to 3.
Definition 8.11.
A 3-embedding
$(G,g)$
is spherical if
$dom G$
and
$cod G$
are spherical 2-pasting schemes and
$dom G\cup cod G$
is homeomorphic to the 2-sphere.
Definition 8.12.
A 3-computad
$G$
is locally spherical if each 3-cell together with its domain and codomain is a spherical 3-pasting scheme in
$G$
containing one 3-cell.
Definition 8.13.
A 3-pasting inclusion into a 3-pasting scheme
$(G,g)$
is a 2-computad inclusion
$j$
into
$G$
such that the composite
$gj$
is a 3-pasting scheme for which every 3-cell is a 3-cell of
$(G,g)$
. A 3-subpasting scheme is an equivalence class of 3-pasting inclusions under the evident equivalence.
9. Underlying Three-Dimensional Topology
The main result of this section is Theorem9.11, which states that given any 3-pasting scheme
$(G,g)$
with at least one interior region, there exists an interior region
$F$
such that
$dom F$
is a subpasting scheme of
$dom G$
, and such that if one removes
$d(F)$
from
$G$
, then one has a new 3-pasting scheme containing one fewer interior regions. But first consider an illustrative example.
Example 9.1. Here is an example of a 3-pasting scheme with just one 3-cell whose underlying graph has a cycle.
Note the relationship between Example 9.1 and the following definition.
Definition 9.2.
A 3-embedding
$(G,g)$
is acyclic if there exists no alternating sequence
$F_0,x_o,F_1,\ldots ,F_{m}$
with m
$\gt$
0, with each
$F_{i}$
a 3-cell and each
$x_{i}$
a 2-cell of
$(G,g)$
, with
$F_0=F_{m}$
, and
$x_{i}$
an element of
$out F_{i}\cap in F_{i+1}$
.
This is a two-dimensional notion of acyclity that must hold of a three-dimensional pasting scheme, whereas Example 9.1 addressed a one-dimensional such notion that, although essential for a two-dimensional pasting scheme, would constrain us too much in three dimensions.
Proposition 9.3.
If a 3-embedding
$(G,g)$
satisfies the 2-cell extension condition, then it is acyclic.
Proof.
Suppose there is a cycle
$F_0,x_0,\ldots ,F_{m}$
. Then,
$x_0$
extends to a 2-pasting scheme
$X$
from
$S$
to
$T$
in
$G$
, which in turn extends to
$S(X)$
, enclosing the region
$B(X)$
. Recall that every 2-cell of
$X$
is an element of
$in (B(X))$
, and
$S(X)$
extends
$X$
through the exterior region of
$(G,g)$
. So
$F_0$
is outside
$B(X)$
but
$F_1$
is inside it. Since
$F_0=F_{m}$
, it follows that there exists an
$i$
such that
$F_{i}$
is inside
$B(X)$
but
$F_{i+1}$
is outside it, but this is a contradiction since every 2-cell on
$X$
is oriented into
$B(X)$
, so cannot be an element of
$out F_{i}$
.
We shall call any interior region
$F$
of
$(G,g)$
such that
$dom F$
is a subpasting scheme of
$dom G$
a topmost region of
$(G,g)$
.
Proposition 9.4.
If a 3-embedding
$(G,g)$
is acyclic and has at least one interior region, then it has a topmost region.
Proof.
Let
$F_0$
be any interior region. If every 2-cell of
$in F$
lies on
$dom G$
, then since
$dom F$
is spherical, it follows that
$dom F$
is a subpasting scheme of
$dom G$
. If not, then let
$x_0$
be a 2-cell of
$in F$
that is not on
$dom G$
. It must therefore be an element of
$out F_1$
for some interior region
$F_1$
. Continue inductively. Since
$(G,g)$
is finite and acyclic, there must exist some
$m$
for which
$dom F_{m}$
is a subpasting scheme of
$dom G$
.
Corollary 9.5.
If a 3-embedding
$(G,g)$
with at least one interior region satisfies the 2-cell extension condition, then it has a topmost region.
This is not quite enough to yield the result we seek as we need to conclude that replacing the domain of a topmost region by its codomain replaces
$domG$
by another 2-pasting scheme and then be able to continue inductively. We need a little more than that too. We proceed as follows.
Definition 9.6.
A 3-embedding
$(G,g)$
satisfies the domain replacement condition if for every 2-pasting scheme
$X$
in
$G$
with domain
$S$
and codomain
$T$
,
-
(i) if
$F$
is a 3-cell with
$dom F$
a subpasting scheme of
$X$
, then replacing
$dom F$
by
$cod F$
in
$X$
gives another 2-pasting scheme embedded in 3-space, and also in
$X$
, replacing
$dom F$
by a single cell gives a 2-pasting scheme
-
(ii) if
$F$
and
$F'$
are different 3-cells such that
$dom F$
and
$dom F'$
are both subpasting schemes of
$X$
, then in
$X$
, replacing both
$dom F$
and
$dom F'$
by single cells gives a 2-pasting scheme.
Note the difference in the two parts of condition (i) of domain replacement. By definition,
$X$
is a pair
$(\overline {X} ,j_{X})$
consisting of a 2-pasting scheme
$\overline {X}$
and a monomorphism
$j_{X}:C(X)\rightarrow G$
. Since
$G$
is locally spherical,
$dom F$
is a pair
$(\overline {dom F} ,j_{dom F})$
consisting of a spherical 2-pasting scheme
$\overline {dom F}$
and a monomorphism
$j_{dom F}$
; similarly for
$cod F$
. We assume that
$\overline {dom F}$
is a subpasting scheme of
$\overline {X}$
and that
$j_{X}$
restricts to
$j_{dom F}$
. If we replace
$\overline {dom F}$
by
$\overline {cod F}$
in
$\overline {X}$
, we would have a 2-embedding
$\overline {X'}$
, and if we make the corresponding replacement of
$j_{dom F}$
, we would have a new map
$j_{X'}$
in
$2$
-
$Computad$
. The first part of condition (i) demands that
$\overline {X'}$
is a 2-pasting scheme and that
$j_{X'}$
is a monomorphism, and hence, by composition with
$g$
, embeds
$\overline {X'}$
into 3-space. The second part of condition (i) only demands that the replacement of
$\overline {dom F}$
by a single cell is a 2-pasting scheme.
Proposition 9.7. Domain replacement implies interiority.
Proof.
We proceed by induction on the number of 3-cells of
$(G,g)$
. If
$(G,g)$
has no 3-cells, then the result is trivial. If
$(G,g)$
has
$m+1$
3-cells, then let
$F$
be a topmost 3-cell of
$(G,g)$
and let
$G_1$
be the 3-pasting scheme given by removing
$d(F)$
from
$G$
. Then, by induction,
$G_1$
satisfies interiority. By definition of 3-embedding, since
$F$
is a topmost 3-cell, no
$k$
-cell in
$d(F)$
appears in
$c(F')$
for any 3-cell
$F'$
. The result follows directly.
Lemma 9.8.
Let
$(G,g)$
be an acyclic 3-embedding that satisfies interiority (Definition 8.8). Then if
$x$
is a
$k$
-cell on
$cod G$
for any
$k\lt 2$
, then
$x$
either lies on
$dom G$
or
$x$
lies in
$c(F)$
for some interior region
$F$
of
$(G,g)$
.
Proof.
The proof is by induction on the number of 3-cells in
$(G,g)$
. If
$(G,g)$
has no 3-cells, the result is trivial. If
$(G,g)$
has
$m+1$
3-cells, then by Proposition 9.4,
$(G,g)$
has a topmost region, say
$F$
. Note that if one replaces any spherical subpasting scheme of a 2-pasting scheme by another 2-pasting scheme with the same domain and codomain, then the result is a 2-pasting scheme. Moreover, by interiority, no 0-cell or 1-cell in
$c(F)$
lies on
$dom G$
. Also, no 2-cell can lie on both
$out F$
and
$out E$
. Hence, if one removes
$d(F)$
from
$G$
, one obtains a new 3-embedding
$G_1$
. Trivially,
$G_1$
is acyclic. Moreover,
$G_1$
satisfies interiority and
$cod G_1 = cod G$
. So, by induction, we are done.
Theorem 9.9.
Let
$(G,g)$
be a 3-embedding that satisfies the 2-cell extension condition. Then
$(G,g)$
satisfies the domain replacement condition if and only if it satisfies interiority.
Proof.
First assume that
$(G,g)$
satisfies interiority. If one replaces any spherical subpasting scheme of a 2-pasting scheme by another 2-pasting scheme with the same domain and codomain, then the result is a 2-pasting scheme. So it suffices to show that if
$X$
is a 2-pasting scheme from
$S$
to
$T$
in
$(G,g)$
, and
$F$
is a 3-cell in
$(G,g)$
with
$dom F$
lying on
$X$
, then no
$k$
-cell in
$c(F)$
lies on
$X$
. The collection of 3-cells of
$(G,g)$
that lie outside
$B(X)$
forms a 3-embedding with domain
$dom G$
and codomain
$X$
. We shall call this 3-embedding
$X'$
. Since
$(G,g)$
satisfies the 2-cell extension condition, it is acyclic, so
$X'$
is also acyclic. Moreover,
$X'$
also satisfies interiority. So, by Lemma 9.8, for each
$k\lt 2$
, every
$k$
-cell on
$X=codX'$
occurs either on
$dom G$
or in
$c(F')$
for some
$F'$
outside
$B(X)$
. So, since
$(G,g)$
satisfies interiority, it follows that no
$k$
-cell on
$X$
lies in
$c(F)$
. For
$k=2$
, no
$k$
-cell can lie on both
$outF$
and
$outX$
. The converse holds by Proposition 9.7.
This allows us to reformulate the definition of a 3-pasting scheme as follows.
Definition 9.10.
A 3-pasting scheme is a 3-embedding
$(G,g)$
that satisfies the 2-cell extension condition and domain replacement.
Now we are ready for the 3-category pasting theorem.
Theorem 9.11.
For any 3-pasting scheme
$(G,g)$
with at least one interior region, there exists a topmost region
$F$
such that removing
$d(F)$
from
$G$
gives a new 3-pasting scheme containing one fewer interior regions.
Proof.
This follows immediately from Corollary 9.5 and Theorem9.9 given the observation that any 2-pasting scheme
$X$
from
$S$
to
$T$
in
$G$
that includes any 2-cell in the domain of a topmost 3-cell
$F$
necessarily includes every element of
$in F$
.
Note that we have not yet used condition (ii) of the domain replacement condition. It is used to show the unicity of the possible composites of a labeled pasting scheme which, along with the inductive use of Theorem9.11, completes the proof of the 3-category pasting theorem.
Tidying up now, the definition of 3-pasting scheme is not as asymmetric as it first appears. The apparent asymmetry in the definition of domain replacement is, in the presence of the 2-cell extension condition, illusory. One could say that that a 3-embedding
$(G,g)$
satisfies the codomain replacement condition if
$(G,g)$
with the reverse orientation of 3-space satisfies domain replacement.
Proposition 9.12.
Let
$(G,g)$
be an acyclic 3-embedding. Then
$(G,g)$
satisfies domain replacement if and only if it satisfies codomain replacement.
Proof.
Suppose
$(G,g)$
satisfies domain replacement. Let
$X$
be a 2-pasting scheme from
$S$
to
$T$
in
$G$
and let
$F$
be a 3-cell of
$G$
with
$cod F$
a subpasting scheme of
$X$
. We shall show that if one replaces
$cod F$
by
$dom F$
in
$X$
, one has a 2-pasting scheme embedded in 3-space. We proceed by induction on the number of 3-cells of
$(G,g)$
that lie outside
$B(X)$
. If it is 1, then the 3-cell must be
$F$
, so the replacement of
$cod F$
by
$dom F$
in
$X$
is
$dom G$
, hence a 2-pasting scheme embedded in 3-space. If it is
$m+1$
, then there exists a 3-cell
$F_1$
different to
$F$
and outside
$B(X)$
. If
$F_1$
is not a topmost 3-cell, then there exists
$F_2$
outside
$B(X)$
such that
$out F_2\cap in F_1$
is non-empty. Note that
$F_2$
is not
$F$
since
$codF$
is a subpasting scheme of
$X$
but
$F_2$
lies outside
$B(X)$
. So, by induction, since
$(G,g)$
is acyclic, there exists a topmost 3-cell
$F'$
of
$(G,g)$
that lies outside
$B(X)$
and is not
$F$
. Then, if we remove
$d(F)$
from
$G$
, we are done by induction. Thus, we have proved part of codomain replacement. The rest follows directly from this part together with domain replacement. The converse is dual.
Corollary 9.13.
Let
$(G,g)$
be a 3-embedding that satisfies the 2-cell extension condition. Then
$(G,g)$
satisfies domain replacement if and only if it satisfies codomain replacement.
10. Conclusion
The importance of associativity could hardly be overstated. It is fundamental to functional programming, partial evaluation, out-of-order computation, precomputation, database query optimization, and many of the fundamental mathematical notions underlying almost all computer science. In the classical, one-dimensional, rearrange the brackets, approach, little attention has been paid to a feature of associativity that is vitally important: the fact that any order of computation still results in achieving the final answer. Rightly, the single final answer independent of order of computation is important, and in the classical case achieving a final answer is guaranteed, and so is not remarked upon.
Two-dimensional associativity is similarly straightforward. The 2-category pasting theorem assures us of a common final answer, and in two-dimensional algebra, substituting a result for a partial computation can never lead to a situation that fails to terminate.
The main purpose of this paper has been to prove a 3-categorical pasting theorem that assures us of a common final answer for three-dimensional algebra, but to highlight the impossibility of avoiding circumstances that might lead us to deadlock and failure to reach that answer. We believe that that is a fundamental part of associativity that is little understood, and that it is very important to identify circumstances where computations might fail to terminate. Such situations, like the crossed arms mentioned in the introduction, can be understood globally but may be arbitrarily hard to identify locally in a complicated computation, so our first step is to raise awareness of the existence of that anomaly and the importance of not taking for granted something which happens without remark in (only) the one- and two-dimensional cases.
In future work, we expect to further develop the theory of pasting as an operation in its own right and to highlight the conditions under which associativity, including termination after substitution, can be assured along with the connections to oriented geometry and homotopical algebra. We also look forward to the forthcoming thesis of Diana Kessler (Kessler (Reference Kessler2026)) and her work with Amar Hadzihasanovic which promises further new obstructions to composition at dimension 4 (see Example 126 of Hadzihasanovic and Kessler (Reference Hadzihasanovic and Kessler2023)), and the novel insights that that work may bring.
Acknowledgements
We are very pleased to record our gratitude to Angela Callaghan, Angus Johnson, Soichiro Fuji and Alex Simpson, and more generally to the members of the Australian Category Seminar. We acknowledge, with gratitude, support from the Australian Research Council. This paper has been much improved by the wise advice of an anonymous referee whose suggestions for future work will be taken up elsewhere. Opus 4.6 was used for the conversion of three diagrams.
Open access
