Introduction
Atish Bagchi and I are writing a monograph Graph-Based Logic and Sketches (latest draft September, 2008). It involves a kind of double abstraction and is hard to understand. This post is the first in a series of posts aimed at explaining what is going on. I am writing this series on my own. Don’t blame Atish for anything I say!
A sketch (invented fifty years ago by Charles Ehresmann) is a mathematical structure designed for specifying a type of mathematical structure. Sketches are described in this series of posts, and in detail in references [1] and [3].
The monograph is about an abstraction of the concept of sketch called a form. Forms also specify kinds of mathematical structures, and they can specify more kinds of structures than sketches can. (See reference [2].) A form is a kind of sketch of a sketch (not literally).
I will sneak up on the idea of sketch using the specification of directed graphs as an example.
Directed graphs
This picture shows a directed graph. A graph theorist might call it a directed multigraph with loops.
What makes it a directed graph is that it has some nodes (x, y, z and w in this case), some arrows (a, b, c, d, e, u), and each arrow has a source and a target; for example, the source of c is z and its target is x. That information completely determines the structure of a directed graph.
The picture has lots of extraneous information irrelevant to the structure, for example the placement of the nodes. This extraneous data may make it easier to see the structure but is not part of the structure of the directed graph itself. (Note 1.)
The statement in blue above is an informal definition of “directed graph” written in mathematical English. This definition determines a type of mathematical structure. You could go on and say that a morphism of directed graphs must take nodes to nodes, arrows to arrows, and preserve source and target. For example, a morphism f from the directed graph in the picture to some other directed graph must satisfy the requirements that the source of f(c) must be f(z) and the target must be f(x). Thus the two statements in blue define a category of directed graphs. (Note 2).
About definitions
The definitions in blue require experience in reading mathematical prose and fairly sophisticated pattern-recognition to determine that they are definitions and to determine just what requirements they impose for an object to be a directed graph. This is discussed in detail in abstractmath.org.
Both the definitions in blue could be made more formal. They could be clearly marked as definitions and the example remarks could be segregated into another paragraph. For example:
Definition. A directed graph consists of two sets A, whose elements are called arrows, and N, whose elements are called nodes, and two functions
and
.
This formal definition is still a piece of mathematical English. It still requires pattern recognition to extract the mathematical content. But what is the mathematical content of a definition? Both mathematical logic and sketch theory provide (different) answers to this question: Both provide a mathematical object that determines a type of structure.
First-order theories
A first-order theory is a mathematical structure that specifies a type of mathematical structure. It provides a mathematically defined system of symbols, expressions and formulas that determine a type of structure, along with a set of rules that determine which sets-with-structure are of the desired type, in other words are models. The expressions and formulas are strings of symbols defined recursively and subject to axioms.
As an example, the theory for directed graphs could contain two types (node, arrow), a set of variables of each type, two unary function symbols s and t, and some production rules such as: “If a is of type arrow, then s(a) is a well formed term of type node.” (You could also use a single-sorted theory, with predicates that say whether an object is a node or an arrow.) A model of this theory (in the category of sets) must consist of two sets and two functions between them.
This theory is a mathematical object. Having first-order theories and their models as math objects allows you to prove theorems such as the Löwenheim-Skolem Theorem (every finitary first order theory that has an infinitary model has non-isomorphic models, which is where you get non-standard integers).
The details about first order theories are spelled out in the Stanford encyclopedia entry. Wikipedia has a list of first order theories of common structures such as groups and (undirected) graphs.
A first order theory could be described as a mathematical object consisting of strings of symbols subject to certain axioms, along with rules describing what models must be. Thus it taks a formal definition, such as the definition of directed graph given above, and models it as strings, in the same way we might model the flight of a cannonball as a parabola. (This is a different use of the word “model” from the meaning of model of a first order theory. Abstractmath.org has a discussion about the various uses of the word “model”.) Thus a first order theory could be called a string-based specification of a type of math structure.
Sketches
A sketch is a graph-based specification of a type of mathematical structure. The sketch for directed graphs is shown at the right. It is itself a graph, which is confusing. Get used to it. That is ultimately the key to the idea of form.
A model M of this sketch in a category
consists of objects
and
of
and morphisms
and
of
.
Thus a model in the category of sets is both of these things:
(A) A particular directed graph.
(B) A functor from the sketch to the category of sets.
(A functor from a directed graph into a category is defined in the same way as a functor from a category into a category, except that there are no composites or identities to preserve. )
A morphism of models of this sketch from
to
is a pair of functions
and
for which these diagrams commute:
If you chase these diagrams you will discover that they say both these things:
(A)
is a morphism of directed graphs.
(B)
is a natural transformation from
to
.
That is a start on understanding sketches: Models are functors and morphisms between models are natural transformations.
Specifying more kinds of structure
Groups, small categories, fields and many other structures are models of sketches. To show how that happens, I have to say how to sketch binary operations (to define groups), how to impose equations (to state the associative law), how to define equalizers (so I can say how to define composition when the domain of one morphism equals the codomain of another) , “not equals” (so I can say
), and many other things. We can go further and sketch special kinds of categories (cartesian closed, toposes, and others) which we will need to do to create forms with more power than sketches. (Note 3).
Notes
1. You can denote the set of positive divisors of 7 by {1,7} or by {7,1}; in either case it is the set whose elements are exactly 1 and 7 and nothing else. Whether the 1 or the 7 comes first inside the braces is not relevant. It is interesting that most notation systems for mathematical object has properties that are irrelevant to the structure denoted — even the notation for a two-element set. This introduces noise in the required pattern recognition process.
2. There are other ways to define morphism of directed graphs; for example, you can allow an arrow to go to a node. That category of directed graphs can also be sketched. So can undirected graphs. Reference [4] gives a survey of this area.
3. When we sketch types of categories, the morphisms of models turn out to be functors that preserve the structure on the nose instead of up to isomorphism. This is very annoying.
Acknowledgment
Thanks to Toby Bartels for corrections and suggestions.
References
1. Toposes, triples and theories, by Michael Barr and Charles Wells. Revised edition in Reprints in Theory and Applications of Categories, No. 1, 2005. Downloadable PDF.
2. On the limitations of sketches, by Michael Barr and Charles Wells. Canadian Mathematical Bulletin 35 (1992), 287-294.
3. Sketches of an Elephant: A Topos Theory Compendium, Volume 2 (Oxford Logic Guides 44), by Peter T. Johnstone. Oxford University Press, ISBN 978-0198524960.
4. Graphs of morphisms of graphs, by R. Brown, I. Morris, J. Shrimpton and C. D. Wensley, 2008.