nLab
direct category

Contents

Idea

A direct category is a category in which the morphisms only go in “one direction.”

A direct category can be thought of as a category of geometric shapes for higher structures which includes only the “inclusions of faces,” not any “degeneracy” maps. (The more general notion of Reedy category can also include degeneracies.) The objects of a direct category admit no nontrivial automorphisms, but the notion can also be generalized to allow for such automorphisms.

Alternately, a direct category can be thought of as a combinatorial representation of a single geometric shape. In this case, each object is a “face” and each morphism is the inclusion of a lower-dimensional face in a higher-dimensional one. If DD is a direct category regarded as a category of geometric shapes, then each dDd\in D can be represented by the slice category D/dD/d, a direct category regarded as a single geometric shape. (In general, however, D/dD/d may admit more automorphisms than dd, so it may need to be equipped with a “labeling” or “orientation” to truly recapture the shape dd.)

Finally, a direct category can also be thought of as a categorification of the notion of well-founded relation from posets to categories.

Definition

Standard definition

A category DD is a direct category if the following equivalent conditions are satisfied.

  • DD contains no infinite descending chains of nonidentity morphisms \cdots \to\cdot \to\cdot\to\cdot (including cycles of length >0\gt 0).
  • The relation aba\prec b on ob(D)ob(D) defined by “there exists a nonidentity morphism from aa to bb” is well-founded.
  • There exists a function d:ob(D)Ordd\colon ob(D)\to Ord, where OrdOrd is the class of ordinals, such that every nonidentity morphism of DD raises the degree.
  • DD is a Reedy category (in particular an elegant Reedy category) in which D D_- consists only of identity maps (or equivalently D +D_+ is all of DD).

In particular, a poset is a direct category just when its strict order relation <\lt is well-founded. Thus, direct categories can be seen as a categorification of well-founded relations.

If D opD^{op} is a direct category, then we say that DD is an inverse category.

Direct versus one-way categories

Of course, a direct category can have no nonidentity endomorphisms, since any such endomorphism would be a cycle of length 1. A category with this property is sometimes called a one-way category.

A direct category is also necessarily skeletal, since any nonidentity isomorphism and its inverse would form a cycle of length 2. The notion of generalized direct category, below, relaxes this requirement.

Conversely, a skeletal one-way category can have no cycles of nonidentity morphisms of any finite length, since by the one-way property all morphisms in such a cycle would be isomorphisms, hence endomorphisms by skeletality, and hence identities by the one-way property. Since any infinite chain in a finite category contains a cycle, we see that

  • A finite category is a direct category if and only if it is one-way and skeletal.

Since this condition is self-dual, we also see that

  • A finite category is direct if and only if it is inverse.

An infinite category can be one-way and skeletal without being direct or inverse, such as the poset \mathbb{Z} with its usual ordering. However, if it additionally has finite fan-out, meaning that for each object xx there are altogether only finitely many morphisms with source xx (and arbitrary target), then it must be an inverse category, for any infinite non-cyclic chain would induce infinitely many distinct morphisms out of any of its objects by composition. In FOLDS, skeletal one-way categories with finite fan-out are called simple categories and used as signatures; thus

  • Any simple category (in the sense of FOLDS) is an inverse category.

However, a category can be inverse without having finite fan-out. Let SS be an infinite set and consider the poset S{}S \cup \{\infty\}, with SS having the discrete ordering (no nonidentity arrows) and \infty being less than every element of SS. This does not have finite fan-out, since \infty is the source of infinitely many distinct arrows, but it is inverse, since there are clearly no chains of nonidentity arrows of length >1\gt 1.

Allowing automorphisms

Some categories of geometric shapes, such as the tree category Ω\Omega and the cycle category Λ\Lambda, include automorphisms of their objects. By analogy with the notion of generalized Reedy category, we can define DD to be a generalized direct category by replacing “identity” with “isomorphism” in the above definition. Thereby we obtain the following equivalent conditions for DD to be a generalized direct category.

  • DD contains no infinite descending chains of noninvertible morphisms \cdots \to\cdot \to\cdot\to\cdot.
  • The relation aba\prec b on ob(D)ob(D) defined by “there exists a noninvertible morphism from aa to bb” is well-founded.
  • There exists a function d:ob(D)Ordd\colon ob(D)\to Ord, where OrdOrd is the class of ordinals, such that every noninvertible morphism of DD raises the degree.
  • DD is a generalized Reedy category in which D D_- consists only of isomorphisms (or equivalently D +D_+ is all of DD).

Of course, Ω\Omega and Λ\Lambda are not generalized direct categories themselves, since they have degree-lowering degeneracies as well, but their full subcategories of coface maps are generalized-direct. More generally:

  • If RR is any generalized Reedy category, then R +R_+ is a generalized direct category.

Properties

Model structures

Every direct category (and every inverse category) is in particular a Reedy category, in fact an elegant Reedy category. Therefore whenever MM is a model category there is a Reedy model structure on M DM^D. In the case of direct and inverse categories, these model structures are even easier to describe, since either the latching or the matching objects are degenerate.

Examples

Inside the simplex category

The wide subcategory Δ +\Delta_+ of the simplex category on the injective map (the co-face maps) is direct. Its presheaves are semi-simplicial objects/semi-simplicial sets as opposed to simplicial objects/simplicial sets.

The direct category of corollas

We now define a “universal” generalized direct category which contains “all” geometric shapes for higher structures. This is based on (Borisov).

A functor f:DEf\colon D\to E between generalized direct categories is called a dependency if it is equivalent to the inclusion of a sieve, or equivalently if it is a fully faithful functor and a discrete fibration in the generalized sense of Street. If DD and EE are skeletal (as they must be if they are non-generalized direct categories), then any dependency must be isomorphic to the inclusion of a sieve. One also usually works only with skeletal generalized direct categories, although the definition does not require it.

If we regard direct categories as a categorification of well-founded relations, then dependencies are a categorification of injective simulations, i.e. the inclusions of initial segments.

Define a corolla to be a generalized direct category with a weakly terminal object; we call this object the vertex of the corolla. If a generalized direct category is finite and skeletal, then it is a corolla if and only if it has a unique object which is not the source of any noninvertible morphism. Corollas are the direct categories which it is most natural to regard as single geometric shapes; other direct categories are more like “pasting diagrams” of geometric shapes.

Let CorollaCorolla be the category of small skeletal corollas and dependencies.

Theorem

CorollaCorolla is a (large) generalized direct category.

Proof

Suppose that d 2C 2d 1C 1d 0C 0\cdots \overset{d_2}{\to} C_2 \overset{d_1}{\to} C_1 \overset{d_0}{\to} C_0 is a descending chain of noninvertible dependencies. Any dependency whose target is a corolla and whose image contains the vertex must be an equivalence, and hence an isomorphism if the corollas are skeletal; thus none of the dependencies C n+1C nC_{n+1} \to C_{n} can have the vertex in their image. Let c nC 0c_n\in C_0 be the image of the vertex nC n\star_n \in C_n under the composite d 0d n1d_0\circ \dots \circ d_{n-1}. Then we have a noninvertible morphism c n+1c nc_{n+1} \to c_n for each nn, arising from some map d n( n+1) nd_n(\star_{n+1}) \to \star_n which exists since n\star_n is weakly terminal. This is a contradiction, since C 0C_0 is a generalized direct category.

Of course, the same is true for any subcategory of CorollaCorolla. In particular, it is very natural to consider only the category FinCorollaFinCorolla of finite corollas, which is moreover essentially small (though not finite).

We next observe that CorollaCorolla is the “universal” generalized direct category in a certain sense. Let DD be any generalized direct category; then the slice category D/dD/d is a corolla for any dDd\in D. Moreover, if f:ddf\colon d\to d' is a morphism in DD which is monic, then the “composition” functor Σ f:D/dD/d\Sigma_f\colon D/d \to D/d' is a dependency. Thus, if every morphism in DD is monic, we have a functor ext D:DCorollaext_D\colon D \to Corolla with ext D(d)=D/dext_D(d)= D/d and ext D(f)=Σ fext_D(f)=\Sigma_f.

Now if f,g:ddf,g\colon d\to d' are parallel morphisms and Σ f=Σ g\Sigma_f=\Sigma_g, then in particular f=Σ f(id d)=Σ g(id d)=gf = \Sigma_f(id_d) = \Sigma_g(id_d) = g; thus ext Dext_D is faithful. Therefore, if DD is a direct category in which all morphisms are monic, and in which D/dD/dD/d \cong D/d' implies d=dd=d' (which includes many examples), then DD is equivalent to a subcategory of CorollaCorolla.

This subcategory of CorollaCorolla is usually not full, however. In particular, for dDd\in D the corolla D/dD/d will generally admit more automorphisms than dd has in DD. For instance, if DD is a non-generalized direct category, then dd has no nontrivial automorphisms, whereas D/dD/d generally will. In particular, if the objects of DD have any sort of “orientation” or “labeling,” then this information is forgotten by the functor ext Dext_D.

References

Revised on November 23, 2012 13:22:30 by Urs Schreiber (82.169.65.155)