Undecidability of the Free Adjoint Construction

R. J. MacG. Dawson ^{∗} Saint Mary’s University

email: rdawson@stmarys.ca

R. Paré Dalhousie University email: pare@mscs.dal.ca

D.A. Pronk Dalhousie University email: pronk@mscs.dal.ca

August 1, 2002

Abstract

In this paper we discuss some aspects of categories obtained by freely adding right adjoints to all arrows in a category. We will give a description of the arrows and 2-cells in such a category and show how the equivalence relation on the 2-cells for an appropriately chosen category C_{𝔸} can be used to simulate a 2-register abacus 𝔸, so that deciding whether two 2cells with different representatives are equal becomes equivalent to solving the halting problem for the abacus. In particular, this implies that (in general) equality of 2-cells in such categories is undecidable.

Keywords: free adjoint construction, 2-category, undecidability, abacus

AMS classification: 18A40, 18D05

∗All three authors are suppported by NSERC grants.

1 Introduction

In the 2-category Cat, an arrow (that is, a functor) f: A → B is said to have a right adjoint u: B → A if there exist 2-cells ε: f ∘ u ⇒ i_{B} and η: i_{A} ⇒ u ∘ f, such that the composite f ⇒^{f∘η} f ∘ (u ∘ f) = (f ∘ u) ∘ f ⇒^{ε∘f} f is equal to i_{f}, and the composite u ⇒^{η∘u} (u ∘ f) ∘ u = u ∘ (f ∘ u) ⇒^{u∘ε} u is equal to i_{u}. This definition can obviously be extended to any 2-category; in most cases, as in Cat itself, not all arrows have adjoints.

There will always be some adjunctions, however. Identity arrows are selfadjoint, and more generally any inverse pair f, f^{−1} constitutes an adjunction with identity 2-cells as unit and counit. Another special class of adjunctions, more general than inverse pairs, are the equivalences, pairs for which the unit and counit are isomorphisms.

If a 2-category does not have a certain type of adjunction, there may be a construction that adds these. Some examples are:

• Any semigroup may be turned into a group in a canonical way by adding inverses. The constructions of the integers from the natural numbers, and of the nonzero rationals from the nonzero integers, are familiar examples.

• Gabriel and Zisman’s category of fractions [6] adds inverses to a class of arrows satisfying certain conditions. (This construction is not explicitly 2-categorical, because the units and counits are identities; however, as shown in [9], it is useful to consider it in this context.)

• Quillen’s homotopy categories [10] add inverses to the weak equivalences of a model category.

• Pronk’s bicategory of fractions [9] add equivalences to a suitable class of arrows, thereby transforming the original arrows into equivalences as well.

• In [11] Schanuel and Street add a right adjoint to the single nonidentity arrow of 2 The structure of the resulting 2-category is surprisingly rich; it contains both Δ and Δ^{op} as hom-categories.

• In [3], the authors develop a construction Π_{2}(C) which adds general adjoints to all arrows in any category.

• In [5], it is shown that if the original category has pullbacks, and adjoints are added subject to the Beck-Chevalley condition, the 2-category Span(C) is obtained.

In all of the above examples, there are equivalence relations on the resulting structures; the basic principle is illustrated by the equation 2 − 4 = 3 − 5 in the first example above. In most of these cases, it is fairly straightforward (if we know the structure of the original category) to determine whether two compositions of arrows or 2-cells are equal. In this paper, however, we show that the equality of 2-cells in Π_{2}(C) is undecidable for some choices of C, even when C is presented in such a fashion that all compositions can be evaluated.

It should be noted that in general there is more than one way to add adjoints. For instance consider the category 2 = (0 →^{f} 1). To give f a right adjoint, we must add an arrow u: 1 → 0, and 2-cells ε and η. However, the requirement that f ⊣ u does not fully define the new bicategory. For instance, it does not tell us whether ufuf = uf. In the construction of Schanuel and Street, this identity - and any other not required by the adjunction - does not hold, making Adj initial among all 2-categories extending 2 in which f has an adjoint, or, equivalently, the free construction of this type.

In [3] we extend this construction, adding right adjoints to an arbitrary category C to obtain a 2-category Π_{2}(C). The adjoint arrows correspond to arrows of C^{op}; thus, a general arrow of Π_{2}(C) corresponds to a zigzag of arrows of C. The 2-cells of Π_{2}(C) are generated by the identity cells on the arrows of C and their adjoints, and by the units and counits. Every composition of these 2-cells corresponds to a planar diagram of a special type, called a fence (these are described below); vertical and horizontal composition of fences are defined. These compositions do not satisfy the middle-four interchange law; to obtain a 2category we must identify all “vertical-first” compositions of fences (α∗β)∘(γ∗δ) with the corresponding “horizontal-first” compositions (α ∘ γ) ∗ (β ∘ δ). The resulting 2-category is Π_{2}(C).

The equivalence relation mentioned above is shown in [3] to be generated by a class of local substitutions based upon compositions and factorizations within C. Fences that can be obtained from each other by a single such operation will be called directly equivalent. Both the definition of a fence, and the equivalence relation, will be given in detail in Section 2 below; for proofs, the reader is referred to the paper cited.

In this paper, we show that the equivalence relation on fences that yields Π_{2}(C) is undecidable for certain choices of C. To do this, we follow the usual strategy of modelling a known undecidable problem within the one we wish to prove undecidable. Common choices for the known undecidable problem are the word problem for groups and the halting problem for Turing machines. Both of these involve structures (strings of generators in one case, the “tape” of the Turing machine in the other) that can grow without bound. As will be shown below, any two equivalent fences in Π_{2}(C) must have the same number of arrows. We will therefore use a different (though related) undecidable problem, the halting problem for abacuses.

Abacuses, introduced by Lambek [7] and (under the name “register machines”) by Minsky [8], are universal models for computation similar to Turing machines. Like Turing machines, they have a finite number of internal program states, a halting state, and change state in a deterministic manner, branching on some instructions based upon the contents of a specified memory location. However, where the Turing machine has infinitely many registers, each able to take a finite number of values, the abacus has finitely many registers, each able to hold an arbitrarily large natural number. It was shown by Minsky (op. cit.) that any abacus, and any Turing machine, may be simulated by an appropriate 2-register abacus; in particular, there exist universal 2-register abacuses, for which the halting problem is undecidable.

Undecidability occurs in several places in higher-dimensional category theory. For instance, in [1] it was shown that the word problem for a free double category could be undecidable. In [4] the authors show that various free extensions of double categories and 2-categories involve an undecidable word problem for composable arrangements of 2-cells.

2 Freely Adding Adjoints

In [3] we have studied the structure of a 2-category Π_{2}(C) obtained by freely adding adjoints to all arrows in a category C. We start by summarizing the results of [3] for this special case.

2.1 The 2-category Π_{2}(C).

Let C be any category. We write Π_{2}(C) for the following 2-category:

1. The objects of Π_{2}(C) are the same as the objects of C, so Π_{2}(C)_{0} = C_{0}.

2. The arrows in Π_{2}(C) are zig-zags in C, i.e. an arrow in C(A, B) is of the form

[figure: A = C_{1}; f_{1}; D_{1}; g_{1}; C_{2}; f_{2}; D_{2}; ⋯; D_{n−1}; g_{n−1}; C_{n}; f_{n}; D_{n} = B.]

We denote such an arrow by

(g_{1}, ⋯, g_{n−1}; f_{1}, ⋯, f_{n}).

3. A 2-cell

(g_{1}, ⋯, g_{n−1}; f_{1}, ⋯, f_{n}) ⇒ (g′_{1}, ⋯, g′_{m−1}; f′_{1}, ⋯, f′_{m})

is an equivalence class of a special kind of diagrams, called fences.

An example of a fence is

[figure: A = C_{1}; f_{1}; D_{1}; g_{1}; C_{2}; f_{2}; D_{2}; g_{2}; C_{3}; f_{3}; D_{3} = B; h_{2}; k_{1}; k_{2}; h_{3}; h_{4}; A = C′_{1}; f′_{1}; D′_{1}; g′_{1}; C′_{2}; f′_{2}; D′_{2}; g′_{2}; C′_{3}; f′_{3}; D′_{3}; g′_{3}; C′_{4}; f′_{4}; D′_{4} = B]

Specifically, fences are determined by an adjoint pair of order-preserving index functions

ϕ: {1, ⋯, m} → {1, ⋯, n} and ψ: {1, ⋯, n} → {1, ⋯, m}

such that ψϕ(i) ≥ i and ϕψ(j) ≤ j, together with families of arrows

k_{j}: D_{j} → D′_{ψ(j)} and h_{i}: C_{ϕ(i)} → C′_{i},

such that all resulting squares commute, i.e.

1. For every 1 ≤ i < n

f′_{i}h_{i} = \{ \begin{matrix}g′_{i}h_{i+1} & if φ(i) = φ(i + 1) \\ k_{φ(i)+1}f_{φ(i)} & otherwise \end{matrix}

2. For every 1 ≤ j < m

k_{j}g_{j} = \{ \begin{matrix}k_{j+1}f_{j+1} & ifψ(j) = ψ(j + 1) \\ g′_{ψ(j)}h_{ψ(j)+1} & otherwise \end{matrix}

Finally we require that h_{1} = id_{A} and k_{n} = id_{B}. We denote such a representative for a 2-cell by (ϕ; ψ; k_{1}, …, k_{n−1}; h_{2}, …, h_{m}). Note that in the example above, ψ(1) = 2, ψ(2) = 2 and ψ(3) = 4, and ϕ(1) = 1, ϕ(2) = 1, ϕ(3) = 3, and ϕ(4) = 3.

2.2 Composition

Composition of arrows in Π_{2}(C) is defined by concatenating of the zig-zags and composing the two composable morphisms:

(g_{1}, ⋯, g_{n−1}, f_{1}, ⋯, f_{n}) ∘ (h_{1}, ⋯, h_{m−1}, k_{1}, ⋯, k_{n}) =

(h_{1}, ⋯, h_{m−1}, g_{1}, ⋯, g_{n−1}, k_{1}, ⋯, k_{n−1}, f_{1} ∘ k_{n}, f_{2}, ⋯, f_{n})

Vertical composition of fences can be calculated by drawing the diagrams above one another and constructing the compositions of the arrows when that is possible. For example, composing

[figure: A = C_{1}; f_{1}; D_{1}; g_{1}; C_{2}; f_{2}; D_{2}; g_{2}; C_{3}; f_{3}; D_{3} = B; h_{2}; k_{1}; k_{2}; h_{3}; h_{4}; A = C′_{1}; f′_{1}; D′_{1}; g′_{1}; C′_{2}; f′_{2}; D′_{2}; g′_{2}; C′_{3}; f′_{3}; D′_{3}; g′_{3}; C′_{4}; f′_{4}; D′_{4} = B]

with

[figure: A = C′_{1}; f′_{1}; D′_{1}; g′_{1}; k′_{1}; C′_{2}; f′_{2}; D′_{2}; g′_{2}; k′_{2}; C′_{3}; f′_{3}; h′_{2}; D′_{3}; g′_{3}; k′_{3}; C′_{4}; f′_{4}; h′_{4}; D′_{4} = B; h′_{3}; A = C′′_{1}; f′′_{1}; D′′_{1}; g′′_{1}; C′′_{2}; f′′_{2}; D′′_{2}; g′′_{2}; C′′_{3}; f′′_{3}; D′′_{3}; g′′_{3}; C′′_{4}; f′′_{4}; D′′_{4} = B]

gives

[figure: A = C′_{1}; f′_{1}; D′_{1}; g′_{1}; k′_{2}k_{1}; C′_{2}; f′_{2}; D′_{2}; g′_{2}; k′_{2}k_{2}; C′_{3}; f′_{3}; h′_{2}h_{3}; h′_{3}; A = C′′_{1}; f′′_{1}; D′′_{1}; g′′_{1}; C′′_{2}; f′′_{2}; D′′_{2}; g′′_{2}; C′′_{3}; f′′_{3}; D′′_{3}; g′′_{3}; C′′_{4}; f′′_{4}; h′_{4}h_{4}; D_{3} = B; D′′_{4} = B]

To be precise, the index functions of the new 2-cell are the compositions of the index functions of the original 2-cells, and the arrows in the diagrams are the compositions of the corresponding arrows:

[ϕ′, ψ′, (k′_{j}), (h′_{i})] · [ϕ, ψ, (k_{j}), (h_{i})] =
= [ϕ ∘ ϕ′, ψ′ ∘ ψ, (\overline{k}_{j}), (\overline{h}_{i})],

where \overline{k}_{j} = k_{ψ(j)}k_{j} and \overline{h}_{i} = h_{i}h′_{ϕ′(i)}.

Horizontal composition of fences is defined by concatenation, together with some compositions in the category C. This is a tensor-like construction over C. For example, horizontal composition of

[figure: A = C_{1}; f_{1}; D_{1}; g_{1}; C_{2}; f_{2}; D_{2} = B; h_{2}; k_{1}; A = C′_{1}; f′_{1}; D′_{1}; g′_{1}; C′_{2}; f′_{2}; D′_{2} = B]

with

[figure: B = E_{1}; p_{1}; F_{1}; q_{1}; E_{2}; p_{2}; F_{2} = C; l_{2}; m_{1}; B = E′_{1}; p′_{1}; F′_{1}; q′_{1}; E′_{2}; p′_{2}; F′_{2} = C]

gives

[figure: A = C_{1}; f_{1}; D_{1}; g_{1}; C_{2}; p_{1}f_{2}; F_{1}; q_{1}; E_{2}; p_{2}; F_{2} = C; h_{2}; p′_{1}k_{1}; l_{2}f_{2}; m_{1}; A = C′_{1}; f′_{1}; D′_{1}; g′_{1}; C′_{2}; p′_{1}f′_{2}; F′_{1}; q′_{1}; E′_{2}; p′_{2}; F′_{2} = C]

To be precise, if

[\overline{ϕ}; \overline{ψ}; \overline{k}_{1}, …, \overline{k}_{n−1}; \overline{h}_{2}, …, \overline{h}_{m}]:
(g_{1}, …, g_{n−1}; f_{1}, …, f_{n}) ⇒ (g′_{1}, …, g′_{m−1}; f′_{1}, …, f′_{m})

and

[ϕ̃; ψ̃; k̃_{1}, …, k̃_{p−1}; h̃_{2}, …, h̃_{q}]:
(u_{1}, …, u_{p−1}; v_{1}, …, v_{p}) ⇒ (u′_{1}, …, u′_{q−1}; v′_{1}, …, v′_{q})

are 2-cells such that cod(f_{n}) = dom(v_{1}) (i.e., that are composable), then the horizontal composition is defined as

[ϕ̃; ψ̃; k̃_{1}, …, k̃_{p−1}; h̃_{2}, …, h̃_{q}] ∘ [\overline{ϕ}; \overline{ψ}; \overline{k}_{1}, …, \overline{k}_{n−1}; \overline{h}_{2}, …, \overline{h}_{m}] =

[ϕ; ψ; k_{1}, …, k_{n−1}; h_{2}, …, h_{m}],

where the index functions

ψ: {1 …, n + p − 1} → {1, …, m + q − 1}
ϕ: {1, …, m + q − 1} → {1, …, n + p − 1}

are

ϕ(i) = \{ \begin{matrix}\overline{ϕ}(i) & for & i ≤ m \\ ϕ̃(i − m + 1) + n − 1 & for & i > m \end{matrix}
ψ(j) = \{ \begin{matrix}\overline{ψ}(j) & for & j ≤ n − 1 \\ ψ̃(j − n + 1) + m − 1 & for & j ≥ n \end{matrix}

and

k_{j} = \{ \begin{matrix}\overline{k}_{j} & if & j < n and \overline{ψ}(j) < m \\ v′_{1}\overline{k}_{j} & if & j < n and \overline{ψ}(j) = m \\ k̃_{j−n+1} & if & j ≥ n \end{matrix}

h_{i} = \{ \begin{matrix}\overline{h}_{i} & if & i ≤ m \\ h̃_{i−m+1}f_{n} & if & i > m and ϕ̃(i − m + 1) = 1 \\ h̃_{i−m+1} & if & i > m and ϕ̃(i − m + 1) > 1 \end{matrix}

2.3 The equivalence relation

The pair of composition operations given above does not have the middle-four exchange property ([3], Example 1). If we identify every composition (α∘β)∗(γ∘ δ) with the corresponding composition (α∗γ)∘(β∗δ), we obtain (op. cit., section 3) the equivalence relation generated (through symmetry and transitivity) by the following relationship: Two diagrams θ and ω representing 2-cells in C^{∗} are called directly equivalent if they are everywhere the same except for two parts of the following shapes: the cell ω contains

[figure: C_{i}; f_{i}; h_{j}; D_{i}; l; k_{i}; g_{i}; C_{i+1}; D′_{j−1}; g′_{j−1}; C′_{j}; f′_{j}; D′_{j}]

and the cell θ contains

[figure: C_{i}; f_{i}; k̃_{i}; D_{i}; l; h̃_{j}; g_{i}; C_{i+1}; D′_{j−1}; g′_{j−1}; C′_{j}; f′_{j}; D′_{j}]

and there exists an arrow l: D_{i} → C′_{j} which factors both diagrams.

Both vertical and horizontal composition are well-defined on equivalence classes of 2-cells ([3], section 2), and together they have the middle-four property. The resulting 2-category is given the name Π_{2}C. The reader is referred to section 4 of [3] for a description of the universal properties of this construction.

3 From abacus to category

In this section we will construct a category, presented in such a way that any composition may be computed trivially, but such that the equivalence relation on fences models an undecidable problem in the theory of computation. There are various undecidable problems that could be used; as the length of fences does not vary within an equivalence class, the abacus (which has a fixed number of registers) is a more convenient model than the Turing machine (the tape of which must be capable of indefinite extension) or the word problem for groups (which again may involve intermediate words of arbitrarily great length). As Minsky has shown that a universal abacus may have as few as two registers, we shall restrict our attention to such a machine.

We shall construct, for any 2-register abacus 𝔸, a category C_{𝔸}, containing three sets of arrows which are indexed by the program state, X register, and Y register of 𝔸 respectively. We then exhibit a family of fences over C_{𝔸}, each containing one arrow from each of these three sets, and therefore indexed by the complete internal state of the abacus. Finally, we show that two such fences are directly equivalent if and only if the abacus passes directly from the state corresponding to one fence to that corresponding to the other. It follows that, if 𝔸 is a universal 2-register abacus, any algorithm to determine the equivalence of fences over C_{𝔸} would also solve the halting problem for 𝔸; the equivalence relation is therefore undecidable.

3.1 Definition of an abacus

Definition 1 An (n-register) abacus consists of

(i) A finite set of states S; (ii) Variables X_{1}, ⋯, X_{n}in ℕ which are considered as the contents of the registers; (iii) A function Inst: S → {INCX, INCY, DECX, DECY, HALT}; (iv) A starting state s_{0} ∈ S;

(v) Transition functions σ: S → S and σ′: S → S.

In this paper we will only be interested in the notion of a 2-register abacus, so from now on we will take n = 2 in the definition above, and use X and Y as variables for the registers. The behaviour of the abacus is a partial function S × ℕ × ℕ → S × ℕ × ℕ

𝔖 = (s, X, Y) ↦^{Σ} 𝔖′ = (s′, X′, Y′)

defined as follows

(s′, X′, Y′) = \{ \begin{matrix}(σ(s), X + 1, Y) & if & Inst(s) = INCX \\ (σ(s), X, Y + 1) & if & Inst(s) = INCY \\ (σ(s), X − 1, Y) & if & Inst(s) = DECX and X > 0 \\ (σ′(s), X, Y) & if & Inst(s) = DECX and X = 0 \\ (σ(s), X, Y − 1) & if & Inst(s) = DECY and Y > 0 \\ (σ′(s), X, Y) & if & Inst(s) = DECY and Y = 0 \\ undefined & if & Inst(s) = HALT. \end{matrix}

We can represent this by a graph whose nodes are the elements of S and whose edges are of the form

[figure: s; INCX; σ(s); s; INCY; σ(s); σ(s); σ(s); s; DECX; X=0; s; DECY; Y =0; σ′(s); σ′(s)]

So the σ and σ′ permit branching at nodes s with Inst(s) ∈ {DECX, DECY}. Here is a simple example which adds the contents of the X-register and the Y -register and puts the sum in the X-register and 0 in the Y -register.

[figure: start; s_{0}; Y =0; DECY; s_{1}; s_{2}; INCX]

If one starts with X = 4 and Y = 3, this abacus would go through the following states: (s_{0}, 4, 3) ↦ (s_{2}, 4, 2) ↦ (s_{0}, 5, 2) ↦ (s_{2}, 5, 1) ↦ (s_{0}, 6, 1) ↦ (s_{2}, 6, 0) ↦ (s_{0}, 7, 0) ↦ (s_{1}, 7, 0) at which point it halts.

3.2 A graph representation for C_{𝔸}

Let A be a 2-register abacus. The category C_{𝔸} is generated by a graph of the following form:

[figure: A; X; g_{2}; x_{m}; ···; f_{1}; C; ···; ···; c_{s}; ···; Y; g_{1}; f_{1}; ···; y_{n}; B; A; X′; g′_{2}; f′_{1}; C′; Y′; g′_{1}; f′_{2}; B]  (1)

So the set of objects of the category C_{𝔸} is

C_{0} = {A, X, X′, C, C′, Y, Y′, B},

and the horizontal arrows shown in (1) are the only arrows in their hom-sets. The diagonal and vertical arrows in (1) represent hom-sets containing more than one element. These hom-sets are symmetric in the sense that the right side of the diagram is a mirror image of the left side.

The hom-sets that are indicated by vertical arrows in the diagram (1) are:

Hom(C, C′) = {c_{s}|s ∈ S}
Hom(X, X′) = {x_{m}|m ∈ ℕ}
Hom(Y, Y′) = {y_{n}|n ∈ ℕ}

These satisfy the following relations:

g′_{2}x_{m} = g_{2} for all m ∈ ℕ,
c_{s}f_{1} = f′_{1}x_{m} for all s ∈ S and m ∈ ℕ,
f′_{2}y_{n} = f_{2} for all n ∈ ℕ.

The hom-sets indicated by the diagonal arrows in the diagram (1) are

Hom(C, X′) = {α_{m,s}, β_{m,s}|m ∈ ℕ, s ∈ S with Inst(s) ∈ {INCX, DECX}}
Hom(C, Y′) = {γ_{n,s}, δ_{n,s}|n ∈ ℕ, s ∈ S with Inst(s) ∈ {INCY, DECY}}.

The arrow α_{m,s} makes the following diagram commute

\xymatrix{X \ar[r]^{f_{1}} \ar[d]_{x_{m}} & C \ar[dl]_{α_{m,s}} \ar[d]^{c_{s}} \\ X′ \ar[r]_{f′_{1}} & C′,}

i.e.,

x_{m} = α_{m,s} ∘ f_{1} and f′_{1} ∘ α_{m,s} = c_{s}.  (2)

We also require that in the diagram

\xymatrix{ & X \ar@{.>}[r]^{f_{1}} \ar@{.>}[d]_{x_{m}} & C \ar[dl]^{α_{m,s}} \ar[dl]_{β_{m,s}} \ar@{.>}[d]^{c_{s}} & Y \ar[l]_{g_{1}} \\ A & X′ \ar[l]^{g′_{2}} \ar@{.>}[r]_{f′_{1}} & C′}

we have

α_{m,s} ∘ g_{1} = β_{m,s} ∘ g_{1} and g′_{2} ∘ α_{m,s} = g′_{2} ∘ β_{m,s}.  (3)

The β_{m,s} need to satisfy the following equations:

β_{m,s} ∘ f_{1} = \{ \begin{matrix}x_{m+1} & if Inst(s) = INCX \\ x_{m−1} & if Inst(s) = DECX and m > 0 \\ x_{0} & if Inst(s) = DECX and m = 0 \end{matrix}  (4)

and

f′_{1} ∘ β_{m,s} = \{ \begin{matrix}c_{σ(s)} & if Inst(s) = INCX \\ c_{σ(s)} & if Inst(s) = DECX and m > 0 \\ c_{σ′(s)} & if Inst(s) = DECX and m = 0 \end{matrix}  (5)

We also write

κ(x_{m}, c_{s}) := β_{m,s} ∘ f_{1} and λ(x_{m}, c_{s}) := f′_{1} ∘ β_{m,s}.  (6)

Dually, the arrow γ_{n,s} makes the following diagram commute

\xymatrix{C \ar[d]_{c_{s}} \ar[dr]^{γ_{n,s}} & Y \ar[l]_{g_{1}} \ar[d]^{y_{n}} \\ C′ & Y′ \ar[l]^{g′_{1}}}

i.e.,

y_{n} = γ_{n,s} ∘ g_{1} and g′_{1} ∘ γ_{m,s} = c_{s}.  (7)

We also require that in the diagram

\xymatrix{X \ar[r]^{f_{1}} & C \ar@{.>}[d]_{c_{s}} \ar[dr]^{γ_{n,s}} \ar[dr]_{δ_{n,s}} & Y \ar@{.>}[l]_{g_{1}} \ar@{.>}[d]^{y_{n}} \\  & C′ & Y′ \ar@{.>}[l]^{g′_{1}} \ar[r]_{f′_{2}} & B}

we have that

γ_{n,s} ∘ f_{1} = δ_{n,s} ∘ f_{1} and f′_{2} ∘ γ_{n,s} = f′_{2} ∘ δ_{n,s}.  (8)

The δ_{m,s} need to satisfy the following equations:

δ_{n,s} ∘ g_{1} = \{ \begin{matrix}y_{n+1} & if Inst(s) = INCY \\ y_{n−1} & if Inst(s) = DECY and n > 0 \\ y_{0} & if Inst(s) = DECY and n = 0 \end{matrix}  (9)

and

g′_{1} ∘ δ_{n,s} = \{ \begin{matrix}c_{σ(s)} & if Inst(s) = INCY \\ c_{σ(s)} & if Inst(s) = DECY and n > 0 \\ c_{σ′(s)} & if Inst(s) = DECY and n = 0 \end{matrix}  (10)

We also write

κ(c_{s}, y_{n}) := g′_{1} ∘ δ_{n,s} and λ(c_{s}, y_{n}) := δ_{n,s} ∘ g_{1}.  (11)

3.3 The equivalence relation on Π_{2}(C_{𝔸})_{2}

In this section we will discuss the equivalence relation for representatives of 2-cells in Π_{2}(C_{𝔸})_{2} of the form

(ϕ, ψ, (k_{j}), (h_{i})): (g_{2}, g_{1}; I_{A}, f_{1}, f_{2}) ⇒ (g′_{2}, g′_{1}; I_{A}, f′_{1}, f′_{2})

with ϕ = ψ = id and k_{1} = id_{A}. Since this implies that the leftmost square of the diagram for this 2-cell only consists of identities, we will not draw it:

[figure: A; A; g_{2}; X; h_{2}; X′; g′_{2}; f_{1}; C; k_{2}; C′; f′_{1}; g_{1}; Y; h_{3}; Y′; g′_{1}; f_{2}; B; B; f′_{2}]

Note: For the rest of this paper we will denote such a representative by an ordered list

(h_{2}, k_{2}, h_{3})

of its vertical arrows, and we will call such a diagram rectangular.

If for any consecutive pair of vertical arrows, i.e. h_{2}, k_{2} or k_{2}, h_{3}, the functions γ, δ, κ, and λ from the previous subsection are defined, the equations (2) to (3),

(6) to (8), and (11) imply that

(h_{2}, k_{2}, h_{3}) ∼ (κ(h_{2}, k_{2}), λ(h_{2}, k_{2}), h_{3})

and

(h_{2}, k_{2}, h_{3}) ∼ (h_{2}, κ(k_{2}, h_{3}), λ(k_{2}, h_{3})).

For this particular instance of the equivalence relation, we say that (κ(h_{2}, k_{2}), λ(h_{2}, k_{2}), h_{3}) and (h_{2}, κ(k_{2}, h_{3}), λ(k_{2}, h_{3})) are successor equivalent to, or are successors of (h_{2}, k_{2}, h_{3}). We will also say that a diagram D follows from a diagram D′ if it can be obtained from D by repeatedly taking successors. This yields a rewrite system with certain restrictions: all rewrite rules replace one adjacent pair of letters by another pair.

Note that all vertical diagrams are of the form (x_{m}, c_{s}, y_{n}). We write D_{𝔖} = (x_{m}, c_{s}, y_{n}) when 𝔖 = (s, m, n). It follows directly from equations (4), (5), (9), and (10), that

Lemma 1 The diagram D_{𝔖′} is a successor of D_{𝔖} if and only if 𝔖′ = Σ(𝔖). In particular, any diagram of the form (x_{m}, c_{s}, y_{n}) has a unique successor if Inst(s) ≠ HALT, and it has no successors if Inst(s) = HALT.

Definition 2 We call a diagram D′ a predecessor of a diagram D when D is a successor of D′. Predecessors of a diagram (x_{m}, c_{s}, y_{n}) correspond to internal states 𝔖 such that Σ(𝔖) = (s, m, n).

4 Properties of the Simulation

In this section we show that the halting problem for the abacus A is equivalent to determining whether there exist natural numbers n and m and a state s with Inst(s) = HALT, such that the diagrams D_{𝔖_{1}} and (x_{m}, c_{s}, y_{n}) represent the same 2-cell in Π_{2}(C_{𝔸}).

This quantification over the natural numbers is not actually necessary. Given an abacus A that can halt in a state (h, m, n) with m or n nonzero, it is always possible to modify it to obtain a new abacus A^{∘} that ‘clears the registers’ before halting but otherwise behaves identically. We create two new ‘pre-halt’ states p_{1} and p_{2} with the following properties:

Inst(p_{1}) = DECX, σ(p_{1}) = p_{1}, σ′(p_{1}) = p_{2}
Inst(p_{2}) = DECY, σ(p_{2}) = p_{2}, σ′(p_{2}) = h

Whenever σ(s) = h or σ′(s) = h in 𝔸, the corresponding successor in 𝔸^{∘} is p_{1}; otherwise 𝔸 and 𝔸^{∘} are identical. Thus, the halting problem for the original abacus 𝔸 is equivalent to determining whether there is a state s with Inst(s) = HALT such that the diagrams D_{𝔖_{1}} and D_{(x_{m},c_{s},y_{n})} represent the same 2-cell in Π_{2}(C_{𝔸^{∘}}).

Theorem 1 Let 𝔸 be an abacus and C_{𝔸} the category described in the previous section. There exist natural numbers n and m and a state s with Inst(s) = HALT such that the diagrams D_{𝔖_{1}} and (x_{m}, c_{s}, y_{n}) are equivalent as 2-cells in Π_{2}(C_{𝔸}) if and only if the abacus is able to reach a halting state.

Proof: Suppose that the abacus is able to reach the halting state s, say Σ^{n}(𝔖_{1}) = (s, m, n) with Inst(s) = HALT. Then it follows immediately from Lemma 1 that diagram D_{𝔖_{1}} is equivalent to diagram (x_{m}, c_{s}, y_{n}).

Conversely, suppose that there exist natural numbers n and m and a state s with Inst(s) = HALT such that the diagrams D_{𝔖_{1}} and (x_{m}, c_{s}, y_{n}) are equivalent. We will first show that in this case diagram D_{H} := (x_{m}, c_{s}, y_{n}) follows from diagram D_{𝔖_{1}}. Let

D_{𝔖_{1}} = D_{0} ∼ ⋯ ∼ D_{i} ∼ ⋯ ∼ D_{2n} = D_{H}  (12)

be a shortest list of direct equivalences which shows that D_{𝔖_{1}} ∼ D_{H} (i.e., this is a list so that no sublist would form a sequence of direct equivalences with the same beginning and ending diagrams). Note that every second diagram in this sequence is vertical. So for each i ∈ {0, …, n}, the diagram D_{2i} is either a successor or a predecessor of D_{2i−2}. Since D_{H} does not have any successors, it follows that D_{H} is the successor of D_{2n−2}. Now let D_{2j} be the last diagram after which this sequence consists only of pairs of direct equivalences which correspond to successors. Then D_{2j−2} would have to be a successor of D_{2j}. However, since successors are unique by Lemma 1, this implies that D_{2j−2} = D_{2j+2} and there exists a shorter list of direct equivalences from D_{𝔖_{1}} to D_{H}. This contradicts our assumption that the list (12) is minimal. We conclude that D_{H} follows from D_{𝔖_{1}}.

Since (12) forms a list of successors, and successors are unique, it follows that D_{2i} = D_{Σ^{i}(𝔖_{1})}. We conclude that the even indexed diagrams in (12) encode the successive internal states of the abacus as it progresses to the halting state.

5 An Alternative Construction

The construction given in the previous section does not only yield a category for which the equivalence relation on Π_{2}(C)_{2} is undecidable, but it shows rather concretely how any computation on an abacus may be translated into an equivalence problem for fences over an appropriate category. (A Java applet illustrating this for the Collatz (3n+1)-problem can be found on cs.stmarys.ca/∼dawson/abacus.html.) In this section, we will examine an alternative construction (first described in [2]) which, while rather less concrete, is shorter and yields undecidable equivalence problems for fences over some familiar categories such as Set and Grp. Our first proposition is probably a “folk theorem”.

Proposition 1 There exists a bipartite graph G = (V_{1}, V_{2}, E) with the following properties:

1. The vertex sets V_{1} and V_{2}, and the set E of edges, are each indexed by a subset of F × ℕ × ℕ for a finite set F; for each of the sets V_{1}, V_{2}, and E, there is a bounded-time algorithm to determine whether (s, x, y) is an index of an element of that set.

2. Given any two vertices of G there is a bounded-time algorithm to determine whether they are connected by an edge; and given any edge and any vertex there is a bounded-time algorithm to determine whether the edge contains the vertex.

3. The problem of determining whether two vertices are in the same component of G is undecidable.

Proof: We construct G from a universal 2-register abacus 𝔸^{∘}, as described above, that halts only in the state (h, 0, 0). One set of vertices V_{1} corresponds to the complete internal states 𝔖 = (s, x, y) of the abacus; the other set, V_{2}, corresponds to the legal transitions [𝔖 → Σ(𝔖)]. (As there is at most one legal transition out of any given state, the first claim follows.) There are edges joining each of the vertices 𝔖 and Σ(𝔖) to the vertex [𝔖 → Σ(𝔖)], and no other edges; the second claim thus follows trivially. Finally, it is evident that determining whether (s, x, y) and (h, 0, 0) are in the same component is equivalent to solving the halting problem for 𝔸^{∘}, from which the third claim follows.

Theorem 2 For any bipartite graph G = (V_{1}, V_{2}, E), there exists a family of fences over Set, all with the same domain and the same codomain and indexed by the vertices of G, such that two vertices are in the same component of G if and only if the corresponding fences are equivalent.

Proof: For i = 1, 2, let p_{i} : E → V_{i} be the function that sends an edge to its endpoint in V_{i}. Consider the class of fences of the form

[figure: ∅; ∅; {∗}; v; V_{1}; ∅; E; p_{1}; V_{2}; V_{2}; p_{2}]  (13)

We note that these are in 1-1 correspondence with the functions v : {∗} → V_{1}, that is, with the elements of V_{1}. The only other fences with this domain and codomain are of the form

[figure: ∅; ∅; {∗}; V_{1}; w; ∅; E; p_{1}; V_{2}; V_{2}; p_{2}]  (14)

where t(∗) is a transition x → y in V_{2}.

If two such fences are directly equivalent, there exists a function u : {∗} → E such that p_{1}u = v and p_{2}u = t. Thus, u(∗) must be of the form (v, t), where t(∗) = (v → w) or (w → v)). Conversely, a fence of form (14) in which ∗ is mapped to the transition (x → y) can only be directly equivalent to a fence of form (13) in which ∗ is mapped to x or y. It follows that two fences of the form (13), in which ∗ is mapped to v and v′ respectively, are equivalent if and only if v and v′ are in the same connected component of G.

The main theorem of this section follows immediately from this:

Theorem 3 The equivalence of fences over Set is undecidable.

Corollary 1 If Set is a full subcategory of C, then the equivalence of fences over C is undecidable.

This corollary covers many familiar categories such as topological spaces, categories, posets, graphs, and several common variants of these (e.g., Hausdorff spaces and directed graphs). Substituting the one-point set for the empty set in the construction lets us extend this result to other categories, such as pointed sets, and pointed topological spaces. A further variation, given in [2], models the word problem for groups to show that the equivalence of fences over Grp is also undecidable.

6 Decidability Results

In the previous two sections we have given examples of categories C for which the equivalence relation on Π_{2}(C)_{2} is undecidable. But this is not a problem for all categories. In this section we discuss two types of categories for which the equivalence relation is decidable. We have already observed one condition on the category C that makes the equality of 2-cells in Π_{2}(C) decidable.

Proposition 2 If the category C is locally finite, equality of 2-cells in Π_{2}(C) can be decided in bounded time.

The construction in the previous section makes heavy use of the fact that the arrows in the category C don’t cancel. If a category C satisfies the condition that for any diagram of the form

[figure: •; f; •; g; h; •; k; •]

we have

kg = kh and gf = hf implies g = h  (15)

the word problem for 2-cells in Π_{2}(C) becomes decidable in bounded time:

Proposition 3 If the category C satisfies the condition (15), equality of 2-cells in the category Π_{2}(C) can be determined in bounded time: maximally (m−1)(n− 1) searches for the existence of a factorization and m + n − 2 checks for equality of two arrows in C are required to determine whether two representatives for a 2-cell (g_{1}, ⋯, g_{n−1}; f_{1}, ⋯, f_{n}) ⇒ (g′_{1}, ⋯, g′_{m−1}; f′_{1}, ⋯, f′_{m}) are equivalent.

Proof:Note that in this condition is equivalent to requiring that every square of the form

[figure: C′; D′; C; D]

has maximally 1 factorization. Consequently, a situation as described in the previous section can not happen: if two representatives have the same index functions, they are only equivalent when they are the same. So the only work that needs to be done in checking whether two 2-cells are equivalent, is to see whether the appropriate factorizations exist to change the index functions of one of them into the index functions of the other, and then one needs to check whether the corresponding arrows in the resulting diagrams are equal. There exist maximally (m − 1)(n − 1) factorizations for a set of diagrams representing one 2-cell, and m + n equality checks are needed.

6.1 Examples

1. If the category C has only monic or only epic maps, C satisfies this condition.

2. If C is a category with only monic maps and D has only epic maps, the category C × D satisfies this condition.

3. For any category C, the subcategory of the category of arrows C^{→} consisting of squares where the top arrow is monic and the bottom is epic (or vice versa) satisfies this condition.

4. The category generated by the following diagram in Set satisfies this condition:

[figure: X; f; h×k; X × Y; g; Y]

where f(x) = (x, y_{0}), h is an isomorphism and k is an isomorphism that keeps y_{0} fixed, y_{0} ∈ Y is a chosen fixed point and g(x, y) = y.

References

[1] R. J. MacG. Dawson, R. Paré, What is a double category like?, Jour. Pure Appl. Alg. 168 (2002), pp. 19-34.

[2] R. J. MacG. Dawson, R. Paré, D. A. Pronk, Undecidability and free adjoints, in Proceedings of the World Multiconference on Systemics, Cybernetics and Informatics 2001, Volume XIV, N. Callaos, F. G. Tinetti, J. M. Champarnaud, J. K. Lee (Eds), International Institute of Informatics and Systemics, Orlando, 2001, pp. 156-161

[3] R. J. MacG. Dawson, R. Paré, D. A. Pronk, Adjoining adjoints, to appear in Adv. in Math.

[4] R. J. MacG. Dawson, R. Paré, D. A. Pronk, Free extensions of double categories, in preparation.

[5] R. J. MacG. Dawson, R. Paré, D. A. Pronk, Free adjoints and spans, in preparation.

[6] P. Gabriel and M. Zisman, Calculus of Fractions and Homotopy Theory, Springer-Verlag, New York, 1967.

[7] J. Lambek, How to program an infinite abacus, Canad. Math. Bull. 4 (1961), pp. 295-302.

[8] M. L. Minsky, Recursive unsolvability of Post’s problem of ‘tag’ and other topics in the theory of Turing machines, Annals of Math. 74 (1961), pp. 437-455.

[9] D. A. Pronk, Etendues and stacks as bicategories of fractions, Comp. Math. 102 (1996), pp. 243-303.

[10] D. Quillen, Homotopical Algebra, LNM 43, Springer Verlag, New York, 1967.

[11] S. Schanuel, R. Street, The free adjunction, Cahier Topologie Géom. Differentielle Catégoriques 27 (1986), pp. 81-83.