Theory and Applications of Categories, Vol. 24, No. 16, 2010, pp. 418–450.

ON THE DUALITY BETWEEN TREES AND DISKS

DAVID OURY

Abstract. A combinatorial category Disk was introduced by André Joyal to play a role in his definition of weak ω-category. He defined the category Θ to be dual to Disks. In the ensuing literature, a more concrete description of Θ was provided. In this paper we provide another proof of the dual equivalence and introduce various categories equivalent to Disk or Θ, each providing a helpful viewpoint.

1. Introduction

André Joyal in order to define weak n-categories introduced Θ which was naturally filtered with the simplicial category Δ being the first term of the filtration. In [Jo97] he defined Θ as the dual of a category Disk of disks. He also suggested a more explicit description of Θ involving the trees of Michael Batanin in [BS00]. Michael Makkai and Marek Zawadowski in [MZ01] and Clemens Berger in [Be02] gave explicit proofs that the two version of Θ are equivalent. In this paper we give a third proof which is a conceptual lifting of the duality between ordinals and intervals. In the process, several categories are introduced, each turning out to be equivalent to Θ or Disk, and so each providing us with useful new perspectives on Joyal’s definitions.

The category Δ_{+} is known as the augmented simplicial category and contains a single object (the empty ordinal) in addition to those of Δ. Primarily, we work with augmented categories which contain a unique trivial object and are more suitable for inductive arguments. Four of these augmented categories have reduced counterparts which are equivalent to the categories Disk or Θ.

In Section 2 we recall the definitions of ordinals and intervals and define functors which witness that they are dual. The section ends with two simple results which are used in the proof of Theorem 6.2. In Section 3 we define augmented categories iI_{+} and iΔ_{+}, inductively built from I_{+} and Δ_{+} (respectively), and prove that they are dual. Their reduced counterparts are denoted iI and iΔ (respectively). In Section 4 we recall the definition of Joyal’s category Disk and demonstrate an equivalence between Disk and iI.

In Section 5.2 we recall Street’s definition of globular cardinal and define restriction and suspension operations on them. In Section 5.9 we define so called ordinal graphs which are inductively defined counterparts to globular cardinals and demonstrate an equivalence between the category of globular cardinals and the category of ordinal graphs. In Section 5.18 we recall the definition of ω-category and define free functors on globular cardinals and on ordinal graphs. We then demonstrate that the free ω-category on a globular cardinal is isomorphic to the free ω-category on the corresponding ordinal graph. The objects of Θ are, by definition, the free ω-categories on globular cardinals. In Section 6 we demonstrate an equivalence between Θ and the inductively defined category iΔ.

The author wishes to thank Macquarie University for financial support (MQRES scholarship and travel grants to Northwestern University May 2009 and University of Adelaide June 2009).

Received by the editors 2010-01-22 and, in revised form, 2010-10-10.

Transmitted by Clemens Berger. Published on 2010-10-12.

2000 Mathematics Subject Classification: 18D05, 18D20, 18D35.

Key words and phrases: delta, disk, duality, globular set, omega-category, theta-category, tree.

\begin{matrix}c \\ ◯ \end{matrix} David Oury, 2010. Permission to copy for private use granted.

In the remaining two sections we provide a more categorical description of the categories Disk and Θ by defining so called labeled trees which satisfy specific requirements relevant to our purposes. Two categories of labeled trees, named tI_{+} and tΔ_{+}, are defined and easily shown to be dual. Their reduced counterparts are shown to be equivalent to the categories Disk and Θ (respectively).

Restriction and suspension operations are defined on labeled trees with the goal of working with them inductively and constructing equivalences between these two categories of labeled trees and their inductively defined counterparts. The proofs that iI_{+} is equivalent to tI_{+} (Proposition 8.2) and that iΔ_{+} is equivalent to tΔ_{+} (Proposition 8.4) are essentially the same; however, we give all the details for clarity.

A disk of dimension ≤ N is defined in [Jo97] as a sequence of length N of bundles of intervals with extra conditions. If we had been dealing with families, rather than those bundles, of intervals we could have made use of known properties of the finite coproduct completion functor F am_{Σ}. In particular, if we have an equivalence A^{op} ≃ B, it lifts to an equivalence F am_{Σ}(A)^{op} ≃ F am_{Π}(B) where F am_{Π} is the finite product completion functor. Our replacements tI and tΔ for Disk and Θ are modifications of F am_{Σ}(I_{+}) and F am_{Π}(Δ_{+}). Instead of finite families we have labeled trees.

2. The ordinal/interval duality

The category Δ_{+}, called the algebraist’s Δ, has objects [n] = {0, .., n} for n in {−1, 0, ...} where [−1] = {} and morphisms which are order preserving functions. The category I_{+} is the sub-category of Δ_{+} whose objects, called intervals, are non-empty ordinals, i.e. [0], [1], [2], …, and whose morphisms preserve the greatest and least elements, i.e. morphism f: [n] → [m] has f(0) = 0 and f(n) = m. Collectively, the greatest and least elements of [n] are its end points.

2.1. Definition. We define contravariant functors

( )^{∨}: I_{+} → Δ_{+}  ( )^{∧}: Δ_{+} → I_{+}
: [n] ↦ [n − 1]  : [n] ↦ [n + 1]
: f ↦ f^{∨}  : g ↦ g^{∧}

on morphisms as follows. Given a morphism f: [n] → [m] of I_{+} there is a function f^{∨}: [m − 1] → [n − 1] in Δ_{+} defined by

f^{−1}{0, 1, …, j} = {0, 1, …, f^{∨}(j)}

where

i ≤ f^{∨}(j) if and only if f(i) ≤ j.  (1)

Given a morphism g: [n − 1] → [m − 1] of Δ_{+} there is a function g^{∧}: [m] → [n] in I_{+} defined by

g^{−1}{i, i + 1, …, m − 1} = {g^{∧}(i), g^{∧}(i) + 1, …, n − 1}

where

g^{∧}(i) ≤ j if and only if i ≤ g(j).  (2)

2.2. Theorem. The functor

( )^{∨}: I_{+}^{op} → Δ_{+}

is an isomorphism of categories with inverse ( )^{∧}: Δ_{+}^{op} → I_{+}.

Proof. Given a morphism f: [n] → [m] of I_{+} and an integer i in [m], then by applying 1 to f(i) ≤ f(i) we obtain i ≤ f^{∨}f(i) and by applying 2 to this inequality obtain (f^{∨})^{∧}(i) ≤ f(i). Hence (f^{∨})^{∧} = f. Likewise, we have (g^{∨})^{∧} = g for a morphism g of Δ_{+}.

2.3. Observation. Let γ: [m] → [n] be an ordinal morphism. The fiber of γ^{∧} over 0 < j ≤ n is

{γ(j − 1) + 1, γ(j − 1) + 2, …, γ(j)}.

This fact is used in Theorem 6.2.

2.4. Observation. If γ: [m] → [n] is an ordinal map with m ≥ 0 then γ^{∧}(i) is an endpoint when either i ≤ min imγ or i > max imγ. This fact is also used in Theorem 6.2.

3. Induction on intervals and ordinals

In this section we introduce inductively defined augmented categories iI_{+} and iΔ_{+} and demonstrate that they are dual.

3.1. Definition. We define the category iI_{+} inductively, with objects filtered by height. The object of height 0 (zero) is the interval [0] and is trivial. An object H of height n is an interval H_{∗} and for each i in H_{∗} an object H(i) of height strictly less than n which is trivial if and only if i is an endpoint of H_{∗}. The object H with H_{∗} = [0] is identified with the trivial object.

For every object H there is a unique morphism H → [0]. Hence [0] is terminal. In addition, there are no non-identity morphisms with codomain [0]. A morphism g: H → K, for H and K with non-zero height, consists of an interval map g: H_{∗} → K_{∗} and for all i in H_{∗} a morphism g(i): H(i) → K(gi).

Define composition using induction as follows. Let f: H → K and g: K → L be composable morphisms. The object map of g ∘ f is the composite of the object maps of g and f. For i ∈ H_{∗} then the composite (g ∘ f)(i): H(i) → L(gfi) is g(fi) ∘ f(i). We have the category iI_{+}. The category iI is the full subcategory of iI_{+} containing the non-trivial objects.

3.2. Definition. We define the category iΔ_{+} inductively, with objects filtered by height. The object of height 0 (zero) is the ordinal [−1] and is trivial. An object K of height n is an ordinal K_{∗} and for each j ∈ (K_{∗})^{∧} an object K(j) of height strictly less than n which is trivial if and only if j is an endpoint of (K_{∗})^{∧}. The object H with H_{∗} = [−1] is identified with the trivial object.

For every object K there is a unique morphism [−1] → K. Hence [−1] is initial. In addition, there are no non-identity morphisms with domain [−1]. A morphism g: H → K, for H and K of non-zero height, consists of an ordinal map g: H_{∗} → K_{∗} and for all j ∈ (K_{∗})^{∧} a morphism g(j): H(g^{∧}j) → K(j).

Define composition using induction as follows. Let f: H → K and g: K → L be composable morphisms. The object map of g ∘ f is the composite of the object maps of g and f. For i ∈ L_{∗} then the composite (g ∘ f)(i): H((g ∘ f)^{∧}i) → L(i) is g(i) ∘ f(g^{∧}i). We have the category iΔ_{+}. The category iΔ is the full subcategory of iΔ_{+} containing the non-trivial objects.

3.3. Definition. We define functors

∨: iI_{+}^{op} → iΔ_{+}

and

∧: iΔ_{+}^{op} → iI_{+}

using the functors ( )^{∨} and ( )^{∧} of the equivalence between ordinals and intervals.

Define ∨ on objects using induction on their height. Send the trivial object [0] of iI_{+} to the trivial object [−1] of iΔ_{+}. Assume ∨ is defined for objects of height n and let H be an object of height n + 1. Define ∨H as ((H_{∗})^{∨}, ∨H(i)).

Define ∨ on morphisms using induction on the height of their codomain. Send each unique morphism of iI_{+} into the trivial object [0] to the corresponding unique morphism of iΔ_{+} out of the trivial object [−1]. Assume ∨ is defined on morphisms with codomain of height n and let g be a morphism of iI_{+} with codomain of height n + 1. Define ∨g as (g^{∨}, ∨g(i)) as each morphism g(i) has codomain of height n.

Similarly, define ∧ on objects (respectively morphisms) using induction on their height (respectively on the height of their domains). Send the trivial object of iΔ_{+} to the trivial object of iI_{+}. Send morphisms of iΔ_{+} out of the trivial object to morphisms of iI_{+} into the trivial object. Let g be a morphism of iΔ_{+}. Define ∧g as (g^{∧}, ∧g(i)).

3.4. Theorem. The functors ∨ and ∧ are mutually inverse isomorphisms.

The proof uses induction and follows directly from the mutually inverse functors of the duality between ordinals and intervals.

3.5. Corollary. The categories iI and iΔ are dual.

4. Equivalence between iI and Disk

In Section 3 we showed that the categories iI and iΔ are dual. Here we demonstrate that the category iI and Joyal’s category Disk are equivalent. To do so we construct the category Disk_{+}, the augmented counterpart to Disk, and show that it is equivalent to the category iI_{+}. We begin by defining forests and trees, and then define operations of restriction and suspension on trees in order to work with them inductively.

4.1. Definition. A forest is a functor A: ω^{op} → Set

⋯  [figure: p_{2}] A_{2}  [figure: p_{1}] A_{1}  [figure: p_{0}] A_{0}.

A tree A is a forest such that A_{0} ≅ {∗}. The vertices of height n are the elements of A_{n}. The unique vertex of height 0 (zero) of a tree is called the root. We often denote the root of a tree A as ∗. We can regard a tree as a directed graph. There is an edge from vertex x to vertex y when p_{n}(x) = y for some n ∈ ℕ. We denote the above forest by (A, p) or A. Define p_{n,m}: A_{n+m} → A_{n} as the composite ∘_{i=n}^{n+m−1}p_{i} which is

A_{n+m}  [figure: p_{n+m−1}]⋯  [figure: p_{n}] A_{n}.

A forest has degree n when p_{n,m} is a bijection for all m ≥ 1 and has finite degree when it has degree n for some n ∈ ℕ.

4.2. Definition. A forest map is a natural transformation of forests and so is a sequence of set maps

[figure: ⋯; B_{2}; q_{2}; ⋯; ⋯; ···; ⋯; A_{2}; p_{2}; A_{2}; B_{2}; f_{2}; B_{2}; B_{1}; q_{1}; A_{2}; B_{2}; f_{2}; A_{2}; A_{1}; p_{1}; A_{1}; B_{1}; f_{1}; B_{1}; B_{0}; q_{0}; A_{1}; B_{1}; f_{1}; A_{1}; A_{0}; p_{0}; A_{0}; B_{0}; f_{0}]

such that the squares commute. This map is denoted by f: (A, p) → (B, q) or f: A → B. A tree map is a natural transformation between trees. We have the category F orest and its full subcategory T ree.

4.3. Definition. We define a restriction operation on trees in order to work with trees as inductive or recursive objects. Let u_{n}: ω → ω be the functor defined by u_{n}(i) = i + n. Let A be a forest and x an element of A_{n}. The restriction of A by x denoted A(x) is the largest subfunctor of A ∘ u_{n}: ω^{op} → Set such that A(x)_{0} = {x}. We sometimes refer to A(x) as a subtree of A.

The restriction of f by x denoted f(x), where f: A → B is a forest map, is the lifting in

[figure: A ∘ u_{n}; B ∘ u_{n}; f·u_{n}; A(x); A ∘ u_{n}; incl; A(x); B(f_{n}x); f(x); B(f_{n}x); B ∘ u_{n}; incl]

of f · u_{n} along the inclusions A(x) → A ∘ u_{n} and B(f_{n}x) → B ∘ u_{n}.

4.4. Definition. Define a suspension functor

su: F orest → T ree

as follows. Given a forest A then its suspension su A is

⋯  [figure: p_{1}] A_{1}  [figure: p_{0}] A_{0}  [figure] {∗}.

Given a map f: A → B of forests then its suspension su f is

[figure: ⋯; B_{1}; ⋯; ⋯; ···; ⋯; A_{1}; A_{1}; B_{1}; f_{1}; B_{1}; B_{0}; A_{1}; B_{1}; f_{1}; A_{1}; A_{0}; A_{0}; B_{0}; f_{0}; B_{0}; {∗}.; A_{0}; B_{0}; f_{0}; A_{0}; {∗}; {∗}; {∗}.]

4.5. Observation. The coproduct of a collection of trees is a forest and its suspension is a tree. The subtrees of the suspension given by vertices of height 1 (one) are isomorphic to the trees of the original collection. We provide the details below.

Let (A(i), p(i)) be a tree with A(i)_{0} = {x_{i}} for each i in a set I. Let A′ = su ∑ A(i) and let copr(i): A(i) → ∑ A(i) be coprojections for each i ∈ I. The fiber of p(i)_{0,n} over x_{i} is A(i)_{n}. The fiber of [∑ p(i)]_{0,n} over x_{i} lying in ∑ A(i)_{0} is A′(x_{i})_{n}. The coproduct in Set requires that the former is sent by the left coprojection of

onto the latter. As the coprojections are monomorphisms then A(i) and A′(x_{i}) are isomorphic by copr(i).

[figure: ∑ A(i)_{n}; ∑ A(i)_{0}.; ∑ p(i)_{0,n}; A(i)_{n}; ∑ A(i)_{n}; copr; A(i)_{n}; A(i)_{0}; p(i)_{0}^{n}; A(i)_{0}; ∑ A(i)_{0}.; copr]

4.6. Definition. A disk as defined by Joyal in [Jo97] is a tree (A, p) of finite degree

1. such that the fibers of p_{n}: A_{n+1} → A_{n} have interval structure (for n ∈ ℕ)

2. with sections d_{0}, d_{1} : A_{n} → A_{n+1} of p_{n} where p_{n}^{∗}(x) = [d_{0}(x), .., d_{1}(x)]

3. such that the equalizer of d_{0}, d_{1} : A_{n} → A_{n+1} is d_{0}(A_{n−1}) ∪ d_{1}(A_{n−1}).

The equalizer of condition 3 is the singular set of A_{n}. All fibers are non-empty by condition 2 and the interval p_{0}^{∗}(x) is strict by condition 3, where x is the single element of A_{0}.

A morphism of disks f: (A, p) → (B, q) as defined by Joyal in [Jo97] as a sequence of set maps f_{n}: A_{n} → B_{n} which commute with the projections p_{n} and q_{n}, respect the order of the interval fibers and preserve the endpoints (first and last elements) of the interval fibers. This defines the category Disk.

In addition, we define the augmented category Disk_{+}. An object of Disk_{+} is a tree of finite degree satisfying 1 and 2 above, but we relax 3 to allow the fiber over the root to be the unique non-strict interval [0]. Hence Disk_{+} contains, in addition to the objects of Disk, trees of degree 0 (zero). These additional objects are terminal. The morphisms of Disk_{+} are defined identically to those of Disk.

4.7. Definition. We define a functor

Φ: Disk_{+} → iI_{+}.

Define Φ on objects using induction on the degree of disks. Send disks of degree 0 (zero) to [0] the trivial object of iI_{+}. Assume that Φ is defined on disks of degree n and let (A, p) be a disk of degree n + 1. We define an object H of iI_{+} from the data of (A, p). Let H_{∗} = p_{0}^{∗}(x), the fiber over the unique element x of A_{0}, and let H(i) = ΦA(i) for each i ∈ H_{∗} where A(i) is the restriction of A by i. Note that H_{∗} is an interval as fibers have interval structure, that A(i) is a disk of degree at most n for each i ∈ H_{∗} and that A(i) is trivial when i is an endpoint by condition 3. Define ΦA as H.

We define Φ on disk morphisms using induction on the degree of their codomain. The disks of degree 0 (zero) are terminal objects. As Φ preserves the terminal object then disk morphisms with codomain of degree 0 (zero) are sent to the unique morphism into the trivial object of iI_{+}. Assume Φ is defined on morphisms with codomain of degree n and let f: (A, p) → (B, q) be a disk morphism with codomain of degree n+1. We define a morphism g of iI_{+} from the data of f. Let g = f_{1} which is an interval morphism as f preserves order and endpoints. Let g(i) = Φf(i) where f(i) is the restriction of f by i for each i ∈ A_{1}. Define Φf as g.

4.8. Theorem. The category Disk_{+} is equivalent to the category iI_{+} by

Φ: Disk_{+} → iI_{+}

which is surjective on objects.

Proof. Surjective. We show that Φ is surjective on objects using induction on the height of objects of iI_{+}. The trivial disks are sent to the trivial object [0] and so Φ is surjective on objects of height 0 (zero). Assume Φ is surjective on objects of height n and let H be an object of height n + 1. By induction there exists a disk A(i) with ΦA(i) = H(i) for each i in H_{∗}. Let A′ = su ∑ A(i) where the coproduct is indexed over the elements of H_{∗}. Give the fiber over ∗ an interval structure from that of H_{∗}. For each element x in A′_{n} with n > 0 give the fiber over x an interval structure by pulling back along the coprojections. By Observation 4.5 then A′(i) ≅ A(i). Define ΦA′ as H′. As Φ is constant on isomorphism classes then we have ΦA′(i) = ΦA(i), equivalently H′(i) = H(i). By construction H′_{∗} = (p′_{0})^{∗}(∗) is isomorphic to H_{∗} and is in fact identically H_{∗} as Δ is skeletal. Hence Φ is surjective on objects.

Faithful. We show that Φ is faithful using induction on the height of the codomain of morphisms of iI_{+}. As Φ reflects the terminal object it is faithful on morphisms with codomain of height 0 (zero). Assume that Φ is faithful on morphisms with codomain of height n and let f, f′: (A, p) → (B, q) be parallel disk morphisms such that Φf = Φf′ has codomain of height n + 1. Then, by induction, f(i) = f′(i) for each i ∈ A_{1}. As f(i) and f′(i) are defined by liftings on inclusions which are jointly surjective it follows that f = f′ and Φ is faithful.

Full. We show Φ is full using induction on the height of the codomain of morphisms of iI_{+}. As Φ preserves the terminal object it is full on morphisms of height 0 (zero). Assume that Φ is full on morphisms with codomain of height n and let g: Φ(A, p) → Φ(B, q) have codomain of height n+1. We have an interval morphism g and a morphism g(i) of iI_{+} for each i ∈ Φ(A, p). By induction there exist disk morphisms f(i): A(i) → B(gi) such that Φf(i) = g(i). In the following diagram

[figure: A(i)_{n}; A_{n+1}; incl; A(i)_{n}; ∑ A(i)_{n}; copr; A(i)_{n}; B(gi)_{n}; f(i)_{n}; B(gi)_{n}; ∑ B(gi)_{n}; copr; B(gi)_{n}; B_{n+1}; incl; A_{n+1}; ∑ A(i)_{n}; ∑ A(i)_{n}; ∑ B(gi)_{n}; ∑ B(gi)_{n}; B_{n+1}]

the left triangle commutes as the inclusions into A_{n+1} are jointly surjective and the other regions commute by coproduct. Define f′ by setting f′_{n+1} to the lower composite for each n ∈ ℕ. Then f′(i) is (by definition) the upper horizontal morphism and so f(i) = f′(i). The inclusions and commutativity of the diagram imply that f_{1} as defined is identically g as required. Hence Φf′ = g.

4.9. Corollary. The category Disk is equivalent to the category iI.

5. Objects of Θ

From [BS00], an object of Θ is defined as the free ω-category on a non-empty globular cardinal. We define the augmented counterpart to Θ, named Θ_{+}, as containing objects which are free ω-categories on possibly empty globular cardinals.

In Section 5.2 we recall the definition of globular cardinal and define restriction and suspension operations on them. In Section 5.9 we define ordinal graphs, which are inductively defined counterparts of globular cardinals. An equivalence is demonstrated between the categories of globular cardinals and ordinal graphs. The section closes with the definition of a map that sends objects of iΔ_{+} to ordinal graphs. In Section 5.18 we recall the definition of ω-category and adapt Michael Batanin’s construction of the free ω-category on a globular set. In addition we define the free ω-category on an ordinal graph and show that it is isomorphic to the free ω-category of the corresponding globular cardinal.

In this and following sections we will use the following shorthand with the intention of providing an uncluttered presentation. In the sequel often indices are given over all elements of a known finite linearly ordered set except the first. In some cases the previous element to the index is also used. Our shorthand is designed to simplify the presentation in these instances.

5.1. Notation. Let F inOrd_{+} denote the full subcategory of Ord with objects finite linearly ordered sets and let F inOrd denote the full subcategory containing the non-empty finite linearly ordered sets. Define

( ) \f : Ob F inOrd → Ob F inOrd_{+}
: {x_{0}, x_{1}, …, x_{p}} ↦ {x_{1}, x_{2}, …, x_{p}}.

which returns its argument without the first element. The “\f” is intended to indicate that the first element is removed. The operator p( ) takes arguments which are elements of finite linearly ordered sets with cardinality at least 2 (two) and returns their predecessor. For example given a finite linearly ordered set I = {x_{0}, x_{1}, …, x_{p}} then p(x_{i}) = x_{i−1} for all x_{i} ∈ I \f.

5.2. Globular cardinals. Globular cardinals were defined by Ross Street in [St00] Section 1. We collect here the definitions and notation related to this concept, as relevant for our purposes. In addition, we define restriction and suspension operations.

5.3. Definition. We begin by quoting the definition of globular object from [St00]. Let G be the category with objects the natural numbers and non-identity arrows

σ_{m}, τ_{m}: m → n for m < n

such that commutes for all k < m < n and all α, β ∈ {σ, τ}. A globular object in C is a functor X: G^{op} → C. A morphism of globular objects is a natural transformation between globular objects. Hence a globular set is a pair of sequences of set maps

[figure: k; n; β_{k}; k; m; β_{k}; m; n; α_{k}]

⋯  [figure: s_{2}; t_{2}] X_{2}  [figure: s_{1}; t_{1}] X_{1}  [figure: s_{0}; t_{0}] X_{0}

such that s_{n}s_{n+1} = s_{n}t_{n+1} and t_{n}s_{n+1} = t_{n}t_{n+1} for all n ∈ ℕ. The maps of the sequence s are source maps and the maps of the sequence t are target maps. The set X_{n} contains the n-vertices of X.

A globular set X has dimension n when n is the smallest integer such that X_{m} is empty for all m > n. The empty globular set has dimension -1 (minus one). A globular set has finite dimension when it has dimension n for some n ≥ −1.

A morphism f: X → Y of globular sets is a sequence f of set maps

[figure: ⋯; Y_{2}; s; ⋯; ⋯; ···; ⋯; X_{2}; s; X_{2}; Y_{2}; f_{2}; Y_{2}; Y_{1}; s; X_{2}; Y_{2}; f_{2}; X_{2}; X_{1}; s; X_{1}; Y_{1}; f_{1}; Y_{1}; Y_{0}; s; X_{1}; Y_{1}; f_{1}; X_{1}; X_{0}; s; X_{0}; Y_{0}; f_{0}; ⋯; Y_{2}; t; ⋯; ⋯; ···; ⋯; X_{2}; t; X_{2}; Y_{2}; f_{2}; Y_{2}; Y_{1}; t; X_{2}; Y_{2}; f_{2}; X_{2}; X_{1}; t; X_{1}; Y_{1}; f_{1}; Y_{1}; Y_{0}; t; X_{1}; Y_{1}; f_{1}; X_{1}; X_{0}; t; X_{0}; Y_{0}; f_{0}]

which commute with the source and target maps. We have the category of globular sets. A globular set X has a partial order ◀ generated from the relation

x ≺ y when x = s(y)
or  y = t(x)

for x ∈ X_{n} and either y ∈ X_{n+1} or y ∈ X_{n−1} (respectively). When x ◀ y there exists a (possibly trivial) sequence x_{0}, ..., x_{n} of vertices in X with x_{0} = x, x_{n} = y and x_{i−1} ≺ x_{i} for all i ∈ {1, .., n}. A globular cardinal is a globular set with a finite set of vertices and where the order given above is linear. We have GlobCard the category of globular cardinals.

5.4. Definition. Vertices x and y in a globular cardinal X are consecutive in Y (with Y a subset of X) when {z ∈ Y : x ◀ z ◀ y} = {x, y}.

5.5. Observation. Let f: X → Y be a morphism of globular cardinals and let x and y be consecutive in X_{n}. There exists an element z either in X_{n+1} or X_{n−1} such that s(z) = x and t(z) = y or such that s(y) = z and t(x) = z. In either case f_{n}x and f_{n}y are consecutive in Y_{n} as f preserves source and target. Hence f_{n} is injective and the image of f_{n} is an interval.

5.6. Definition. A map g: A → B of finite linearly ordered sets that is injective and whose image is an interval is called incremental.

5.7. Definition. We define a restriction operation on globular cardinals. Given two consecutive n-vertices of a globular cardinal X the operation returns the globular cardinal which we might call the hom-set determined by the two n-vertices. Let u_{n}: G → G be the functor defined by u_{n}(i) = i + n. Let X be a globular cardinal with y and z consecutive vertices of X_{n}. Define the restriction of X by y, z denoted X(y, z) as the largest subfunctor of X ∘ u_{n+1} such that y ◀ x ◀ z for all x ∈ X(y, z). Notice that X(σ)x = y and X(τ)x = z for all x ∈ X(y, z)_{0} ⊆ X_{n+1}.

We have an inclusion ι_{y,z}: X(y, z) → X∘u_{n+1} of functors for every pair of consecutive vertices y, z ∈ X_{n}. The restriction of f: X → Y by y, z denoted f(y, z) is the lifting in

[figure: X ∘ u_{n+1}; Y ∘ u_{n+1}; f·u_{n+1}; X(y, z); X ∘ u_{n+1}; X(y, z); Y (f_{n} y, f_{n} z); f(y,z); Y (f_{n} y, f_{n} z); Y ∘ u_{n+1}]

of f · u_{n+1} along the inclusions ι_{y,z} and ι_{f_{n}y,f_{n}z}.

5.8. Definition. We define a suspension operation on collections of globular cardinals. Let A = {x_{0}, x_{1}, …, x_{p}} be a finite linearly ordered set and let X(i) be a globular cardinal for each i ∈ A \f. We refer to A and the X(i) collectively as a matched set below. Define the suspension of X(i) over A denoted su(X(i), A) as follows. Define set maps s(i), t(i): X(i)_{0} → A by s(i)(y) = pi and t(i)(y) = i for y ∈ X(i)_{0} and for each i ∈ A \f. Then the suspension su(X(i), A) is

⋯ [figure: ∑ s_{1}(i); ∑ t_{1}(i)]∑ X(i)_{1}  [figure: ∑ s_{0}(i); ∑ t_{0}(i)]∑ X(i)_{0}  [figure: ∑ s(i); ∑ t(i)] A

where the coproducts are indexed over all i ∈ A \f. Notice that s(i)s_{0}(i) = s(i)t_{0}(i) as s(i) is constant. In addition as the required identities hold for each X(i) then the universal property of coproduct in Set implies that

∑ s(i)_{n} ∑ s(i)_{n+1} = ∑ s(i)_{n} ∑ t(i)_{n+1}

for n > 0. Likewise for the target maps. Hence the source and target identities required of globular cardinals are satisfied by the suspension. The linear order given by the source and target maps is

{x_{0}, X(1), x_{1}, X(2), x_{2}, …, x_{n−1}, X(n), x_{n}}.

Hence su(X(i), A) is a globular cardinal.

Similarly, we define a suspension operation on collections of morphisms of globular cardinals. Let X(i), A and Y (j), B be matched sets and let X and Y be their suspensions as defined above. Let f: A → B be an incremental morphism of ordered sets and let f(i): X(i) → Y (fi) be a morphism of globular cardinals for each i ∈ A \f. Define the suspension of f(i) over f denoted su(f(i), f) as

[figure: ⋯; Y_{2}; ⋯; ⋯; ···; ⋯; X_{2}; X_{2}; Y_{2}; ∑ f(i)_{1}; Y_{2}; Y_{1}; X_{2}; Y_{2}; ∑ f(i)_{1}; X_{2}; X_{1}; X_{1}; Y_{1}; ∑ f(i)_{0}; Y_{1}; B; X_{1}; Y_{1}; ∑ f(i)_{0}; X_{1}; A; A; B; f; ⋯; Y_{2}; ⋯; ⋯; ···; ⋯; X_{2}; X_{2}; Y_{2}; ∑ f(i)_{1}; Y_{2}; Y_{1}; X_{2}; Y_{2}; ∑ f(i)_{1}; X_{2}; X_{1}; X_{1}; Y_{1}; ∑ f(i)_{0}; Y_{1}; B; X_{1}; Y_{1}; ∑ f(i)_{0}; X_{1}; A; A; B; f]

where the coproducts are indexed over A \f. The squares commute by universal property of coproduct in Set and the suspension su(f(i), f) is a morphism of globular cardinals.

5.9. Ordinal graphs. The purpose of this section is to define the concept of an enriched graph called a V-graph to allow an inductive definition equivalent to that of globular cardinals. An equivalence is demonstrated between the categories of globular cardinals and ordinal graphs. The section closes with the definition of a map that sends objects of iΔ_{+} to ordinal graphs.

5.10. Definition. A V-graph G, for a category V, consists of a set of vertices G_{∗} and an edge-object G(x, y) in Ob V for every pair of vertices x, y. A morphism of V-graphs f: G → H is a set map f: G_{∗} → H_{∗} and for every edge-object G(x, y) of G a morphism

f(x, y): G(x, y) → H(fx, fy)

of V. We have the category V-Gph of V-graphs, graphs enriched over V.

5.11. Definition. Suppose V has initial object 0 and U is a subset of Ob V containing 0. A U ordinal V-graph G consists of a finite linearly ordered set G_{∗}, objects G(x, y) in U of V for all pairs x, y in G_{∗}, and such that G(x, y) ≠ 0 if and only if y is the successor of x. We have the category (U, V)-Gph_{ord} of U ordinal V-graphs. Notice that the object maps are incremental.

5.12. Definition. We define two categories Graph_{ℕ} and OGraph of enriched graphs. Let Graph_{0} denote the category {∅}-Gph and let Graph_{n+1} denote the category Graph_{n}-Gph for each n ∈ ℕ. Define Graph_{ℕ} as the colimit of the diagram

Graph_{0} → Graph_{1} → ⋯ → Graph_{n} → ⋯

of inclusions. The empty graph ∅ has dimension -1 (minus one). A graph of Graph_{n} has dimension n.

We define OGraph the category of ordinal graphs, a subcategory of Graph_{ℕ}, which we demonstrate in Theorem 5.15 is equivalent to the category of globular cardinals. Let OGraph_{0} denote the category (∅, ∅)-Gph_{ord} and let OGraph_{n+1} denote the category (OGraph_{n}, Graph_{n})-Gph for n ∈ ℕ. Define OGraph as the colimit of the diagram

OGraph_{0} → OGraph_{1} → ⋯ → OGraph_{n} → ⋯

of inclusions.

5.13. Definition. We define a functor

Γ: GlobCard → OGraph

using induction on the dimension of globular cardinals. Let X be a globular cardinal of dimension -1 (minus one). Then X is empty and so an initial object. Define ΓX as the empty ordinal graph. Assume Γ is defined on globular cardinals of dimension n and let X have dimension n + 1. Define ΓX as G where G_{∗} = X_{0} and G(px, x) = ΓX(px, x) for each x ∈ X_{0} \f.

Define Γ on morphisms using induction on the dimension of their domain. Let f: X → Y be a morphism with domain of dimension -1 (minus one). Define Γf as ∅ → ΓY the unique morphism out of the empty graph. Assume Γ is defined on morphisms with domain of dimension n and let f: X → Y be a morphism with domain of dimension n + 1. Define Γf as g with object map f_{0} : X_{0} → Y_{0} and g(px, x) = Γf(px, x) for each x ∈ X_{0} \f.

5.14. Definition. We define a functor

Γ′: OGraph → GlobCard

using induction on the dimension of ordinal graphs. Let G be an ordinal graph of dimension -1 (minus one). Then G is empty and so is initial. Define Γ′G as the initial globular cardinal. Assume Γ′ is defined on ordinal graphs of dimension n and let G have dimension n + 1. Define Γ′G as su(Γ′G(px, x), G_{∗}) where G(px, x) is the collection of non-empty ordinal graphs of G indexed by x ∈ G_{∗} \f.

Define Γ′ on morphisms using induction on the dimension of their domain. Let g: G → H be a morphism with domain of dimension -1 (minus one). Define Γ′g as ∅ → Γ′H the unique morphism out of the empty ordinal graph. Assume Γ′ is defined on morphisms with domain of dimension n and let g be a morphism with domain of dimension n + 1. Define Γ′g as the suspension su(Γ′g(px, x), g) where g(px, x) is the collection of morphisms of ordinal graphs of g indexed by x ∈ G_{∗} \f.

5.15. Theorem. The category GlobCard is equivalent to the category OGraph by

Γ: GlobCard → OGraph

and its equivalence inverse Γ′.

Proof. We construct natural isomorphisms η: Id ⇒ Γ′Γ and ϵ: ΓΓ′ ⇒ Id using induction on the dimension of globular cardinals (respectively ordinal graphs). Let X be a globular cardinal of dimension -1 (minus one). Then X and Γ′ΓX are both empty globular cardinals. Assume η is a natural isomorphism for globular cardinals of dimension n and let X have dimension n + 1. Let X′ = Γ′ΓX which is su(Γ′ΓX(px, x), X_{0}). We construct an isomorphism f: X → Γ′ΓX. Define f_{0} as Id_{X_{0}} and f_{n} as the unique map out of the coproduct in

[figure: ∑ Γ′ΓX(px, x)_{n}; X_{n+1}; Γ′ΓX(px, x)_{n}; ∑ Γ′ΓX(px, x)_{n}; copr; Γ′ΓX(px, x)_{n}; X(px, x)_{n}; ≅; X(px, x)_{n}; X_{n+1}; incl]

for each n > 0. Then f is a bijection as the coprojections are monomorphisms and the composites with the inclusions are monomorphisms and are jointly epi. Naturality arises from the universal property of coproduct.

Let G be an ordinal graph of dimension -1 (minus one). Then G and ΓΓ′G are both empty ordinal graphs. Assume ϵ is a natural isomorphism for ordinal graphs of dimension n and let G have dimension n + 1. Define X as

Γ′G = su(Γ′G(x_{i−1}, x_{i}), G_{∗}).

The globular cardinal X(px, x) is the largest subfunctor of X satisfying the requirements of Definition 5.7. The coprojection

Γ′G(px, x) → ∑ Γ′G(px, x)

is also such a functor and so is identically X(px, x). Then G′ = ΓX = ΓΓ′G has G′_{∗} = G_{∗} and G′(px, x) = ΓΓ′G(px, x) which by induction is naturally isomorphic to G(px, x). Hence ϵ is a natural isomorphism since for any ordinal graph G then ϵ_{G} consists of an identity and components which are natural isomorphisms.

5.16. Definition. We define a map

Υ: Ob iΔ_{+} → Ob OGraph

by induction on the height of objects of iΔ_{+}. Send the initial object [−1] to the empty ordinal graph. Assume Υ is defined on objects of height n and let H have height n+1. Let ΥH be the ordinal graph G with G_{∗} = H_{∗} and

G(i − 1, i) = ΥH(i)

for i which are not endpoints of (H_{∗})^{∧}. Recall H(i) is trivial when i is an endpoint of (H_{∗})^{∧}. Notice that objects of iΔ_{+} of height n are sent to ordinal graphs of dimension n − 1.

Define Υ′: Ob OGraph → Ob iΔ_{+} by induction on the dimension of ordinal graphs. Send the initial ordinal graph to the trivial object [−1]. Assume Υ′ is defined on ordinal graphs of dimension n and let G have dimension n + 1. Suppose G_{∗} = {x_{0}, x_{1}, …, x_{p}}. Define Υ′G as the object H with H_{∗} = [p], with H(0) and H(p + 1) the trivial object of iΔ_{+} and with H(i) = Υ′G(x_{i−1}, x_{i})) for each x ∈ [p] \f. Notice that the ordinal graphs of dimension n are sent to objects of iΔ_{+} of height n + 1.

5.17. Theorem. The object map Υ is surjective.

Proof. Clearly Υ is surjective on ordinal graphs of dimension -1 (minus one). Assume that Υ is surjective on ordinal graphs of dimension n, let G be an ordinal graph of dimension n + 1 and let G′ = ΥΥ′G. Then G_{∗} = G_{∗}′ and, by induction, for each i ∈ G_{∗} \f we have G(pi, i) = G′(pi, i). Hence G = G′ and Υ is surjective.

5.18. ω-categories. We start by recalling the definition of ω-category. Definition 5.21 is adapted from Michael Batanin’s construction in [Ba98] of the free ω-category on a globular set. In addition we define the free ω-category on an ordinal graph and show that it is isomorphic to the free ω-category on the corresponding globular cardinal.

5.19. Definition. A 1-category is an ordinary category and a 0-category is a discrete 1-category. An n-category is a category enriched over (n − 1)-categories for n > 0. Then ωCat, the category of ω-categories, is the colimit of the diagram

0-Cat → 1-Cat → 2-Cat → ⋯ → n-Cat → ⋯

of inclusions. The initial ω-category has dimension -1 (minus one). The ω-categories of n-Cat have dimension n.

5.20. Definition. Let Y be a globular cardinal with x and y consecutive n-vertices. Define Y [x, y] as the largest subfunctor of Y such that Y [x, y]_{n} = {x, y}. We have the inclusion ι[x, y]: Y [x, y] → Y. Let γ be a morphism of globular cardinals. Define γ[x, y] as the composite γ ∘ ι[x, y].

5.21. Definition. We define a functor

𝔉: GlobCard → ωCat.

Let X be a globular cardinal. The n-cells of 𝔉X are isomorphism classes of objects of GlobCard/X which are globular morphisms γ: Y → X where Y has dimension n.

Let Y be a globular cardinal. We define the m-source of Y denoted s_{m} Y (respectively the m-target of Y denoted t_{m} Y) for m ∈ ℕ. Define s_{0} Y (respectively t_{0} Y) as the smallest subfunctor of Y containing the least (respectively greatest) element of Y. For m ≥ 1 define s_{m} Y (respectively t_{m} Y) as the smallest subfunctor of Y containing Y_{ℓ} for all ℓ < m and containing the least (respectively greatest) element of Y [py, y]_{m} for all y in Y_{m−1} \f. Given an n-cell γ (representing an isomorphism class) then dom_{m} (γ) is (the isomorphism class of) the composite

s_{m} Y  [figure: incl] Y  [figure: γ] X.

Likewise for cod_{n} (γ).

Composition in 𝔉X is given by pushout. Let α: Y → X and β: Z → X be n-cells with dom_{m} (β) = cod_{m} (α). There is a unique isomorphism δ: s_{m} Z → t_{m} Y such that dom_{m} β = cod_{m} α ∘ δ where composition and equality is of globular morphisms. Define β ∘^{m} α as the unique morphism in

[figure: s_{m} Z; Z; incl; s_{m} Z; Y; δ; Z; P; Y; P; Y; X; α; Z; X; β; P; X]

out of the pushout P which is defined as Z\s_{m} Z+Y. Specifically, we have P_{ℓ} = Y_{ℓ} = Z_{ℓ} for ℓ < m, P_{m} = Z_{m}\(s_{m} Z)_{m} + Y_{m} and P_{ℓ} = Y_{ℓ} + Z_{ℓ} for ℓ > m where the + operation is the ordered union of linearly ordered sets. Let ∘ denote 0-composition.

An n-cell γ is indecomposable when the cardinality of Y [py, y]_{m} is 2 (two) for all m < n and is 1 (one) when m = n. An n-cell γ is 0-indecomposable when the cardinality of Y_{0} is less than or equal to 2 (two). An n-cell γ is m-indecomposable (for m ≥ 1) when the cardinality of Y [py, y]_{m} is less than or equal to 2 (two) for all y ∈ Y_{m−1} \f.

Observations 5.22, 5.23 and 5.24 are referred to in Definition 5.30.

5.22. Observation. We identify an arbitrary n-cell of 𝔉X with a canonical 0-compos-ition of 0-indecomposable n-cells. Let γ: Y → X be an n-cell where Y_{0} is {y_{0}, y_{1}, …, y_{p}}. We have

γ = γ[y_{p−1}, y_{p}] ∘ … ∘ γ[y_{0}, y_{1}].

We denote this composite as ∘_{y}γ[py, y]. and understand that y is an index over Y_{0} \f.

5.23. Observation. We show (dom_{m} γ)(py, y) = dom_{m−1} γ(py, y) for an n-cell γ of 𝔉X where m < n and y ∈ Y_{0} \f. The lifting in

[figure: s_{m} Y ∘ u_{1}; Y ∘ u_{1}; (s_{m} Y)(py, y); s_{m} Y ∘ u_{1}; (s_{m} Y)(py, y); Y (py, y); Y (py, y); Y ∘ u_{1}; Y ∘ u_{1}; X ∘ u_{1}; γ·u_{1}; Y (py, y); Y ∘ u_{1}; Y (py, y); X(pγy, γy); γ(py,y); X(pγy, γy); X ∘ u_{1}]

along the vertical arrows is (dom_{m} γ)(py, y) where the inclusions are described in Definition 5.7. The composite

s_{m−1} Y (py, y) [figure: incl] Y (py, y) [figure: γ(py,y)] X(py, y)

is dom_{m−1} γ(py, y). It remains to show that (s_{m} Y) (py, y) and s_{m−1} (Y (py, y)) are identical. Let x be an element of (s_{m} Y) (py, y). Then py ◀ x ◀ y and either

x ∈ Y_{ℓ} for 1 < ℓ < m

434  DAVID OURY

or

x is the least element of Y [pz, z]_{m} for some z ∈ Y_{m−1} \f.

Given the first condition then they can be rewritten as

x ∈ Y (py, y)_{ℓ} for ℓ < m − 1

or

x is the least element of Y (py, y)[pz, z]_{ℓ} for some z ∈ Y (py, y)_{m−2} \f.

Jointly these rewritten conditions state that x is in s_{m−1} (Y (py, y)). The converse is also true. We have that (dom_{m} γ)(py, y) and dom_{m−1} γ(py, y) are identical.

5.24. Observation. We show (β ∘^{m} α)(py, y) = β(py, y) ∘^{m−1} α(py, y) for m-composable n-cells α and β of 𝔉X where m < n and y ∈ Y_{0} \f. Let α: Y → X and β: Z → X be m-composable n-cells. Their composition β ∘^{m} α is given the unique morphism out of the pushout in

[figure: s_{m} Z; Z; incl; s_{m} Z; Y; δ; Z; P; Y; P; Y; X; α; Z; X; β; P; X]

where P = Z\s_{m} Z + Y. Let y be an element of P. By Observation 5.23 then (s_{m} Z)(py, y) and s_{m−1} Z(py, y) are identical. Note that Z(py, y)\(s_{m} Z)(py, y) is Z(py, y)\s_{m} Z and further that Z(py, y)\s_{m} Z + Y (py, y) is (Z\s_{m} Z + Y)(py, y). Then P (py, y) is the pushout of

[figure: s_{m−1} Z(py, y); Z(py, y); s_{m−1} Z(py, y); Y (py, y); Z(py, y); P (py, y); Y (py, y); P (py, y); Y (py, y); X(py, y); α(py,y); Z(py, y); X(py, y); β(py,y); P (py, y); X(py, y)]

which is the lifting of the above diagram determined by the element y ∈ P. As all horizontal and vertical maps above are monomorphisms we avoid unnecessary notation by labeling all restrictions with (py, y). Hence the unique map of the second pushout is (β ∘^{m} α)(py, y) from the lifting and β(py, y) ∘^{m} α(py, y) by definition.

5.25. Definition. We define a functor

𝔉: Graph_{ℕ} → ωCat

inductively on the dimension of ordinal graphs. Let G be the enriched graph of dimension -1 (minus one) which is the empty graph. Define 𝔉G as the empty ω-category. Assume 𝔉 is defined on enriched graphs of dimension n and let G have dimension n + 1. Define the object set of 𝔉G as the object set of G. Its hom-sets are defined by induction for distinct objects x and y as

(𝔉G) (x, y) = ∑_{x_{0},...,x_{n}∈G_{∗}} 𝔉 (G (x_{n−1}, x_{n})) × ... × 𝔉 (G (x_{0}, x_{1}))

where x = x_{0} and y = x_{n}. For all x ∈ G_{∗} then (𝔉G)(x, x) is defined as

C_{T} + ∑_{x_{0},...,x_{n}∈G_{∗}} 𝔉(G(x_{n−1}, x_{n})) × ... × 𝔉(G(x_{0}, x_{1}))

where C_{T} is the terminal ω-category.

Define 𝔉 on morphisms as follows. Let g: G → H be a morphism of enriched graphs with domain of dimension -1 (minus one). Define 𝔉g as the unique ω-functor ∅ → 𝔉H. Assume 𝔉 is defined for morphisms with domain of dimension n and let g: G → H be a morphism of enriched graphs with domain of dimension n + 1. Let x_{0}, x_{1}, …, x_{p} denote the objects of G. The morphisms of hom-objects are defined for distinct objects x and y as

(𝔉g)_{x,y} = ∑_{x_{0},...,x_{n}∈G_{∗}} 𝔉 (g (x_{n−1}, x_{n})) × ... × 𝔉 (g (x_{0}, x_{1}))

where x = x_{0} and y = x_{n}. For all x ∈ G_{∗} then (𝔉g)_{x,x} is defined as

g_{T} + ∑_{x_{0},...,x_{n}∈G_{∗}} 𝔉(g(x_{n−1}, x_{n})) × ... × 𝔉(g(x_{0}, x_{1}))

where g_{T} : C_{T} → C_{T} .

5.26. Definition. We define a forgetful functor

𝔘: ωCat → Graph_{ℕ}

using induction on the dimension of ω-categories. Let C be the ω-category of dimension -1 (minus one) which is the empty ω-category. Define 𝔘C as the empty ordinal graph. Assume 𝔘 is defined on ω-categories of dimension n and let C have dimension n + 1. Define 𝔘C as the ordinal graph with object set Ob C and with edge-object (𝔘C)(x, y) = 𝔘(C(x, y)) determined by induction for each pair of objects x and y.

Define 𝔘 on morphisms as follows. Let F: C → A be an ω-functor with domain of dimension -1 (minus one). Define 𝔘F as the unique morphism ∅ → 𝔘A of enriched graphs. Assume 𝔘 is defined on ω-functors with domain of dimension n and let F have domain of dimension n + 1. Define 𝔘F as the ordinal graph with object set morphism identical with that of F and with edge-object morphism (𝔘F)(x, y) = 𝔘(F(x, y)) determined by induction for each pair of objects x and y.

5.27. Theorem. The functor 𝔉 is left adjoint to 𝔘.

Proof. We define, given an ordinal graph G and an ω-category C, a bijection

ϕ: Graph_{ℕ}(G, 𝔘C) → ωCat(𝔉G, C)

using induction on the dimension of ordinal graphs. Let g: G → 𝔘C be a morphism of ordinal graphs with domain of dimension -1 (minus one). Define ϕg as the unique ω-functor 𝔉G → C. Assume ϕ is defined and is a bijection on morphisms of ordinal graphs with domain of dimension n and let g be such a morphism with domain of dimension n + 1. Define ϕg = F: 𝔉G → C as follows. The object morphism of F is that of g. Define, using the induction assumption, the morphism F(x, y) of hom-sets as ϕg(x, y) for each pair of objects x, y of G.

Suppose that g and g′ are morphisms of ordinal graphs such that ϕg = ϕg′. Then the object maps of g and g′ are identical and by the induction assumption the morphisms of edge-objects are identical. Hence ϕ is injective.

Let F: 𝔉G → C be an ω-functor. Define a morphism g of ordinal graphs as follows. The object map of g is that of F. The morphisms of edge-objects are defined using the induction assumption. Hence ϕ is surjective and 𝔉 is left adjoint to 𝔘.

5.28. Observation. In the sequel we restrict 𝔉 of Definition 5.25 to the category of ordinal graphs. Recall that an ordinal graph G has G(x, y) non-empty if and only if y is the successor of x. Let G be an ordinal graph. For all objects x of G we have the hom-object (𝔉G) (x, x) = C_{T}. For every pair x, y of distinct objects then

(𝔉G)_{x,y} = 𝔉 (G (x_{n−1}, x_{n})) × ... × 𝔉 (G (x_{0}, x_{1})) .

Given a morphism g: G → H we have

(𝔉g)_{x,y} = 𝔉 (g (x_{n−1}, x_{n})) × ... × 𝔉 (g (x_{0}, x_{1}))

where x = x_{0}, y = x_{n} and x_{i} is the successor of x_{i−1} for i = 1, .., n.

5.29. Observation. We describe here the n-cells, domain, codomain and composition operations of 𝔉G for an ordinal graph G with objects x_{0}, x_{1}, …, x_{p}. A 0-cell of 𝔉G is an object of G. An n-cell y of 𝔉G is a sequence (y_{i})_{i=h+1}^{k} of (n−1)-cells, one from each factor, of the product ∏_{j=h+1}^{k} 𝔉 (G(x_{i−1}, x_{i})) for h ≤ k in {0, 1, …, p}. The 0-domain of y is x_{h} and the 0-codomain of y is x_{k}. Composition (0-composition) is denoted by ∘ and is given by concatenation of sequences. Hence every n-cell is identified with a unique 0-composition.

The m-domain and m-codomain of an n-cell y denoted dom_{m} y and cod_{m} y are the 0-compositions ∘_{i=h+1}^{k}dom_{m−1} y_{i} and ∘_{i=h+1}^{k}cod_{m−1} y_{i} (respectively) for m < n. The m-composition of n-cells y and z is defined

(y_{i})_{i=h+1}^{k} ∘^{m} (z_{i})_{i=h+1}^{k} = ∘_{i=h+1}^{k} (y_{i} ∘^{m−1} z_{i})

for m < n where the (m − 1)-composition is in 𝔉G(x_{i−1}, x_{i}).

5.30. Definition. We have two free functors both denoted 𝔉, one for globular cardinals and one for ordinal graphs and the functor Γ: GlobCard → OGraph of Definition 5.13. Let X be a globular cardinal. We define an ω-functor

L : 𝔉X → 𝔉ΓX

using induction on the dimension of globular cardinals.

Let X be a globular cardinal of dimension -1 (minus one). Then 𝔉X and 𝔉ΓX are both the empty ω-category. Assume that L is defined for globular cardinals of dimension n and let X have dimension n + 1. Define L by induction on m-cells. Let γ: Y → X be a 0-cell of 𝔉X. Define L on γ as γ_{0}(y) where y is the unique element of Y (and so of Y_{0}). Assume L is defined on m-cells and let γ be an (m + 1)-cell of 𝔉X. By Observation 5.22 we have ∘_{y}γ[py, y] the unique 0-decomposition of γ. Using the induction assumption define L γ as

(L γ(py, y))_{y∈Y_{0} \f} in ∏_{y∈γ(Y_{0} \f)} 𝔉 (ΓX(γpy, γy)) .

Note that γ is an m-cell if and only if L γ is.

We show using induction that L preserves the ℓ-domain and ℓ-codomain operations for ℓ < m. The 0-domain of L γ is γy_{0} and the 0-codomain is γy_{ℓ} where y_{0} is the first element, respectively y_{ℓ} is the last element, of Y_{0}. Hence L preserves dom_{0} and cod_{0} .

Assume that L preserves the ℓ-domain operation. The following derivation begins by replacing γ with its 0-decomposition, uses a basic property of ω-categories to proceed from line 1 to line 2, uses Observation 5.23 to proceed from line 3 to line 4 and uses the induction assumption to proceed from line 4 to line 5. We have

L dom_{ℓ+1} γ = L dom_{ℓ+1} ∘_{y} γ[py, y]
= L ∘_{y} dom_{ℓ+1} γ[py, y]
= (L (dom_{ℓ+1} γ[py, y]) (py, y))_{y}
= (L dom_{ℓ} (γ[py, y](py, y)))_{y}
= (dom_{ℓ} L γ[py, y](py, y))_{y}
= dom_{ℓ+1} (L γ(py, y))_{y}
= dom_{ℓ+1} L γ

and L preserves the domain operations. Likewise for the codomain operations.

We show by induction that L preserves ℓ-composition for ℓ < m. By construction L preserves 0-composition. Assume that L preserves ℓ-composition. Let α and β be (ℓ + 1)-composable n-cells. Then each has 0-decomposition ∘_{y}α[y] and ∘_{y}β[y] (respectively). The following derivation begins by replacing α and β with their 0decompositions, uses a basic property of ω-categories to proceed from line 1 to line 2, uses Observation 5.24 to proceed from line 3 to line 4 and uses the induction assumption to proceed from line 4 to line 5. We have

L (β ∘^{ℓ+1} α) = L (∘_{y}β[py, y] ∘^{ℓ+1} ∘_{y}α[py, y])

= L (∘_{y}(β[py, y] ∘^{ℓ+1} α[py, y]))

= (L (β[py, y] ∘^{ℓ+1} α[py, y])(py, y))_{y}

= (L (β[py, y](py, y) ∘^{ℓ} α[py, y](py, y)))_{y}

= (L β(py, y) ∘^{ℓ} L α(py, y))_{y}

= (L β(py, y))_{y} ∘^{ℓ+1} (L α(py, y))_{y}

= L β ∘^{ℓ+1} L α

and L preserves composition.

5.31. Lemma. The ω-functor L: 𝔉X → 𝔉ΓX is an isomorphism.

Proof. The object set of 𝔉X is isomorphic to X_{0} and the object set of 𝔉ΓX is X_{0}.

Faithful. We show that L is faithful using induction on the n-cells of 𝔉ΓX. Consider morphisms γ: Y → X and γ′: Y′ → X of 𝔉X. Suppose that L γ = L γ′ is a 0-cell of 𝔉ΓX. Then Y and Y′ are singletons, γ and γ′ have identical image and so are isomorphic in GlobCard/X. Hence they are identical in 𝔉X.

Assume that L is faithful on n-cells and let L γ = L γ′ be an (n+1)-cell. We construct an isomorphism α: Y → Y′. By Observation 5.22 then γ and γ′ have canonical 0-decompositions ∘_{y}γ(y) and ∘_{y′}γ′(y′) for y ∈ Y_{0} \f and y′ ∈ Y′_{0} \f respectively. By the construction of these compositions and by definition of L then Y_{0} Y′_{0} are isomorphic. Such an isomorphism is unique and we have α_{0} : Y_{0} → Y′_{0} as Y_{0} and Y′_{0} are linear orders.

Uniqueness of the 0-decompositions in 𝔉ΓX implies that L γ(y) = L γ′(δ_{0}y) for each y ∈ Y_{0} \f. By definition of L then (L γ(y)(py, y)) and (L γ′(δ_{0}y)(pδ_{0}y′, δ_{0}y′)) are identical and by induction the restrictions γ(y)(py, y) and γ′(δ_{0}y)(pδ_{0}y, δ_{0}y) are identical. Then there is a (unique) isomorphism Y (py, y) ≅ Y′(pδ_{0}y, δ_{0}y) for each y ∈ Y_{0} \f. As the corresponding inclusions into Y ∘ u_{1} and Y′ ∘ u_{1} (respectively) are jointly epi then we have isomorphisms δ_{n}: Y_{n} ≅ Y′_{n} for n ≥ 1. The source and target operations are preserved and we have δ: Y ≅ Y′. Hence γ = γ′ and L is faithful.

Full. We show that L is full using induction on the n-cells of 𝔉ΓX. Let x be a 0-cell. Then x is an element of X_{0}. Let Y be a globular cardinal with a single element y and define a globular morphism γ: Y → X by γ_{0} y = x. Then Lγ = x.

Assume that L is full on n-cells and let x = (x_{i})_{i=h+1}^{k} be an (n + 1)-cell. By induction we have n-cells γ(i) such that x_{i} = L γ(i). Then as L preserves composition we have L (∘_{i=h+1}^{k}γ(i)) = ∘_{i=h+1}^{k}x_{i} which is (x_{i})_{i=h+1}^{k}.

Hence L : 𝔉X → 𝔉ΓX is an isomorphism.

6. Equivalence between iΔ and Θ

Michael Makkai and Marek Zawadowski demonstrate, in [MZ01], a duality between the category Disk as defined by André Joyal in [Jo97] and the category, denoted S in [MZ01], of simple ω-categories. We refer the reader to [MZ01] for the details, but quote their definition below. Note that [G] is the free ω-category on G an ω-graph which we call a globular set.

Let G be an ω-graph. Let us call an element (cell) a of [G] maximal if it is proper, that is, not an identity cell, and if the only monomorphisms m: H → G for which a belongs to the image of [m] are isomorphisms. Intuitively, an element is maximal if it is proper, and the whole graph G is needed to generate it. We call G composable if [G] has a unique maximal element; in that case, the maximal element may be called the composite of the graph.

…

An ω-category is simple if it is of the form [G] for a composable ω-graph. The category S is defined as the full subcategory of ωCat on the simple ω-category as objects.

In Proposition 4.8 of [MZ01] they demonstrate that an ω-graph is composable if and only if it is a globular cardinal. Hence the objects of S are ω-categories which are isomorphic to the free ω-category 𝔉X for some globular cardinal X.

6.1. Definition. We define a functor

Ψ: iΔ_{+} → ωCat.

Define Ψ on objects as the composite 𝔉∘Υ. See Definitions 5.16 and 5.25 and Observation 5.28, but we make it more explicit here. Let H be an object of iΔ_{+}. Let G = ΥH. Then the objects of G are those of H and the edge-object G (pi, i) is ΥH(i) for each i ∈ G_{∗} \f. The remaining edge-objects are empty ordinal graphs. Let A = 𝔉G. Then A is an ω-category with object set G_{∗} and hom-objects

A(i, j) = ∏_{k=i+1}^{j} 𝔉 ΥH(k)

when i < j in G_{∗}. For all i ∈ G_{∗} then A(x, x) is the terminal ω-category. For i > j then A(i, j) is the empty ω-category. Notice that the trivial object [−1] of iΔ_{+} is sent to the empty ω-category which is also initial.

We define Ψ on morphisms by induction on the height of their domain. Send morphisms with domain of dimension -1 (minus one) to the unique morphism out of the empty ω-category. Assume that Ψ is defined on morphisms with domain of height n and let g: H → K have domain of height n + 1. We construct an ω-functor F: ΨH → ΨK from the data of g. Let C = ΨH and A = ΨK. Then C has object set H_{∗} and A has object set K_{∗}. Define the object map of F as the object map of g. We construct an ω-functor F_{pi,i}: C (pi, i) → A (F(pi), F(i)) for each i ∈ Ob C \f. From the definition of Ψ on objects we have C (pi, i) = 𝔉ΥH(i) and

A (F (pi) , F (i)) = ∏_{j=F(pi)+1}^{F(i)} 𝔉ΥK(j)

where J_{i} = {F (pi) + 1, ..., F (i)} is the index set of the product. From Observation 2.3 we have J_{i} = (g^{∧})^{∗} (i) and so g^{∧}(j) = i for all j ∈ J_{i}. We have a morphism g(j): H(i) → K(j) of iΔ_{+} with domain of height n for each j ∈ J_{i} by definition of g. By induction, there are ω-functors Ψg(j): 𝔉ΥH(i) → 𝔉ΥK(j) which by the universal property of the product give the required morphism

F_{pi,i}: 𝔉ΥH(i) → ∏_{i=F(pi)+1}^{F(i)} 𝔉ΥK(j).  (3)

We have F_{i,j} = ∏_{k=i+1}^{j} F_{pk,k} by Definition 5.25 and Observation 5.28 for i < j. For i an object of C then F_{i,i} is the unique morphism into the terminal ω-category. For i > j then F_{i,j} has domain the initial (empty) ω-category.

Preserves composition. Let g′: H → K and g′′: K → L be composable morphisms of iΔ_{+}. Put F′ = Ψ(g′), F′′ = Ψ(g′′) and F = Ψ(g) where g = g′′ ∘ g′. Let i be an element of H_{∗}, let J_{i} = (g′^{∧})^{∗} (i) and let L_{j} = (g′′^{∧})^{∗} (j). Then L_{i} = (g′′ ∘ g′^{∧})^{∗} (i) is identically ⋃_{j∈J_{i}} L_{j}.

We show F = F′′ ∘ F′ by showing that the upper horizontal composite of

[figure: 𝔉ΥH(i); ∏_{j=J_{i}} 𝔉ΥK(j); ^{F′^{pi,i}}; 𝔉ΥH(i); 𝔉ΥK(j); Ψg′(j); ∏_{j=J_{i}} 𝔉ΥK(j); 𝔉ΥK(j); pr; 𝔉ΥK(j); ∏_{ℓ=L_{j}} 𝔉ΥL(ℓ); ^{F′′^{pj,j}}; ∏_{j=J_{i}} 𝔉ΥK(j); 𝔉ΥK(j); pr; ∏_{j=J_{i}} 𝔉ΥK(j); ∏_{ℓ=L_{i}} 𝔉ΥL(ℓ); ^{∏^{j} F′′^{pj,j}}; ∏_{ℓ=L_{i}} 𝔉ΥL(ℓ); ∏_{ℓ=L_{j}} 𝔉ΥL(ℓ); pr; 𝔉ΥK(j); ∏_{ℓ=L_{j}} 𝔉ΥL(ℓ); ^{F′′^{pj,j}}; 𝔉ΥK(j); 𝔉ΥL(ℓ); Ψg′′(ℓ); ∏_{ℓ=L_{j}} 𝔉ΥL(ℓ); 𝔉ΥL(ℓ); pr]

is identically F_{pi,i}. For each l in L_{∗} then g(ℓ): H(g^{∧}ℓ) → L(ℓ) is g′′(ℓ) ∘ g′(j) by definition of composition in iΔ_{+} where j = g^{′′∧}ℓ. By induction then Ψg(ℓ) is the diagonal composite. The construction ending at line 3 gives F_{pi,i} as the unique map 𝔉ΥH(i) → ∏_{ℓ=L_{i}} 𝔉ΥL(ℓ) which is ∏_{j} F′′_{pj,j} ∘ F′_{pi,i} as required.

6.2. Theorem. The category iΔ_{+} is equivalent to the category Θ_{+} by

Ψ: iΔ_{+} → Θ_{+}.

Proof. The functor Ψ is essentially surjective by Lemma 5.31.

Faithful. We show Ψ is faithful using induction on the dimension of the domain of ωfunctors. As the initial object of iΔ_{+} is sent to the initial ω-category then Ψ is faithful on morphisms with domains of dimension -1 (minus one) as their domain is the initial object. Assume Ψ is faithful on morphisms with domain of dimension n and that g, g′: H → K are parallel morphisms of iΔ_{+} with domains of dimension n + 1 such that F = Ψg and F′ = Ψg′ are identical. Then g = g′ as the object maps of F and F′ are identical.

Let C = ΨH. For each i ∈ Ob C \f the construction ending at line 3 gives

F_{pi,i} = F′_{pi,i}: 𝔉ΥH(i) → ∏_{j=F(pi)+1}^{F(i)} 𝔉ΥK(j)

where the index set of the product is J_{i} = {F (pj) + 1, F (pj) + 2, …, F (j)}. By construction, composition with the projections out of the product gives

Ψg(j) = Ψg′(j): 𝔉ΥH(i) → 𝔉ΥK(j)

and by the induction assumption g(j) = g′(j) for each j ∈ J_{i}. Let J = ⋃_{i∈Ob C \f} J_{i}. It remains to show for j ∉ J that the morphisms g(j) and g′(j) determined by j are identical.

For j ∉ J then g^{∧}j is an endpoint by Observation 2.4. Hence H(g^{∧}j) is trivial and g(j), g′(j): H(g^{∧}j) → K(j) are identical. Therefore Ψ is faithful.

Full. We show that Ψ is full using induction on the dimension of the domain of ωfunctors. Let F: ΨH → ΨK be an ω-functor where C = ΨH. We construct a morphism g of iΔ_{+} from the data of F such that Ψg = F. Define the object map of g as the object map of F.

Let F be an ω-functor with domain of dimension -1 (minus one). Then F has domain an initial ω-category and so g is the unique morphism [−1] → K. Assume that Ψ is full for ω-functors with domain of dimension n and suppose F has domain of dimension n + 1. We have for each object j ∈ Ob C \f morphisms (ω-functors)

F_{pi,i}: C(pi, i) → A(F(pi), F(i))

with domains of dimension n which are identically

F_{pi,i}: ΨH(i) → ∏_{j=F(pi)+1}^{F(i)} ΨK(j).

The product has index set J_{i} = {F (pj) + 1, F (pj) + 2, …, F(i)}. Composition with the projections of the product gives for each j ∈ J_{i} an ω-functor

F(i, j): ΨH(i) → ΨK(j).

By induction there is a morphism g(i, j) such that Ψg(i, j) = F(i, j) for each j ∈ J_{i} and each i ∈ Ob C \f. Let J = ⋃ J_{i} where the union is indexed over Ob C \f. It remains to define, for each j ∉ J, morphisms g(j): H(g^{∧}j) → K(j). For such j then g^{∧}j is an endpoint by Observation 2.4. Hence H(g^{∧}j) is initial and g(i) is determined. Therefore Ψ is full.

6.3. Corollary. The category iΔ is equivalent to the category S.

We have demonstrated that the categories Disk and Θ are dual using the well-known equivalence between intervals and ordinals. The category iI has been shown equivalent to Disk and provides a description of disks as inductively defined intervals. Similarly iΔ has been shown equivalent to Θ and provides a description of Θ in terms of inductively defined ordinals.

7. Labeled trees

In this section we define dual categories, named tI and tΔ, which are equivalent to the category Disk and the category Θ (respectively). To do so we construct categories named tI_{+} and tΔ_{+}, which are augmented counterparts to tI and tΔ and show that they are dual using the equivalence between ordinals and intervals. They are constructed from trees whose vertices are labeled with intervals and ordinals (respectively) and which satisfy certain conditions.

We begin by defining the concept of labeled tree with appropriate restriction and suspension operations. After defining the concept of constrained tree we state and prove a general theorem which gives mild conditions which allow an equivalence of categories to be lifted to an equivalence between certain categories of constrained trees labeled by the categories of the original equivalence.

We then define dual categories of constrained trees labeled by I_{+} and Δ_{+} which satisfy the conditions of the general theorem. After defining the concept of cropped tree the above equivalence is then restricted to the full subcategories with objects the cropped trees of positive degree.

7.1. Definition. A forest (A, F) labeled in a category C is a forest equipped with functors F_{n}: A_{n} → C for all n ∈ ℕ where A_{n} is considered a discrete category. A tree (A, F) labeled in a category C has A a tree.

7.2. Definition. A forest morphism (f, α): (A, F) → (B, G) in C is given by a tree map f: A → B of trees and a set of natural transformations

α_{n}: F_{n} ⇒ G_{n} ∘ f_{n}: A → C

for all n ∈ ℕ. A tree morphism (f, α): A → B in C has both A and B labeled trees.

Identity morphisms are given by an identity set map and identity natural transformations. Let (f: A → B, α: F ⇒ Gf) and (g: B → C, β: G ⇒ Hg) be composable morphisms. Then (g, β) ∘ (f, α) is defined as

(g ∘ f: A → C, β_{f} ∘ α: F ⇒ Hgf).

A forest op-morphism (f, α): (B, G) → (A, F) in C is a tree morphism in C^{op} and so is a tree map f: A → B and a set of natural transformations

α_{n}: G_{n} ∘ f_{n} ⇒ F_{n}: A → C

for all n ∈ ℕ. Let (g: B → C, β: Hg ⇒ G) and (f: A → B, α: Gf ⇒ F) be composable op-morphisms. Then (f, α) ∘ (g, β) is defined as

(g ∘ f: A → C, α ∘ β_{f}: Hgf ⇒ F).

We have the category F orest(C) of labeled forests and morphisms in C and its full subcategory T ree(C) with objects labeled trees in C.

7.3. Definition. We define a restriction operation on labeled trees. The restriction of (A, F) by x is denoted (A(x), F (x)) where (A, F) is a labeled forest and x is an element of A_{n} has A(x) given by Definition 4.3 and F (x)_{m} defined as the composite

A(x)_{m}  [figure: incl.] A_{n+m}  [figure: F_{n+m}] C.

The restriction of (f, α) by x is denoted (f(x), α(x)) where (f, α): A → B is a forest morphism in C and x is an element of A_{n} has f(x) given by Definition 4.3 and α(x)_{m} given by the composite pasting diagram

[figure: α_{n+m}; ⇒; A_{n+m}; B_{n+m}; f_{n+m}; A(x)_{m}; A_{n+m}; incl; A(x)_{m}; B(f_{n}x)_{m}; f(x)_{m}; B(f_{n}x)_{m}; B_{n+m}; incl; C; C; 1; A_{n+m}; C; F_{n+m}; A_{n+m}; B_{n+m}; f_{n+m}; B_{n+m}; C; G_{n+m}]

where the two vertical composites are F (i)_{m} and G(f_{n}x)_{m} (respectively).

The restriction of (f, α) by x is denoted (f(x), α(x)) where (f, α) is a forest opmorphism (with f: A → B and α: Gf ⇒ F) and x is an element of A_{n} has f(x) given by Definition 4.3 and has α(x)_{m} given by the composite pasting diagram where the two vertical composites are G(f_{n}x)_{m} and F (x)_{m} (respectively).

[figure: α_{n+m}; ⇒; B_{n+m}; A_{n+m}; f_{n+m}; B(f_{n}x)_{m}; B_{n+m}; incl; B(f_{n}x)_{m}; A(x)_{m}; f(x)_{m}; A(x)_{m}; A_{n+m}; incl; C; C; 1; B_{n+m}; C; G_{n+m}; B_{n+m}; A_{n+m}; f_{n+m}; A_{n+m}; C; F_{n+m}]

7.4. Definition. Define a suspension functor

su: F orest(C) × C → T ree(C)

as follows. Given a forest (A, F) in C and an object c in C then the suspension of A over c denoted su(A, c) is (A′, F′) where A′ = su A and F′ is defined by F′_{0}(∗) = c and F′_{n+1} = F_{n} for n ∈ ℕ.

Given a forest morphism (f, α): (A, F) → (B, G) and a morphism g: c → d of C then the suspension of f, α over g denoted su(f, g) is (f′, α′): su(A, c) → su(B, d) where f′ = su f and α′ is defined by α′_{0}(∗) = g and α′_{n+1} = α_{n} for n ∈ ℕ.

7.5. Observation. This is the “labeled” counterpart to Observation 4.5. The coproduct of a collection of labeled trees is a labeled forest and its suspension is a labeled tree. The labeled subtrees of the suspension are isomorphic to the trees of the original collection. We provide the details below.

Let c be an object of C and (A(i), F (i)) be a labeled tree in C with A(i)_{0} = {x_{i}} for each i in a set I. Let (A′, F′) be the suspension of (∑ A(i), ∑ F (i)) over c. By Observation 4.5 then copr(i): A(i) ≅ A′(x_{i}) and the left triangle of

[figure: A′(x_{i})_{n}; ∑ A(i)_{n}; incl.; ∑ A(i)_{n}; C; A(i)_{n}; A′(x_{i})_{n}; ≅; A(i)_{n}; ∑ A(i)_{n}; copr; A(i)_{n}; C; F (i)_{n}]

commutes. The lower composite is F′(x_{i})_{n} and we have an isomorphism

(copr(i), Id: F (i) ⇒ F′(x_{i}) ∘ copr(i))

between (A(i), F (i)) and (A′(x_{i}), F′(x_{i})).

7.6. Definition. A labeled forest (A, p, F) in C is said to be constrained by the functor U: C → Set when for each n ∈ ℕ we have an isomorphism

λ_{n}: A_{n+1} ≅ el(UF_{n})

such that λ_{n}x ∈ UF_{n}(p_{n}x) where el(UF_{n}) is the category of elements of UF_{n} and consists of pairs (y, ξ) with y ∈ A_{n} and ξ ∈ UF_{n}(y). Then λ_{n}x = (y, ξ) where y = p_{n}(x). The set A_{n+1} of (n + 1)-dimensional vertices of A is determined by the labels on its n-dimensional vertices.

7.7. Definition. A morphism (f, α): (A, p, F) → (B, q, G) between labeled trees in C is said to be constrained by U: C → Set when for each n ∈ ℕ

[figure: B_{m+1}; el(UG_{n}); η_{n}; A_{n+1}; B_{m+1}; f_{n+1}; A_{n+1}; el(UF_{n}); λ_{n}; el(UF_{n}); el(UG_{n}); el(U·α_{n})]

commutes where the horizontal arrows are the isomorphisms of Definition 7.6. An opmorphism (f: A → B, α: Gf ⇒ F): (B, q, G) → (A, p, F) between labeled trees in C constrained by U: C^{op} → Set also has that the above diagram commutes. As the horizontal maps above are isomorphisms, the set map f_{n+1} is determined by the data from lower dimensions. We have the category Con (C, U) of labeled forests in C constrained by U.

7.8. Definition. The 2-category Cat/_{Set} is the 2-category of small categories over Set. We define a 2-functor

Con : Cat/_{Set} → Cat

as follows. Let U: C → Set be an object of Cat/_{Set}, which we also write as (C, U), and define Con (C, U) as the category with objects and morphisms given by Definitions 7.6 and 7.7 (respectively). Let F: C → A be a morphism of Cat/_{Set} and define

Con F: Con (C, U_{C}) → Con (A, U_{A})
: (A, H) ↦ (A, F ∘ H)
: (f, α) ↦ (f, F · α)

by post-composition with F. Let (A, H) be a constrained tree. Then A_{n+1} is isomorphic to el(U_{C}H_{n}) which is identically el(U_{A}F H_{n}) by the commutativity required of morphisms in comma categories, in this case U_{C} = U_{A}F. Then (A, F H) is a constrained tree. Let (f, α) be a constrained morphism. Then el(U_{C} · α) is identically el(U_{A}F · α) and Con (F) is well-defined.

Let γ: F → G be a 2-cell (natural transformation) of Cat/_{Set} and define

Con γ: Con F ⇒ Con G: Con (C, U_{C}) → Con (A, U_{A})
: (A, H) ↦ (1_{A}, γ_{H})

by post-composition with γ. Naturality of Con (α) follows directly from that of α.

It is easy to see that Con preserves identities and composition of 1-cells and of 2-cells.

7.9. Theorem. Let F: C → A and G: A → C be 1-cells of Cat/_{Set}. If F and G are an adjoint pair then so are Con F and Con G. Moreover, if F and G are mutual inverse equivalences (respectively isomorphisms) then Con F and Con G are mutual inverse equivalences (respectively isomorphisms).

Proof. Since Con is a 2-functor, it preserves adjunctions, equivalences and isomorphisms.

Two cases of labeled trees are of interest here: labeling by Δ_{+} and by I_{+}. In the case of Δ_{+} we constrain by the functor U = U ∘ ( )^{∧} and for I_{+} by U = U where U is the underlying set functor. We define an additional requirement on such trees and call the trees satisfying this additional requirement cropped.

7.10. Definition. Let (A, p, F) be a labeled tree in Δ_{+}, respectively a labeled tree in I_{+}, constrained as stated above. An end element x ∈ A_{n+1} is one for which λ_{n,x} is either a greatest or least element of F_{n}(p_{n}x)^{∧} (respectively F_{n}(p_{n}x)). We call (A, p, F) cropped when, for all n ∈ ℕ,

x is an end element of A_{n+1} if and only if UF_{n+1}(x) is a singleton.

If (A, p) is a tree of degree 0 (zero), so that all the p_{n} are bijections, then the labeling F of a cropped tree (A, p, F) is unique. We call these the trivial cropped trees.

7.11. Definition. The category tI_{+} is the full subcategory of Con(I_{+}, U) whose objects are cropped labeled trees in I_{+} of finite degree. The category tI is the full subcategory of tI_{+} containing the trees of positive degree.

7.12. Definition. The category tΔ_{+} is the full subcategory of Con(Δ_{+}, U( )^{∧}) whose objects are cropped labeled trees in Δ_{+}^{op} of finite degree. The category tΔ is the full subcategory of tΔ_{+} containing the trees of positive degree.

7.13. Observation. An object (A, F) of tI_{+} is trivial if and only if F_{0}(∗) = [0]. An object (A, F) of tΔ_{+} is trivial if and only if F_{0}(∗) = [−1].

7.14. Observation. We provide an example of an object of tI_{+} of degree 3 (three).

[figure: [0]; [2]; [3]; [2]; [0]; [2]; [0]; [0]; [0]; [3]; [1]; [3]; [2]; [3]; [0]; [3]; [0]; [0]; [0]; [0]; [0]; [0]; [0]; [1]; [0]; [1]; [0]; [2]; [1]; [2]; [0]; [2]; [0]; [0]; [0]; [0]; [0]; [0]; [0]; [0]; [0]; [0]; [0]; [0]; [0]; [0]; [0]; [1]; [0]; [1]; [0]; [0]; [0]; [0]; [0]; [0]; ⋮; [0]; ⋮; [0]; ⋮; [0]; ⋮; [0]; ⋮; [0]; ⋮; [0]; ⋮; [0]; ⋮; [0]; ⋮; [0]; ⋮; [0]]

7.15. Corollary. The categories tI_{+} (resp. tI) and tΔ_{+} (resp. tΔ) are dual.

Proof. The functors ( )^{∧} and ( )^{∨} of the ordinal/interval equivalence and the constraining functors of tI_{+} and tΔ_{+} satisfy the hypothesis of Theorem 7.9.

The categories tI_{+} and tΔ_{+} of labeled trees were designed for their similarity with the categories F am_{Σ}(I_{+}) and F am_{Π}(Δ_{+}) (respectively). The objects of tI_{+} and tΔ_{+} are trees of intervals, respectively of ordinals, with extra structure and their morphisms are essentially tree morphisms which respect the additional structure.

8. Equivalence of new definitions

In this last section we demonstrate an equivalence between tI_{+} and iI_{+} and, in a parallel proof, between tΔ_{+} and iΔ_{+}.

8.1. Observation. A constrained tree is a labeled tree with the requirement (see Definition 7.6) that the fiber of a vertex and the underlying set of its label are isomorphic. The restriction operation reflects the fibers of all vertices. Hence the restriction of a constrained (respectively cropped) tree is constrained (respectively cropped) and the restriction of a constrained morphism is constrained.

We show that the coproduct of constrained trees is constrained. Given a collection of constrained trees (A(i), F (i)) with comma objects λ(i) then, by the universal property of coproduct, ∑ λ_{n}: ∑ A_{n+1} → ∑ el(UF (i)_{n}) is an isomorphism. As the functor el( ) preserves coproducts then ∑ el(UF (i)_{n}) is isomorphic to el(∑ UF (i)_{n}). Hence ∑ A(i)_{n+1} ≅ ∑ el(UF (i)_{n}) and ∑ A(i) is constrained.

We show that the coproduct of constrained morphisms is constrained. Given a collection (f(i), α(i)) of constrained morphisms then in

[figure: ∑ B(j)_{n+1}; ∑ el(UG(j)_{n}); ≅; ∑ A(i)_{n+1}; ∑ B(j)_{n+1}; ∑ f(i)_{n+1}; ∑ A(i)_{n+1}; ∑ el(UF (i)_{n}); ≅; ∑ el(UF (i)_{n}); ∑ el(UG(j)_{n}); ∑ el(U·α_{n}); ∑ el(UG(j)_{n}); el(∑ UF (i)_{n}); ≅; ∑ el(UF (i)_{n}); ∑ el(UG(j)_{n}); ∑ el(U·α_{n}); ∑ el(UF (i)_{n}); el(∑ UF (i)_{n}); ≅; el(∑ UF (i)_{n}); el(∑ UF (i)_{n}); el(∑ U·α_{n})]

the left square commutes by functoriality of coproduct and the right square commutes by naturality. Hence the coproduct of constrained morphisms (and constrained trees) is constrained. The coproduct of cropped trees is cropped as the coprojections in Set are jointly surjective monomorphisms.

The suspension su(A, c) is constrained by U if A_{0} ≅ Uc and A is constrained by U. The suspension su((f, α), g) is constrained by U if f_{0} ≅ Ug and (f, α) is constrained by U. Similarly, su(A, c) is cropped if A is cropped and A(i) is trivial when i is an endpoint of Uc.

8.2. Proposition. The category tI_{+} is equivalent to the category iI_{+} by a functor

Ξ_{I}: tI_{+} → iI_{+}

which is surjective on objects.

Proof. Let (A, F) be a cropped tree of height n in tI_{+}. Then we have an object C = F_{0}(∗) of I_{+} and a set map

H: U(C) → Ob Con(I_{+}, U)
: i → A(i)

such that H(i) is trivial if and only if i is an endpoint of C. Hence a tree of height n in tI_{+} has an alternative description as a pair (C, H) consisting of an object C of I_{+} and function H: U(C) → Ob Con(I_{+}, U) such that H(i) is trivial if only if i is an endpoint of C and has height strictly less than n, for all i ∈ U(C). Similarly, a morphism of tI_{+} has an alternative description as a pair (γ, h): (C, H) → (C′, H′) consisting of a morphism γ: C → C′ of I_{+} and function h: U(C) → Ar Con(I_{+}, U) with h(i): H(i) → H′(γi).

This data is, by design, that required by Definition 3.1 for the objects and morphisms of iI_{+}. We define a functor

Ξ_{I}: tI_{+} → iI_{+}

by sending the trivial tree of tI_{+} to the trivial object of iI_{+}, and by sending morphisms into the trivial tree to morphisms into the trivial object. The rest follows by induction.

8.3. Corollary. The category tI is equivalent to the category iI.

The proofs of propositions 8.2 and 8.4 are nearly identical. We include both and list here the two ways in which the categories iI_{+} and iΔ_{+} differ which affect the details of the two proofs. First, the trivial object of iI_{+} is the terminal object [0] and the trivial object of iΔ_{+} is the initial object [−1]. Second, the subtrees of an object H of iI_{+} are indexed by the elements of H_{∗} where the subtrees of an object K of iΔ_{+} are indexed by the elements of (K_{∗})^{∧}.

8.4. Proposition. The category tΔ_{+} is equivalent to the category iΔ_{+} by

Ξ_{Δ} : tΔ_{+} → iΔ_{+}

which is surjective on objects.

Proof. Let (A, F) be a cropped tree of height n in tΔ_{+}. Then we have an object C = F_{0}(∗) of Δ_{+} and a set map

H: U(C^{∧}) → Ob Con(Δ_{+}, U( )^{∧})
: i → A(i)

such that H(i) is trivial if and only if i is an endpoint of C^{∧}. Hence a tree of height n in tΔ_{+} has an alternative description as a pair (C, H) consisting of an object C of Δ_{+} and function H: U(C^{∧}) → Ob Con(Δ_{+}, U( )^{∧}) such that H(i) is trivial if only if i is an endpoint of C^{∧} and has height strictly less than n, for all i ∈ U(C^{∧}). Similarly, a morphism of tΔ_{+} has an alternative description as a pair (γ, h): (C′, H′) → (C, H) consisting of a morphism γ: C′ → C of Δ_{+} and function h: U(C^{∧}) → Ar Con(Δ_{+}, U) with h(i): H′(γ^{∧}i) → H(i).

This data is, by design, that required by Definition 3.2 for the objects and morphisms of iΔ_{+}. We define a functor

Ξ_{Δ} : tΔ_{+} → iΔ_{+}

by sending the trivial tree of tΔ_{+} to the trivial object of iΔ_{+}, and by sending morphisms out of the trivial tree to morphisms out of the trivial object. The rest follows by induction.

8.5. Corollary. The category tΔ is equivalent to the category iΔ.

The category tI provides a description of disks as trees with vertices labeled by intervals. Similarly tΔ provides a description of Θ in terms of trees with vertices labeled by ordinals.

References

[Ba98] Michael Batanin, Monoidal globular categories as a natural environment for the theory of weak n-categories, Advances in Mathematics 136 (1998) 39–103

[BS00] Michael Batanin, Ross Street, The universal property of the multitude of trees, Journal of Pure and Applied Algebra 154 (2000) 3–13

[Be02] Clemens Berger, A cellular nerve for higher categories, Advances in Mathematics 169 (2002) 118–175

[Jo97] André Joyal, Disks, duality and Θ-categories, Preprint (1997)

[Ma98] Saunders Mac Lane, Categories for the Working Mathematician, 2nd edition, Springer-Verlag (1998)

[MZ01] Mihaly Makkai and Marek Zawadowski, Duality for simple ω-categories and disks, Theory and Applications of Categories 8 (2001) 114–243

[St87] Ross Street, The algebra of oriented simplexes, Journal of Pure and Applied Algebra 49 (1987) 283–335

[St00] Ross Street, The petit topos of globular sets, Journal of Pure and Applied Algebra 154 (2000) 299–315

[Ve08] Dominic Verity, Complicial sets: characterising the simplicial nerves of strict ω-categories, Memoirs of the American Mathematical Society 193 (2008)

Macquarie University New South Wales 2109 Australia

Email: david.oury@mq.edu.au

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

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

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

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

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

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

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

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

gavin seal@fastmail.fm

Transmitting editors.

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

Valeria de Paiva: valeria.depaiva@gmail.com

Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, Macquarie University: steve.lack@mq.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Tom Leinster, University of Glasgow, Tom.Leinster@glasgow.ac.uk Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca