nLab
sketch

Contents

Context

Category theory

Limits and colimits

Contents

Idea

In a Lawvere theory, one specifies an algebraic theory by giving a small category TT with finite products. Then a model of the theory is given by a functor TSetT \to Set that preserves products.

A sketch is a generalization of this idea, where we take a small category TT, and pick some distinguished limit and colimit cones. Then a model of the sketch is a functor that preserves these limits and colimits.

Definition

Definition

A sketch is a small category TT equipped with a set LL of cones and a set CC of cocones. A realized sketch is one where all the cones in LL are limit cones and all the cocones in CC are colimit cocones.

A limit-sketch is a sketch with C=C = \emptyset, while a colimit-sketch is a sketch with L=L = \emptyset.

A model of a sketch in a category 𝒞\mathcal{C} is a functor T𝒞T\to \mathcal{C} taking each cone in LL to a limit cone and each cocone in CC to a colimit cocone. In particular, TT is realized if and only if its identity functor is a model. Frequently the notion of model is restricted to the case 𝒞=Set\mathcal{C}=Set.

A category is called sketchable if it is the category of models (in SetSet) of a sketch.

Examples

Example

A Lawvere theory is a special case of a (limit-)sketch, where the category is one with a distinguished object XX such that all objects are (isomorphic to) powers of XX, and C=C = \emptyset and LL is the set of all product cones.

Properties

Relation to accessible and locally representable categories

Proposition

The categories of models of sketches are equivalently the accessible categories.

Proposition

The categories of models of limit-sketches are the locally presentable categories.

Remark

From the discussion there we have that

  • an accessible category is equivalently:

    • a full subcategory of a presheaf category that’s closed under κ\kappa-filtered colimits for some κ\kappa
    • the category of models of a sketch
  • a locally presentable category is equivalently:

    • a reflective full subcategory of a presheaf category that’s closed under κ\kappa-filtered colimits for some κ\kappa
    • the category of models of a limit sketch
    • an accessible category with all small limits
    • an accessible category with all small colimits

We can “break in half” the difference between the two and define

  • a locally multipresentable category to be equivalently:
    • a multireflective full subcategory of a presheaf category that’s closed under κ\kappa-filtered colimits for some κ\kappa
    • the category of models of a limit and coproduct sketch
    • an accessible category with all small connected limits
    • an accessible category with all small multicolimits

and

  • a weakly locally presentable category to be equivalently:
    • a weakly reflective full subcategory of a presheaf category that’s closed under κ\kappa-filtered colimits for some κ\kappa
    • the category of models of a limit and epi sketch
    • an accessible category with all small products
    • an accessible category with all small weak colimits

Symmetric Monoidal Structures on the Category of Sketches

The category of sketches is well behaved: it is complete, cocomplete, cartesian closed and has a second symmetric monoidal closed structure.

Proposition

The category of sketches is topological over the category of directed pseudographs.

The above proposition gives the category of sketches Cartesian products - however these are often not the sketches one would expect when thinking of the product of two theories. Instead consider the tensor product:

Proposition

Let S,TS,T be sketches. We define the sketch STS \otimes T to be:

The vertices of STS \otimes T are the product of the set of vertices from SS, TT. The set of arrows is given as

{(α,b)|αEdge(S),bVertex(T)}{(a,β)|aVertex(S),βEdge(T)} \{ (\alpha, b) | \alpha \in \mathsf{Edge}(S), b \in \mathsf{Vertex}(T)\} \cup \{ (a, \beta) | a \in \mathsf{Vertex}(S), \beta \in \mathsf{Edge}(T)\}

where the source of (α,b)(\alpha,b) is (s S(α),b)(s_S(\alpha), b), and vice versa. SS is often called the horizontal structure and TT as the vertical structure. The set of diagrams is the union of the following three sets:

  • The horizontal diagrams are constant in the second parameter: H={(D,b)|DDiagrams(S),bVertex(T)}H = \{ (D, b) | D \in \mathsf{Diagrams}(S), b \in \mathsf{Vertex}(T) \}
  • The vertical diagrams are constant in the first parameter: V={(a,D)|aVertex(S),DDiagrams(T)}V = \{ (a, D) | a \in \mathsf{Vertex}(S), D \in \mathsf{Diagrams}(T) \}
  • Also add every square diagram: CC is the set of squares for each edge α\alpha in SS, βT\beta \in T

The set of cones and cocones are define analogously to the set of commuting diagrams, except only the vertical and horizontal cones are taken.

This tensor product, along with the unit (*,,,)(*, \emptyset, \emptyset, \emptyset), gives the category of sketches a second symmetric monoidal category.

This monoidal structure is useful for considering structures like double categories (i.e. categories in the category of categories).

Proposition

Let S,TS,T be sketches, and XX some category. Then the category of models of SS in the category of models of TT in XX is equivalent to the category of models of STS \otimes T in XX.

References

An overview of the theory is given in

An extensive treatment of the links between theories, sketches and models can be found in

  • Michael Makkai, Robert Paré, Accessible categories: The foundations of categorical model theory Contemporary Mathematics 104. American Mathematical

    Society, Rhode Island, 1989.

That not only every sketchable category is accessible but that conversely every accessible category is sketchable is due to

  • Christian Lair, Catégories modelables et catégories esquissables, Diagrammes (1981).

The category of sketches itself was studied as a semantics for type theory in:

  • John W. Gray“The Category of Sketches as a Model for Algebraic Semantics’.” Categories in Computer Science and Logic: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference Held June 14-20, 1987 with Support from the National Science Foundation. Vol. 92. American Mathematical Soc., 1989.

Last revised on March 25, 2019 at 18:41:54. See the history of this page for a list of all contributions to it.