nLab sketch

Idea

The notion of a sketch (Bastiani & Ehresmann 1972) is one formalisation of the notion of a theory. It is diagrammatic, and has the advantage of being very close to category theory, allowing it to very naturally express the category theoretic structure which is required to construct a model of the theory (finite products, say). On the other hand, it is not a very concise notion: as Example illustrates, writing down the full details of a sketch even in the simplest examples takes time!

There is a precise correspondence between categories of models of sketches and accessible categories and locally presentable categories, discussed below.

The notion of a sketch generalises that of a Lawvere theory. See Example .

Details

Sketches

Definition

A sketch is a small category $T$ equipped with a set $L$ of cones and a set $C$ of cocones. Alternatively, it is a directed graph equipped with a set $D$ of diagrams, a set $L$ of cones, and a set $C$ of cocones.

Definition

A realized sketch is one where all the cones in $L$ are limit cones and all the cocones in $C$ are colimit cocones.

Definition

A limit sketch is a sketch with $C = \emptyset$.

Definition

A colimit sketch is a sketch with $L = \emptyset$.

Definition

A finite product sketch is a limit sketch in which the only cones are those of finite product diagrams.

Definition

A finite limit sketch is a limit sketch in which the only cones are those of finite limit diagrams.

Models of sketches

Definition

A model of a sketch in a category $\mathcal{C}$ is a functor $T\to \mathcal{C}$ taking each cone in $L$ to a limit cone and each cocone in $C$ to a colimit cocone.

In particular, $T$ is realized if and only if its identity functor is a model.

Definition

If one takes the definition of a sketch to be that involving directed graphs, a model of a sketch in a category $\mathcal{C}$ is a morphism of directed graphs from the directed graph of the sketch to the underlying directed graph of $\mathcal{C}$, so that diagrams are taken to commutative diagrams, cones are taken to limit cones, and co-cones are taken to colimit cones.

Frequently the notion of model is restricted to the case $\mathcal{C}=Set$.

Definition

A category is sketchable if it is the category of models (in $Set$) of a sketch.

Examples

Example

A sketch, more precisely a finite product sketch, for the theory of pointed sets can be constructed as follows. The directed graph can be taken to be the following.

The set of diagrams can be taken to be empty. The set of cones can be taken to be the set with the single cone given by the vertex $v_{1}$, i.e. a cone of the empty diagram. The set of co-cones can be taken to be empty.

A model of this sketch necessarily sends the vertex $v_{1}$ to a product of the empty diagram, hence to a one element set $1$; sends the vertex $v_{2}$ to any set $X$; and sends the arrow from $v_{1}$ to $v_{2}$ to an arrow from $1$ to $X$, that is, to an element of $X$, as required.

Example

A sketch, more precisely a finite product sketch, for the theory of unital magmas (sets equipped with a binary operation which has a two sided neutral element) can be constructed as follows.

The directed graph can be taken to be the following:

The set of diagrams can be taken to have six elements, the first consisting of:

the second consisting of the following

the third consisting of the following

the fourth consisting of the following

the fifth consisting of the following

and the sixth consisting of the following.

The set of cones can be taken to have four elements, the first being the leftmost vertex (cone of the empty set), the second consisting of

the third consisting of

and the fourth consisting of the following.

The set of co-cones can be taken to be empty.

In a model of this sketch, the leftmost vertex is sent to a one element set $1$, the middle vertex is sent to an arbitrary set $X$, the top vertex is sent to the product $1 \times X$, the bottom vertex is sent to the product $X \times 1$, and the right vertex is sent to the product $X \times X$. The arrow $e$ picks out an element $e_{X}$ of $X$.

The arrow $e,-$ is sent to an arrow $e_{X} \times id: 1 \times X \rightarrow X \times X$, which is forced by the universal property of $X \times X$ and the fact that the diagrams

and

commute to really be the product of the arrows $e_{X}$ and $id$. Similarly, the arrow $-,e$ is sent to an arrow $id \times e_{X}: X \times 1 \rightarrow X \times X$, which is forced by the fact that the diagrams

and

commute to really be the product of the arrows $e_{X}$ and $id$.

The arrow $m$ is sent to a map $m: X \times X \rightarrow X$ which is arbitrary except that the diagrams

and

are forced to commute.

Putting all of this together, we see that we exactly have a unital magma.

Example

A Lawvere theory is a special case of a (limit) sketch, where the category is one with a distinguished object $X$ such that all objects are (isomorphic to) powers of $X$, and $C = \emptyset$ and $L$ 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.

(Adámek & Rosický 1994, Cor. 1.52)

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

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,T$ be sketches. We define the sketch $S \otimes T$ to be:

The vertices of $S \otimes T$ are the product of the set of vertices from $S$, $T$. The set of arrows is given as

$$\{ (\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 $(\alpha,b)$ is $(s_S(\alpha), b)$, and vice versa. $S$ is often called the horizontal structure and $T$ 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) | D \in \mathsf{Diagrams}(S), b \in \mathsf{Vertex}(T) \}$

• The vertical diagrams are constant in the first parameter: $V = \{ (a, D) | a \in \mathsf{Vertex}(S), D \in \mathsf{Diagrams}(T) \}$

• Also add every square diagram: $C$ is the set of squares for each edge $\alpha$ in $S$, $\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 $(\ast, \emptyset, \emptyset, \emptyset)$, gives the category of sketches a monoidal structure.

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

Proposition

Let $S,T$ be sketches, and $X$ some category. Then the category of models of $S$ in the category of models of $T$ in $X$ is equivalent to the category of models of $S \otimes T$ in $X$.

One can ask when $S \otimes T$ has the same models as $T \otimes S$, i.e. when $S$-models in the category of $T$-models are the same as $T$-models in the category of $S$-models. This is the case, roughly, when the colimits and limits specified in the sketches commute. For example, since limits always commute, you can swap the sketches if both are limit sketches. And you can swap a finite product sketch with a sifted colimit sketch etc. For more precise statements see David Bensons article and the references therein.

In general one can not swap the order in the monoidal product. For example take the (terminal object + coproduct)-sketch $S$ whose models are maps $X \to X \coprod 1$ and the finite product sketch $M$ whose models are monoids. Look at models of these in $Set$: Since in the category of monoids the terminal object is also initial, the coproduct of a monoid with the terminal object is isomorphic to that monoid again. Therefore $S$-models in $M$-Mod are monoids with an endomorphism. On the other hand $M$-models in $S$-Mod are pairs of monoids one of which has one element more, plus a homomorphism between them. These categories do not seem to be equivalent.

Related concepts

• internalization

References

General

Original articles:

• Charles Ehresmann, Esquisses et types de structures algébriques, Bul. Inst. Polit. Iasi 14 1–2 (1968) 1-14 [pdf]

• Andrée Bastiani, Charles Ehresmann, Categories of sketched structures, Cahiers de Topologie et Géométrie Différentielle Catégoriques, Tome 13 no 2 (1972) 104-214 (numdam:CTGDC_1972__13_2_104_0)

Overview in:

• Charles Wells, Sketches: Outline with references, 1993 (citeseer:10.1.1.217.3531, pdf)

See also:

• Michael Barr, Notes on Sketches, Technical report of the Electrotechnical Laboratory (computer language section), Tsukuba, Japan (1997) [pdf, pdf]

Textbook accounts:

• Michael Barr, Charles Wells, Section 4 of: Toposes, Triples, and Theories, Originally published by: Springer-Verlag, New York, 1985, republished in:

  Reprints in Theory and Applications of Categories, No. 12 (2005) pp. 1-287

and with emphasis on the relation to locally presentable and accessible categories:

• Michael Makkai, Robert Paré, Chapter 3 onwards in: Accessible categories: The foundations of categorical model theory, Contemporary Mathematics 104. American Mathematical Society, Rhode Island, 1989 (ISBN:978-0-8218-7692-3)

• Jiří Adámek, Jiří Rosický, Def. 1.49 onwards in: Locally presentable and accessible categories, Cambridge University Press (1994)

Proof that not only every sketchable category is accessible but that conversely every accessible category is sketchable:

• Christian Lair, Catégories modelables et catégories esquissables, Diagrammes 6 5 (1981) [numdam:DIA_1981__6__A5_0, pdf]

The tensor product of sketches is investigated here:

• David D. Benson, Multilinearity of sketches, TAC, vol.11, nr. 3, pp.269-277

The category of sketches itself was studied as a categorical 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.

See also

• Martin Brandenburg, Large limit sketches and topological space objects (arXiv:2106.11115)

In enriched category theory

Discussion of sketches the generality of enriched category theory:

• G. Max Kelly, Structures defined by finite limits in the enriched context, I, Cahiers de topologie et géométrie différentielle 23 1 (1982) 3-42 [numdam:CTGDC_1982__23_1_3_0]

• Francis Borceux, Carmen Quinteriro, Jiří Rosický, A theory of enriched sketches, Theory and Applications of Categories, 4 3 (1998) 47-72 [tac:4-03, pdf]

Generalisations

Discussion in the generality of internalization into 2-categories:

• Ross Street, Complete objects relative to a theory (1976) [pdf, pdf]

• Yoshiki Kinoshita, John Power, Makoto Takeyama, Sketches, Journal of Pure and Applied Algebra 143 1-3 (1999) 275-291 [doi:10.1016/S0022-4049(98)00114-5]

• Ross Street, Pointwise extensions and sketches in bicategories [arXiv:1409.6427]

Generalising the approach of Kinoshita, Power & Takeyama 1999, a notion of sketch relative to an algebraic weak factorisation system is defined in:

• John Bourke, Richard Garner, Algebraic weak factorisation systems II: Categories of weak maps, Journal of Pure and Applied Algebra 220 (2016) [arXiv:1412.6560, doi:10.1016/j.jpaa.2015.06.003]