This blog has moved, but some stuff has been left behind.

This blog has moved to a new location: http://www.abstractmath.org/Word%20Press/

During the move, most links were trashed and so were some posts.  Most of the difficulty occurred in a long sequence of posts about turning definitions into mathematical objects.  Because of this, I have retained those files here on the old site until I can merge them into one long article.  Once I do this, this website will disappear.

All the other articles on the site have been trashed.  They are all on the new site.  Some of the links in the articles published before 2010 have not yet been repaired.

Definitions into mathematical objects 9

This is the ninth post in a series, continuing TDMO1TDMO2TDMO3TDMO4, TDMO5TDMO6, TDMO7 and TDMO8.  This series builds up to an explanation of the concept of form in the paper Graph-Based Logic and Sketches by Atish Bagchi and me.  This post tells how to sketch cartesian closed categories and gives an example of a form.

Cartesian closed categories

A Cartesian closed category is a category mathcal{C} with the following structure:

  • mathcal{C} has binary products.
  • For each pair of objects A and B of mathcal{C}, there is an object B^A and an arrow text{eval}:B^Atimes Ato BB^A is an exponential object.
  • For each triple of objects A, B and C of mathcal{C}, there is a map lambda:text{Hom}(Btimes A, C)to text{Hom}(B,C^A) such that for every arrow f:Btimes Ato C, the diagram below commutes:

CCCDiagrams1(lameval)

  • For any arrow g:Bto C^A, lambda(text{eval}circ(gtimestext{Id}[A]))=g.

It follows that lambda is a natural isomorphism of homsets.

Going from f:Btimes Ato C to lambda f is called currying or partial application. You can curry a multivariable function all the way down to a constant.  The inverse process is usually called uncurrying.   It constitutes getting rid of entries in the codomain of a function that are function spaces by adding variables to the function. I suggest using blanding instead of “uncurrying”.

The FL sketch for cartesian closed categories

The FL sketch for CCC’s (which I will call CCCSk) is spelled out in detail in GBLS. I will mention some of the constructions here.  I will use many of them in the next section to give an example of a form.

Objects and arrows

The arrows needed are spelled out in Sections 7.2 and  7.6 of GBLS.  Here I mention

  • text{unit}:text{ob}totext{ar} that formally picks out the identity arrow of an object.
  • text{twovf}, the formal set of functions of two variables, in other words arrows of the form f:Btimes Ato C.
  • text{arrow}:text{twovf}totext{ob}^f that picks out the arrow f itself.
  • text{tsource}:text{twovf}totext{ob} that picks out the source Btimes A of a two-variable function f:Btimes Ato C.
  • text{curry}, the formal set of curried functions from B to C^A.
  • text{csource}:text{curry}totext{ob}^B and text{ctarget}:text{curry}totext{ob}^{C^A} that pick out the source and target of a curried function g:Bto C^A.
  • text{fs}:text{ob}^Btimestext{ob}^Atotext{ob}^{B^A} that picks out the function space B^A of two objects B and A.
  • text{ar}_2, the formal set of composable pairs of arrows in the FL sketch for categories, defined by this pullback diagram:

CatAr2Def(Ar2Def)

For the purposes of the example below, I need  text{bsource}:text{twovf}totext{ob}^Btimestext{ob}^A as defined by this diagram:CCCTSourceDef(Bsource)

In an object-oriented program built on this work, this would be a derived method..

One of the limit cones in CCCSk defines text{curry} and in particular gives text{fs} the properties it needs:

CCCurryDiagram(Curry)

The commutative diagram below should have been included in the FL sketch for categories in Section 7.2 of GLBS.   It gives the composite of a composable pair the right source and target.

CatCompCompat(Compreq)

Representing reflexive function spaces

An object A of a cartesian closed category is reflexive if there are arrows I:A^Ato A and J:Ato A^A such that

ReflexiveFSRetractDiagram(ret)

commutes.  That means  A^A is a retract of AA^A is called  a reflexive function space. RFS’s  are the theoretical basis for programming languages which have “functions as first class objects”.

So a sketch for RFS’s would be defined by a limit cone over  the diagram below.  I have always shown the cones in blue before, but GBLS does not show cones at all, and it isn’t necessary to show them.

ReflexiveConeBase(ReflFSConeBase)

To specify a reflexive function space you would have to give  an object A and two arrows I:A^Ato A, J:Ato A^A that satisfies Diagram (lameval) above, so the mandatory projections would be to text{ob}^A, text{ar}^I and text{ar}^J.  The projection to text{ob}^{A^A} is induced by Diagram (Curry) above, the projection to text{ar}^{<J,I>} by Diagram (Ar2Def), and the projection to text{ob}^Atimes text{ob}^A follows from the fact that it is the vertex of the product cone shown.  The other projections exist by composition.

Let’s call the vertex of this cone text{rfs} for “reflexive function space”.  Note that all the objects and arrows in this diagram exist in the FL sketch for cartesian closed categories.

Now you can check (or forget all the constructions above and just Put Your Hands On The Monitor And Believe) that in a model M of the FL sketch for CCC’s, M(text{rfs}) would be the set of reflexive function spaces together with specified inclusion I:A^Ato A and retraction J:Ato A^A.

Non-surprise: In any model of the FL sketch for CCC’s in the category of sets, M(text{rfs}) will be the empty set. It is well known that for any set A  the function space A^A has cardinality properly bigger that the cardinality of A, so there can be no inclusion of A^A into A.

Nevertheless, M(text{rfs}) is a perfectly well defined set.  It just turns out to be empty.

Forms

Forms are defined formally in GBLS.  This series of posts is supposed to give you an intuitive idea or understanding of form.  Well, we can make a form for reflexive function spaces out of the work done above.  Some terminology:

Constructor space

The sketch CCCSk for cartesian closed categories is a constructor space. A constructor space must be an FL-sketch that “contains” and is “generated” (see GBLS, Chapter 6.1) by the FL sketch for categories, and indeed CCCSk is built from the FL sketch for categories by adjoining some objects and arrows, cones and commutative diagrams that all exist already in the FL Cattheory for categories (see TDMO6).  So a constructor space text{C} has models we can call  C-categories. In particular a model for CCCSk in sets is a cartesian closed category.  In previous posts I have constructed constructor spaces for categories with finite products and categories with finite limits.

Constructor spaces construct doctrines, in the one-dimensional case and with restrictions I will mention in a later post.

For any constructor space text{C} , take an object F in the FL Cattheory of text{C}   and adjoin a new arrow f:1to F where 1 is the terminal object.  f  is what we call a C-form and text{C} with f as a freely adjoined arrow is called text{C}_f.

A model of a text{C}-form “in a C-category cal{K}“  means that cal{K} is a model of text{C}_f  This means that in  cal{K}, M(F) is nonempty.

The CCC-form for reflexive function spaces is then a global element of the node text{rfs} of CCCSk as constructed above for some CCC.  There are no models in the category of sets, but there are many toposes (and many other CCC’s) that do have models, such as the realizability topos.

I have lots of miscellaneous comments and explanations to make about the idea of form which must wait for another post.

References

[1] Charles Wells (1990), A generalization of the concept of sketch.

(see TDMO6) (see TDMO6)

Definitions into mathematical objects 8

This is the eighth post in a series, continuing TDMO1TDMO2TDMO3TDMO4,TDMO5TDMO6 and TDMO7.  This series builds up to an explanation of the concept of form in the paper Graph-Based Logic and Sketches by Atish Bagchi and me.  This post tells how to sketch categories with finite products.

Categories with finite products

We gave an FL sketch for categories in TDMO7.  The sketch has (among others) objects the formal set (Note 2) of objects \text{ob}, the formal set of arrows \text{ar} and the formal set of composable pairs of arrows \text{ar}_2, as well as arrows

\mathbf{source}, \mathbf{target}:\mathbf{ar}\longrightarrow\mathbf{ob} that formally pick the source and target of an arrow and

\mathbf{comp}:\mathbf{ar_2}\longrightarrow\mathbf{ar} that picks out the composite of a pair of arrows.

A category has finite products (is an FP category) if it has terminal objects and binary products.  GBLS describes the construction of the FL sketch for categories with finite products in section 7.3, which spells out how you sketch the set of terminal objects and the set of binary product cones.  I will give a more detailed discussion of how to do binary product cones here and introduce the annotation notation we use.

Syntax and semantics

We must distinguish between the FL sketch for FP categories and its models, which are FP categories.  A diagram in the FL sketch will be in black (the color for syntax) and a diagram in a category with finite products will be green (the color for semantics).  In both syntax and semantics, projection arrows may be blue and arrows that exist uniquely (fill-in arrows) may be red.

Product diagrams

A product diagram in an FP category looks like this:

ProductCone(Diagram \Lambda)

But a diagram can look like that without being a product diagram. You have to say that it is a product diagram.  (Note [1].)  This means that for any cone to the same pair of objects

AnyCone

(Diagram \Gamma)

there is a unique arrow h making this diagram commute:

FiaDiagram

(Diagram F)

FL sketch for FP categories

To get the FL sketch for FP categories, you start with the sketch for categories and add some objects and arrows.  The ones listed below are the objects and arrows needed for sketching the set of binary cones and finite-product cones.  Others are needed for the terminal object (much easier).

Objects

\text{cone}, the formal set of cones of the form \Lambda.

\text{fid}, the formal set of fill-in diagrams (diagrams of the form of F above).

Arrows

\text{prod}:\text{ob}\times\text{ob}\rightarrow\text{cone}, that picks out the product cone over a pair of objects.

\text{soco}:\text{fid}\rightarrow\text{cone}, that picks out the source cone of a fill-in arrow.

\text{taco}:\text{fid}\rightarrow\text{cone}, that picks out the target cone of a fill-in arrow.

\text{ufid}:\text{cone}\rightarrow\text{fid}, that takes a cone to the unique fill-in diagram that has the cone as source cone.

\text{fia}:\text{fid}\rightarrow\text{ar} that formally picks out the fill-in arrow in a fill-in diagram.

Specification for the formal set of cones

The FL sketch for FP categories contains this limit cone, which requires that the two arrows in a cone have the same source. Note that I have named the projections lproj and rproj.

ConeDef

(Diagram ConeSpec)

Annotations

This cone is annotated according to a system that is spelled out precisely in GBLS.  The annotation of this diagram refers to cone \Gamma above.  Some perspectives on this situation:

  1. The annotations allow you to chase the diagram.  For example, if \Gamma is a member of the set of cones of a model, then \text{lproj}(\Gamma)=q_1 and \text{source}(q_1)=\text{V}.
  2. \Gamma is being used as the shape graph (GBLS, 2.3) for ConeSpec.
  3. The annotation is a section of the model thought of as a sheaf.

Specification for the formal set of fill-in diagrams

This much more complicated annotated limit cone defines \text{fid}:

fidcone

I completed the annotation compared to the version in GBLS, whose partial annotation generates the rest.  The three projection arrows shown generate all the others, not shown to avoid clutter.

Some notes and examples:

  1. It is worthwhile checking through the conditions to see that this limit cone really does specify fid.  If you do, you will see the sketch needs a couple of commutative diagrams, found in GBLS, 7.3.2.
  2. The whole diagram is commutative because of the diagrams just mentioned and the commutative diagrams of the FL sketch for categories mentioned in TDMO7 (and described completely in GBLS 7.2).
  3. This diagram is symmetrical in spirit, with one exception: The arrow prod breaks the symmetry because there is no corresponding arrow going upward.  This reflects the fact that a fill-in diagram is not symmetrical: The right hand cone is a limit cone but the left hand cone is not.
  4. I suspect that the diagram could be drawn in a way that is really symmetrical (geometrically) in three dimensions (or four?), except for the break mentioned in (3).

What’s next

We will look more briefly at the FL sketch for cartesian categories, and then it is time, finally, to define form.

Notes

1. When students start taking college math, they soon discover that they have to read the surrounding text to understand what a symbolic expression means.  The expression is no longer self-sufficient.  (The \times symbol can mean multiplication of numbers, of matrices, or cross product of vectors.) When I first came across this aspect of mathematics in a matrix theory course at Texas Southmost College, I felt that I had been ejected from paradise.

2. It is bothersome to refer to the formal sets of objects and of arrows, because the FL sketch for categories, as well as the FL sketch for FP categories I discuss in this post, has models in many other FL categories.  \text{ob} could be called the formal object of objects, and so on.  In fact I could call it the formal object of objects, since green is for semantics. I expect to combine these posts into an expository paper eventually and perhaps I will carry out that practice there. However, I foresee complications which I must contemplate first. (Compare the device I suggested in this post on the comma rule).

References

  1. Atish Bagchi and Charles Wells, Graph-Based Logic and Sketches, draft, September 2008, on ArXiv.
  2. Michael Barr, Models of sketches (1986). Cahiers de Topologie et Géométrie Différentielle Catégorique, 27:93-107.
  3. Michael Barr and Charles Wells. On the limitations of sketches (1992). Canadian Mathematical Bulletin, 35:287-294.
  4. Michael Barr and Charles Wells, Category Theory for Computing Science (1999). Les Publications CRM, Montreal (publication PM023).
  5. Michael Barr and Charles Wells, Toposes, Triples and Theories (2005). Reprints in Theory and Applications of Categories 1.
  6. Peter T. Johnstone, Sketches of an Elephant: A Topos Theory Compendium, Volume 2 (2002). Oxford Logic Guides 44, Oxford University Press, ISBN 978-0198524960.
  7. Yoshiki Kinoshita, John Power, and Makoto Takeyama. Sketches (1997). In Mathematical Foundations of Programming Semantics, Thirteenth Annual Conference, Stephen Brookes and Michael W. Mislove, editors. Elsevier.
  8. A.J. Power and Charles Wells. A formalism for the speci fication of essentially algebraic structures in 2-categories (1992) Mathematical Structures in Computer Science,2:1-28.
  9. Charles Wells. A generalization of the concept of sketch (1990). Theoretical Computer Science, 70:159-178.

Definitions into mathematical objects 7

This is the seventh post in a series, continuing TDMO1, TDMO2, TDMO3, TDMO4, TDMO5 and TDMO6.  This series builds up to an explanation of the concept of form in the paper Graph-Based Logic and Sketches by Atish Bagchi and me.  This post discusses the sketch for categories.

The sketch for categories

FL sketches (finite-limit sketches) makes it possible to construct a sketch for categories. To do this you need some nodes:

\mathbf{ob}, which in a model will become the set of objects –  so in our “formal” terminology  is the formal set of objects.  (This terminology, by the way, is due to John W. Gray).

\mathbf{ar}, the formal set of arrows.

\mathbf{ar}_2, the formal set of composable pairs of arrows.

\mathbf{ar}_3, the formal set of composable triples of arrows, needed to state the associative law.

It needs many arrows, some of which are:

\mathbf{unit}:\mathbf{ob}\longrightarrow\mathbf{ar} that formally picks the identity arrow of an object

\mathbf{source}, \mathbf{target}:\mathbf{ar}\longrightarrow\mathbf{ob} that formally pick the source and target of an arrow.

\mathbf{comp}:\mathbf{ar_2}\longrightarrow\mathbf{ar} that picks out the composite of a pair of arrows.

…as well as many structural arrows that, for example, pick out the first arrow in a composable chain, or that picks out the pair of arrows <h, g\circ f> given a composable triple.

Cones and diagrams

Of course, you can’t just say that \mathbf{ar}_2 is the formal set of composable pairs of arrows.   What you must do is produce a cone that forces it to be that formal set.  And here it is:

CompositeCone

(The blue arrows are the projections, the black objects and arrows form the base diagram.  Note that the middle blue arrow is superfluous, as mentioned in TDMO5.  If you drop it, you may recognize this as an ordinary pullback diagram.)

You need an analogous cone for M(\mathbf{ar_3}) and diagrams for associativity and to make the identity arrows behave right.  The details are in GLBS (reference [1]), chapter 7.

In a model M, the elements of M(\mathbf{ar_2}) are diagrams that look like this:

CompositeChain2

This green diagram is in the model (semantics), and the cone above is a diagram in the syntax. You have to make the distinction constantly in this subject. This is remarkably annoying. To help, I am systematically putting objects of the category-that-is-the-model in green, and cone projections in blueBlack and blue means syntax,  green means semantics.

Remarks

M(\mathbf{ar_2}) is the domain of the composition arrow comp.  So defining categories requires more subtlety that defining an ordinary algebra, where the domains of the ops are always cartesian products:  this domain is an equalizer.  To sketch categories requires the full power of finite limits, not just finite products. Of course, that last sentence does not follow from anything I have said, since there might be a rascally way to use only finite products.  But there isn’t: the category of small categories is not regular (Exercise 6, page 278, of [3])  but any category of multisorted universal algebras (which are the same thing as models of FP theories) does have that property: see [2], section 8.4.

Nevertheless, the category of models of an FL sketch always has all sortwise (see note 1) limits and all sortwise filtered colimits. in particular initial algebras.  We will use that fact.

Categories with structure

Most categories with particular properties can also be sketched with FL sketches.  These include

  • Categories with finite limits
  • Cartesian closed categories
  • Toposes
  • Symmetric monoidal categories
  • Abelian categories

That’s for the next post.

Note

1.  Constructing a particular kind of limit or colimit  “sortwise” means that it is constructed sort by sort.  For example, if always M(S)\times M(T) = M(S\times T), then the category of models has sortwise products.  In most of the references the name “pointwise” is used.

References

  1. Atish Bagchi and Charles Wells, Graph-Based Logic and Sketches, draft, September 2008, on ArXiv.
  2. Michael Barr and Charles Wells, Toposes, Triples and Theories (2005).  Reprints in Theory and Applications of Categories 1.
  3. Michael Barr and Charles Wells, Category Theory for Computing Science (1999).  Les Publications CRM, Montreal (publication PM023).
  4. Michael Barr, Models of sketches (1986).  Cahiers de Topologie et Géométrie Différentielle Catégorique, 27:93-107.

Definitions into mathematical objects 6

This is the sixth post in a series, continuing TDMO1, TDMO2, TDMO3, TDMO4 and TDMO5.  This series builds up to an explanation of the concept of form in the paper Graph-Based Logic and Sketches by Atish Bagchi and me.  This post discusses the cattheories of finite-product sketches and finite-limit sketches (FP sketches and FL sketches).

Background

An FL sketch (finite-limit sketch) is a finite graphmathcal{G} with a finite set mathcal{D} of finite formally commutative diagrams and a finite set mathcal{C} of formal limit cones over finite diagrams (which are not usually among the formally commutative diagrams (Note 1).)

A model of an FL sketch in an FL categoryC is a digraph map into the (underlying graph of) the FL category that take the diagrams inmathcal{D} to commutative cones and the cones inmathcal{C}  to limit cones.

The category of models of the FL sketch mathcal{S} in an FL category mathcal{C} is denoted by mathbf{Mod}left( mathcal{S},mathcal{C} right).

FL and FP cattheories

The FL cattheory of a linear sketchmathcal{S} is a categorytext{CatTh}(text{FL}, mathcal{S}) together with a  modeltext{G}:mathcal{S}totext{CatTh}(text{FL}, mathcal{S}) with the the property that for any model M of mathcal{S} in a category C, there is a unique model M' of text{CatTh}(text{FL}, mathcal{S}) in C such that

GM.

commutes.  G is the generic model of mathcal{S}.

The category of models of the cattheory text{CatTh}(text{FL},mathcal{S}) in mathcal{C} is denoted by mathbf{Mod}left( text{CatTh}(text{FL},mathcal{S}),mathcal{C} right).

The cattheory has this universal property:

Theorem The map Mmapsto GM:mathbf{Mod}left( mathcal{S},mathcal{C} right)to mathbf{Mod}left( text{CatTh}(text{FL},mathcal{S}),mathcal{C} right)

is an equivalence of categories.

(Compare the corresponding theorem in TDMO3 for linear categories.)

This theorem forces the cattheory to be determined up to natural equivalence of categories that commutes with the generic model.  For all practical purposes, a model of the sketch is thus the same thing as a model of its cattheory.

An FP sketchmathcal{S} and its FP cattheorytext{CatTh}(text{FP}, mathcal{S}) are defined in the same way, except that the finite diagrams that the cones are over have to be discrete, and it has properties analogous to those for FL sketches given above.  Note that any FP sketch or  linear sketch will also have an FL cattheory.

Constructing FL cattheories

The linear cattheory of a linear sketch is just the free category generated by the graph of the sketch, with the formally commutative diagrams forced to be commutative.  It is more complicated to prove the existence of the FL cattheory of an FL sketch.  Once you do show it exists, it follows easily from the definition that it is uniquely determined up to equivalence of categories.

There are two approaches to showing the existence of the FL cattheory.

As a fixed point

Introduce an operator on categories that adjoins diagrams that in effect add limit cones to finite diagrams that don’t already have limits.  This is done in lots of detail in sections 4.2 and 4.3 of GLBS (Reference [1]).  Starting with an FL-sketchmathcal{S}, the cattheorytext{CatTh}(text{FL}, mathcal{S}) is the minimum fixpoint of this operator.

This is the computer-sciencey way of doing it.  Each arrow and commutative diagram in the theory is constructed explicitly. When GLBS constructs proofs, this step-by-step construction corresponds to the inductive construction of formulas and rules of inference in classical string-based logic.

Embedded in a functor category

Given an FL sketch mathcal{S}, the categorymathbf{Mod}left( mathcal{S},text{Set} right) of models of mathcal{S} in the category of sets turns out to be a full reflective subcategory of the presheaf category text{Set}^mathcal{S}.

Let’s spell out what this means: the models are finite-limit-preserving functors and the presheaf category contains all functors.  The reflectivity means that the embedding has a left adjoint, which implies that a limit of a diagram in the model category is also the limit of the diagram in the presheaf category.  The fullness means that every natural transformation between models is a morphism of models.

Using these facts you can get an embedding of mathcal{S}^{op} in text{Set}^{mathcal{S}}; text{CatTh}(text{FL}, mathcal{S}) is then the full FL subcategory generated by the image of the embedding.

This is worked out in detail for the FP case in [3], Chapter 4.3.  The construction is then carefully described for the FL case  in Chapter 4.4, but the proof is omitted.  It is quite analogous to the FP case.

I have been focusing here on the FL case because that is the foundation of the construction of forms in GBLS.

Notes

1.  It is a nice exercise to show that you can eliminate all the commutative subdiagrams from the base diagram of a limit cone and get the same limit.

References

  1. Atish Bagchi and Charles Wells, Graph-Based Logic and Sketches, draft, September 2008, on ArXiv.
  2. Michael Barr and Charles Wells, Category Theory for Computing Science (1999).  Les Publications CRM, Montreal (publication PM023).
  3. Michael Barr and Charles Wells, Toposes, Triples and Theories (2005).  Reprints in Theory and Applications of Categories 1.

Addenda to the 1993 Sketches paper

I have uploaded here a version of my 1993 sketches paper with an addendum listing a few relevant papers written since then.  I have not kept up with the field well enough to contemplate a complete revision of the 1993 paper.

I recommend that more people update their papers this way.  I did it by making a new PDF file with the added references and then using Acrobat to combine it with the old paper into one file.  That way I didn’t have to re-TeX the old paper, which is a good thing, since I don’t know where some of the .sty files are.

Definitions into mathematical objects 5

This is the fifth post in a series, continuing TDMO1, TDMO2, TDMO3 and TDMO4.  This series builds up to an explanation of the concept of form in the paper Graph-Based Logic and Sketches by Atish Bagchi and me.

Note So far I have described linear sketches and FP-sketches, and I described the cattheory of a linear sketch.  FP-sketches have cattheories, too.  They will be described together with the cattheories of FL-sketches (defined below) in a later post.

Finite Limits

A cone to a set \cal{S} of objects of a category consists of an object v of the category and one arrow from v to each object in \cal{S}.  A finite-product diagram is a cone to such a (finite) set with the unique fill-in property I explained in TDMO4.

Now suppose we have a finite diagram \cal{D} in a category.  I am specifically not assuming it is commutative.  A commutative cone to \cal{D} is an object v, an arrow(called a projection) from v to each node of \cal{D}, with the additional property that each triangle formed by two projections and an arrow of the diagram must commute.  The diagram is called the base diagram of the cone.

Here is an example base:PullbackBase(a)

A commutative cone over this base will look like the left diagram below.Pullbacks

Since the triangles involving two projections have to commute, the diagonal project is determined by the other two.  For this reason, this particular example is almost always drawn as on the right.

Two other examples:  In each case all the projections are shown on the left and only the necessary ones on the right.

Equalizers(b)LimitCones(c)

A limit cone over a diagram is a commutative cone over the diagram with the same unique-fill-in property that product cones have.  For example if this is a limit cone over diagram (a) above

PullbackDiagram(d)

and the blue arrows on the left below also form a commutative cone over the same base, then there must be a unique fill-in arrow making everything commute in the diagram on the right.PullbackSawHorse

This particular shape (d) of limit cone is called a pullback diagram. A limit cone in the shape of (b) is an equalizer diagram. It turns out that if you assume that if all pullbacks and equalizers exist, then you have limit cones over every finite diagram for free.  Limit cones of shape (c) don’t have a common name but they will be referred to in a later post.

Since a finite set of objects is just a finite diagram with no arrows, product diagrams are limit diagrams.  The commutativity requirement is then vacuous.

A category has all finite limits is called an FL-category. An older name, which, as computer scientists say, should be deprecated, is a left exact category. From the remark in the previous paragraph, an FL-category is automatically an FP-category.

FL-Sketches

An FL-sketch is a digraph together with some  specified finite formally commutative diagrams and some specified finite formal limit diagrams.  A model of an FL-sketch in a category \mathcal{C} is a functor from the digraph to \mathcal{C} that takes the specified formally commutative diagrams to commutative diagrams and the specified formal limit diagrams to limit diagrams.

The first key to understanding GBLS is that all sorts of interesting kinds of categories (cartesian closed, toposes, symmetric monoidal) are models of FL-sketches.  Indeed, I betcha (lived in Minnesota a whole year) every kind of n-category that anyone ever defined is a model of an FL-sketch — it doesn’t take anything that might be called “n-sketches”.  However, they will have the same problem as ordinary categories in that in the category of models the structure has to be preserved on the nose.  In the case of FL-sketches for different kinds of 1-categories, the sketch’s model category is equivalent to the usual way we define categories of that kind of category.  What “equivalence” means for “every kind of n-category” is referred to in Reference 4.

References

  1. Atish Bagchi and Charles Wells, Graph-Based Logic and Sketches, draft, September 2008, on ArXiv.
  2. Michael Barr and Charles Wells, Category Theory for Computing Science (1999).  Les Publications CRM, Montreal (publication PM023).
  3. Michael Barr and Charles Wells, Toposes, Triples and Theories (2005).  Reprints in Theory and Applications of Categories 1.
  4. n-Labs, Equivalence of categories.

Definitions into mathematical objects 4

This is the fourth post in a series, continuing TDMO1, TDMO2 and TDMO3.  This series builds up to an explanation of the concept of form in the paper Graph-Based Logic and Sketches by Atish Bagchi and me.

What has happened so far

I have defined special cases of sketch and the concept of the cattheory of a sketch for those cases. The special cases include

  • The sketch is a digraph (DM, page 218).  Then the category of models is a topos and and cattheory is the free category generated by the digraph.
  • The sketch is a digraph with some formally commutative diagrams.  Then the models are universal algebras of a specific type with only unary operations (Note 1) and the cattheory is the free category generated by the digraph modulo the commutative diagrams.

In this post I will show how to require sketches to preserve categorical limits, starting with products.

Products

A (binary) product diagram in a category is a cone to {a,b}, in other words a diagram that looks like this

(1)TwistedProductDiagram

with this specific universal property:  For any other cone to {a,b}

NoFiProduct

(2)

there is a unique fill-in arrow fi such that this diagram commutes (see Note 2):

FiProduct

(3)

This diagram has been called a sawhorse. But like most metaphors in math, this name is misleading.  The sawhorse is not symmetrical with respect to its two pairs of legs.  The black legs form a product cone but the blue legs need not be a product diagram. It could be called a directed sawhorse.

Another useful way of thinking about diagram (3)  is that the construction of the fill-in arrow is like an algebraic operation whose domain is the set of diagrams of the form (2) for a fixed product diagram (1)  and whose output is the fill-in arrow.   Now ordinary algebraic operations have domain some cartesian product of sets with output in a set.  For example scalar multiplication of a real vector space is an operation \mathbb{R}\times V\longrightarrow V.  The fill-in arrow is an operation on a set of tuples of arrows, but the domain is not the cartesian products of arrow sets; instead it is an equationally defined subset of a cartesian product of arrow sets.

By making the blue cone also a product diagram you get an instant proof that the resulting fi is an isomorphism.  Thus “products in a category are determined up to a unique isomorphism”.

Reference [1], Chapter 5 gives a detailed explanation of products in categories at a rather elementary level.

Finite products

Finite products of more than two objects in a category can be define analogously.  However, if you assume you have all products of two objects then you automatically get all finite products of two or more elements.  It is an easy exercise to see that every category has all products of one object.  A product of no objects is a terminal object and that has to be assumed separately.  An example of this is the category you get if the singleton groups are untimely ripp’d from the category of groups — it has all finite products but no terminal object.

A category has finite products if there is a product diagram for any finite set of objects.

FP sketches

An FP sketch is a digraph together with some  specified formally commutative diagrams and some specified formal product diagrams.  A model of an FP sketch in a category \mathcal{C} is a functor from the digraph to \mathcal{C} that takes the specified formally commutative diagrams to commutative diagrams and the specified formal product diagrams to product diagrams.

The category of all algebras for any specified type of universal algebra (with finitary operations) is  equivalant to the category of models of an FP sketch.  Chapter 4 of [2] describes an FP theory for the category of groups starting on page 126.

The homomorphisms in the category of models of an FP sketch must preserve the designated product diagrams on the nose.  The sketch for groups just mentioned has three designated formal product cones, for the terminal object, G^2 and G^3This is just a technicality although some mathematicians make a big deal out of it.  In fact when mathematicians talk about the “category of groups” they don’t usually even say which product cone they mean by G^2 and G^3.  There is a neat way to handle this using categories enriched over groupoids, but never mind.

Next: finite limits!

Notes

  1. Universal algebras of a specific type with only unary operations (not even constants allowed) are a topos, but in general universal algebras of a specific type (Birkhoff varieties) do not form a topos.  See Johnstone, P. T., When is a variety a topos? Algebra Universalis 21 (1985), 198–212.
  2. Why O Why does the conversion of these diagrams from PDF to JPEG darken the blue so it doesn’t match the text???

References

  1. Michael Barr and Charles Wells, Category theory for computing science (1999).  Les Publications CRM, Montreal (publication PM023).
  2. Michael Barr and Charles Wells, Toposes, Triples and Theories (2005).  Reprints in Theory and Applications of Categories 1.

Definitions into mathematical objects 3

This is the third post in a series, continuing TDMO1 and TDMO2, aimed at explaining the concept of forms in Graph-Based Logic and Sketches.

Clones and theories

Sketches as I have described them so far can now describe some kinds of universal algebras, namely those with unary operations and equations.  n-ary operations and more elaborate constructions will come in a later post.

The first big construction in universal algebra is that of the clone of a type of algebra (commonly called a signature): a specific set of n-ary operations for various n and specific equations involving those operations.  The clone is essentially all the expressions you can create from the operations, requiring two expressions to be equivalent if you can prove they are equivalent given the equations of the algebra.   (For example, in the clone for semigroups, x(y(xy)) is equivalent to (xy)(xy).  On the other hand, xy is not equivalent to yx because there are noncommutative semigroups, so xy = yx can’t possibly follow from the equations.)

The Lawvere theory of the algebra is a different construction which essentially expresses the clone as a special kind of category, with models of the theory being product-preserving functors.

In model theory a first-order theory is an extension of the concept of clone that allows relations other than equality, as well as the use of negation and quantifiers.  First order theories are constructed in a different way from clones and Lawvere theories but they capture the same general idea in the bigger context.

The cattheory of a sketch

For a sketch, the idea equivalent to the clones and theories just described is that of a cattheory. (This is a new coinage.  See Terminology below.)

Suppose we have a linear sketch \mathcal{S} = (\mathbf{G},D) where G is a digraph and D is a set of formally commutative diagrams.  The cattheory of the linear sketch, denoted by \text{CatTh}(\mathcal{S}), is the free category generated by G with the condition imposed that the diagrams in D must become commutative.    The digraph morphism G:\mathbf{G}\to \text{CatTh}(\mathcal{S}) that takes the nodes and arrows in G to the corresponding objects and arrows of the free category is by definition a model of the sketch \mathcal{S}. G is called the generic model of the sketch.

A model of the cattheory \text{CatTh}(\mathcal{S}) in a category \mathcal{C} is simply a functor.  We don’t have to impose properties on the functor because functors automatically preserve commutative diagrams.  When we get into more complicated structures we will have to add preservation requirements on the model functor.  (See note 1.)

The category of models of the linear sketch \mathcal{S} in a category \mathcal{C} is denoted by \mathbf{Mod}\left( \mathcal{S},\mathcal{C} \right).  The category of models of the cattheory \text{CatTh}(\mathcal{S}) in \mathcal{C} is denoted by \mathbf{Mod}\left( \text{CatTh}(\mathcal{S}),\mathcal{C} \right).

The cattheory has this universal property:

Theorem The map M\mapsto GM:\mathbf{Mod}\left( \mathcal{S},\mathcal{C} \right)\to \mathbf{Mod}\left( \text{CatTh}(\mathcal{S}),\mathcal{C} \right)

is an equivalence of categories. (Note 2).

This theorem forces the cattheory to be determined up to natural equivalence of categories that commutes with the generic model.  For all practical purposes, a model of the sketch is thus the same thing as a model of its cattheory.  This will remain true as we go up the hierarchy of new constructions (n-ary operations, limits and colimits, and other things) and is the defining property of the cattheory.   Clones, Lawvere theories and first order theories are all cattheories up to equivalence.

How to think about cattheories

\text{CatTh}(\mathcal{S})  may be thought of as the minimal category that contains a model of \mathcal{S}, the model being the generic model G. Every model M of \mathcal{S} in any category \mathcal{C} must induce a unique (up to natural isomorphism) model of \text{CatTh}(\mathcal{S}) in \mathcal{C}, simply because everything in \mathcal{S} must be there because any category containing a model of \mathcal{S}  must have everything in \text{CatTh}(\mathcal{S}).

For example, consider the sketch for endofunctions in TDMO2.    Because s is in the graph of the sketch, every power of M(s) must be in any category \mathcal{C} containing a model M of the sketch.  This forces by induction a unique functor (model) from the cattheory of the sketch to \mathcal{C}.  (Usually the induced functor is unique only up to natural isomorphism, but this time it is rilly rilly unique.)

Terminology

These remarks apply in general to all kinds of sketches, not just the restricted version we are considering here.

The situation in the literature is confusing.

  • In [2] and in the other books and articles by Michael Barr and/or me, we call the cattheory the theory.
  • In [3], we refer to the cattheory of a finite limit sketch as a theory or as a categorial theory in an attempt to distinguish it from some version or other of logical theory.  We said “categorial theory” instead of “categorical theory” because the latter phrase means something different to logicians.  Unfortunately, “categorial” means something different to linguists!
  • In [1], Johnstone calls the cattheory of a sketch the syntactic category.
  • In [3], page 33, we refer to SynCat[ f ], where f is a form (generalized sketch).  Now f has a cattheory, but it is not SynCat[ f ], which is the cattheory correspond to the doctrine that f belongs to (the type of categories it can have models in.)

I am using “cattheory” so that I will have a neologism that doesn’t mean anything different to anybody.  Personally, I think we should keep using “theory”, because the theory (syntactic category in the sense of Johnstone) is ultimately the same thing (satisfies the same universal property) as the corresponding logical theory; the difference is only in the construction.

Notes

  1. When we have more structure to talk about in the models, we will have to distinguish which cattheory we are talking about for a sketch.  For the linear sketch \mathcal{S}we will refer to \text{CatTh}(\text{LS}, \mathcal{S}), where “LS” refers to linear sketches.  That is the doctrine this particular sketch belongs to.
  2. You have to say what the map M\mapsto GM:\mathbf{Mod}\left( \mathcal{S},\mathcal{C} \right)\to \mathbf{Mod}\left( \text{CatTh}(\mathcal{S}),\mathcal{C} \right)does to morphisms of models, which are natural transformations (remember the models are functors.)   This is easy.

References

  1. 1. Sketches of an Elephant: A Topos Theory Compendium, Volume 2 (Oxford Logic Guides 44), by Peter T. Johnstone.  Oxford University Press, ISBN 978-0198524960.
  2. 2. Toposes, Triples and Theories (online edition), by Michael Barr and Charles Wells. All references to page numbers refer to the online edition, not to the Springer volume, which should be forgotten forever.
  3. 3. Graph-Based Logic and Sketches, Atish Bagchi and Charles Wells (latest draft September, 2008).

Definitions into mathematical objects 2

Introduction

This post continues the discussion of sketches begun in the post Turning Definitions into Mathematical Objects (TDMO1). This series is building up to an explanation of the ideas in the monograph Graph-Based Logic and Sketches, by Atish Bagchi and me. In the previous post, I introduced the idea of a sketch, which is in its simplest form a directed graph (digraph), and a model of a sketch, which is a functor from the digraph to the category of sets. A morphism of models is then a natural transformation between models.

In TDMO1, I described the sketch for directed graphs. We need another example.

The sketch for an endofunction

Loop

(1)

Let \mathcal{L} be the digraph at the left. It has one node c and one arrow s, whose source and target are (necessarily) c. A model of this sketch is a set C and a function from C to itself. Any such function determines a cyclic semigroup of transformations of C. For later use, I want to mention the the particular model in which C is the set of natural numbers and s is the successor function: this is the free semigroup on one letter.

You may want to experiment with other digraphs as sketches. Any digraph produces a category of models in sets. Each such category is a category of presheaves, hence is a topos ([1], p. 67, Theorem 2.4).

Imposing equations

We need to expand the idea of sketch to be able to define more kinds of structure (see “Specifying more kinds of structure” in TDMO1). Let’s start with equations. Suppose we take the sketch for an endofunction and want to modify it so that s^3=1 in every model in Set. This means we must require that the diagram (in the category of sets) below commute for every model M.

ThreeSTo say that this diagram commutes requires that M(s)\circ M(s)\circ M(s)=\text{id}_{M(c)} (see Note 1.) The obvious way to do this is to say that we require that a model is a functor from the digraph (1) to the category of sets that has the property that the image of the digraph

BareTriangleunder M is a commutative diagram in the category of sets. We say that this digraph is formally commutative. In general, in sketch theory, something is formally P if in every model of the sketch its image is required to be P.

This gives us a more general notion of sketch which allows the specification of equations, although so far only between unary operations. Formally, a linear sketch (\mathbf{G}, \cal{D}) consists of a digraph G together with a set \cal{D} of zero or more formally commutative diagrams. It should be apparent that an linear sketch can specify anything that a universal algebra signature with only unary operations can specify. But linear sketches can specify much more than that because they can specify multisorted algebras.

Models in arbitrary categories

A model in Set of a linear sketch (\mathbf{G}, \cal{D}) is a functor M:\mathbf{G}\rightarrow\textbf{Set} with the property that M takes every diagram in to a commutative diagram in Set.  (Note 2).

This definition would still be meaningful if we replaced Set by any category whatever. So now we can talk about a model of (\mathbf{G}, \cal{D}) in any category C. For example, a model in the category of groups of the endofunction sketch above that requires the cube to be the identity function is simply a group with a specified automorphism of order 1 or 3. Indeed, in any category of structures of a certain type, a model is a structure of that type with a specified automorphism of order 1 or 3.

The more elaborate sketches we construct later will still allow models in any category. For example, a model of the sketch for groups (see reference [1], starting on page 126) in the category of Hausdorff spaces is precisely a Hausdorff topological group. Ancient cute theorem: A model of the sketch for groups in the category of groups is an Abelian group. That’s because the group operations must be homomorphisms!

Next we will look at what corresponds in universal algebra to clones.

Notes

1. Saying exactly what “this diagram commutes” means for any particular  exhibited diagram requires fussiness. Chapter 2 of GBLS goes into excruciating detail about this.

2. A model of a linear sketch in the category of sets need not be a topos.

3. A model of a digraph (sketch without equations) in an arbitrary category is not in general a topos.  But a model of a digraph in a topos is a topos.

References

[1] Michael Barr and Charles Wells, Toposes, Triples and Theories. All references to page numbers refer to the online edition, not to the Springer volume, which should be forgotten forever.

[2] Atish Bagchi and Charles Wells, Graph-Based Logic and Sketches.

[3] Charles Wells, Sketches: Outline with references. Warning: This paper contains errors and omissions and will be revised Real Soon Now.

Handbook now online

I have placed an interactive version of the Handbook of Mathematical Discourse on line here. Its formatting is still a little rough, and it omits the quotations and illustrations from the printed book. It also needs the backlinks from the citations and bibliography reactivated. I will do that when I Get Around To It.

Now I can refer to the Handbook via a direct link from a blog post or from abstractmath, and you can click on a lexicographical citation and go directly to the text of the citation.

Comments and error reports are welcome.

Turning definitions into mathematical objects

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.   directedgraph 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 textsf{source:}Arightarrow N and textsf{target:}Arightarrow N.

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

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

parallelpair2A 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 categorymathcal{C} consists of objects M(N) and M(A) of mathcal{C} and morphisms M(s):M(A)rightarrow M(N) and M(t):M(A)rightarrow M(N) of mathcal{C}.

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 M_1 to M_2 is a pair of functions alpha_N:M_1(N)rightarrow M_2(N) and alpha_A:M_1(A)rightarrow M_2(A) for which these diagrams commute:

naturality If you chase these diagrams you will discover that they say both these things:

(A) alpha is a morphism of directed graphs.

(B) alpha is a natural transformation from M_1 to M_2.

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 0neq 1), 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.

Follow

Get every new post delivered to your Inbox.