I’m in the process of changing jobs. As a result of that, I’ve actually got some time between leaving the old, and starting the new. So I’ve been trying to look into Topoi. Topoi are, basically, an alternative formulation of mathematical logic. In most common presentations of logic, set theory is used as the underlying mathematical basis – set theory and a mathematical logic built alongside it provide a complete foundational structure for mathematics.

Topoi is a different approach. Instead of starting with set theory and a logic with set theoretic semantics, Topoi starts with *categories*. (I’ve done a bunch of writing about categories before: see the archives for my category theory posts.)

Reading about Topoi is rough going. The references I’ve found so far are seriously rough going. So instead of diving right in, I’m going to take a couple of steps back, to some of the foundational material that I think helps make it easier to see where the category theory is coming from. (As a general statement, I find that category theory is fascinating, but it’s so abstract that you really need to do some work to ground it in a way that makes sense. Even then, it’s not easy to grasp, but it’s worth the effort!)

A lot of category theoretic concepts originated in algebraic topology. Topoi follows that – one of its foundational concepts is related to the topological idea of a *sheaf*. So we’re going to start by looking at what a sheaf is.

Suppose we’ve got a topological space. A topological space is, intuitively, a collection of objects called *points*, and a relationship that defines “nearness”. If you pick any point in the space, then you can define an ever-expanding circle of *neighborhoods*, where being in a neighborhood of a point means, roughly, that you’re *no further* from that point than any of the other points in the neighborhood. There’s a lot more to it than that, but that’s a good intuitive start.

In basic topology, we mostly focus either vary narrowly on local properties of a topological space (for example, when we study manifolds, which are objects that on a small, local scale look like they’re euclidean, even though on a large scale, they may not be), or they focus on global properties of the entire space. Sheafs are a mechanism that can allow us to bridge those two disparate universes, and find the connection between the local view and the global view.

A sheaf is a very general kind of structure that provides ways of mapping or relating local information about a topological space to global information about that space. There are many different kinds of sheaves; rather than being exhaustive, I’ll pretty much stick to a simple sheaf of functions on the topological space. Sheaves show up *all over* the place, in everything from abstract algebra to algebraic geometry to number theory to analysis to differential calculus – pretty much every major abstract area of mathematics uses sheaves.

Since what I’m ultimately interested in Topoi, I’m going to stick to a simple categorical definition of a sheaf of continuous functions on a topological space. To figure out what a sheaf is, we’ll start with something weaker: a *presheaf*.

A *presheaf* of sets on a topological space can be defined in terms of the category of sets as:

- , the presheaf has a mapping to an object in the category of sets. That is, we’ve got some way of mapping from the open sets (that is, collections of neigborhoods in the topological space) to objects in the category of sets. What that means is that we’ve got a way of talking about the open sets of a topological space using the category of sets.
- , the presheaf contains a morphism which goes from , called a
*restriction morphism*, which must have the following properties.- . (The restriction morphism from any open set to itself must be identity.)
- . (The mapping to restriction morphisms must compose properly.)

That’s one hell of a mouthful, so let’s pick it apart a bit.

The restriction morphisms are the important thing in the definition. What we’re doing with the presheaf is providing a way of taking some statement about as a whole, and providing a way of *restricting* it to one of the open sets of .

The properties of the restriction morphisms basically say:

- if you restrict a subset to itself, none of its properties change;
- if you restrict from the space down to an open set , and then restrict the results of that down to a
*smaller*open space , you end up with the same property as if you restricted directly to without going through . So if we want to look at the properties of an open set, it doesn’t matter whether we restrict things to it in one step, or if we do it gradually in a series of steps: the result will be exactly the same.

So, basically, we’ve got a mapping from open sets in a space to sets, and that mapping is guaranteed to preserve the structure of the topological space. Why should we care about that? Because we can map it to sets that describe things about the space in ways that are easier to understand that the space itself. Topological spaces can be nightmarish beasts to work with; we can instead look at simpler sets. But because the presheaf gives us a mapping to the simpler sets that’s guaranteed to keep the structure of the topological space, we can safely work with the simpler objects.

There’s also another way of describing a presheaf in terms of category theory which I hadn’t seen before, but which I discovered via Wolfram’s Mathworld while I was researching this post. It’s based on the idea of *contravariant functors*.

This is going to get a bit dense, but bear with me. It does, eventually, make sense.

We’ll start with a quick reminder of what a functor is. For a bit more depth, you could look here.

A category is basically a collection of objects that are connected by arrows, called morphisms. There are a bunch of rules about how the morphisms in a category work – but the basic idea is that you’ve got objects and arrows, and the structure of the category is described by the ways that the objects are connected by the arrows. For example, in the category of sets, the objects are sets, and arrows between objects represent functions.

A functor is a structure-preserving mapping from one category to another. Since the structure is expressed by the arrows, what that means is that the functor maps arrows in a way that preserves the structural relationships of those arrows. To be more precise:

Suppose you’ve got two categories, and . A covariant functor from to consists of:

- A mapping from each object to an object .
- A mapping from each morphism to a morphism .

This mapping must preserve the composition structure of – meaning that:

- – that is, every identity arrow of an object in is mapped to an identity arrow in of the corresponding object in ;
- – if you compose and in , and then map it to using the functor, you get the same result as if you first mapped and to arrows in , and then applied the functor. So they compose the same way in both categories.

A normal functor like this is called a *covariant* functor. For presheafs, we want *contravariant* functors. A contravariant functor is almost the same thing, except that the structural preservation property is *reversed*: .

To understand this, think of the normal way that composition works in categories (or in functions); a contravariant functor *reverses* the direction of composition. One way of looking at that is to say that that the normal functor preserves structure by making all of the composition relations work normally – an arrow from to in a category will compose with arrows from to something else after applying the functor. So in some sense, when it maps a morphism, it’s preserving the relations with other morphisms that *start* where ends. But it doesn’t say anything about what happens when the morphism is composed with something that *ends* where *starts*. A contravariant functor does the opposite; it makes sure that through its transformation, the arrow composes properly with everything that ends where it starts, but doesn’t care about the other way.

To get what that means, you can think of it in terms of the category **Set** of sets and functions between them. A functor from **Set** to **Set** maps objects to objects, and functions to functions. A *covariant* functor says that for a set , every function will be mapped to a function *whose results* are acceptable as inputs to the mappings of things that used to compose with f.

It does *not* say anything about how the mapping of will composite with things that used to provide valid *inputs* to . The covariant functor can therefore be thought of as constraining the *output* of the function. The contravariant function does the opposite; it constrains the *input*.

Anyway – the point of that little diversion was to let us see an equivalent simpler definition of the presheaf, which works for presheafs of all of the different kinds of sheaves. Given a topological space , we can define a category over the open sets of , , where the objects in the category are the open sets of , and where for any two objects , there is an arrow if/f .

Now, take a category, , which which contains the values that you want the presheaf to operate over (which would be **Set** in the definition above); the presheaf is just a contravariant functor from to .

The neat thing about this is that the presheaf is supposed to include *restricting* morphisms. The contravariant functor from to guarantees that moving to subsets will *restrict* the values in . That is, if you constrain the input to a function by only giving it a subset, it will behave correctly; it will restrict the output the same way that the input was restricted. So we’ve effectively found all of those restriction morphism embodied in the structure of the contravariant functor. I thought that was pretty nifty. It’s a nice example of what I think is interesting about category theory. Category theory takes a lot of effort to absorb – but once you do, you find lots of complicated ideas can be expressed very simply. You need to learn all of that morphism stuff – but if you do that once, you’ll keep get rewarded for it, because so many things become easier.

SophieYou also need to turn around the morphisms for the contravariant funktor. A morphism m : x->y will be mapped to F(m) : F(y)->F(x).

SeanI don’t think this makes sense:

“It does not say anything about how the mapping of f will composite with things that used to provide valid inputs to f. The covariant functor can therefore be thought of as constraining the output of the function. The contravariant function does the opposite; it constrains the input.”

For example if F is a covariant functor, and f:a->b, and g:c->a are morphisms in the category where F acts, then

F(f circ g) = F(f) circ F(g).

Isn’t that providing information about how F(f) behaves vis-a-vis things that provide inputs to f (i.e. g). Or am I missing something?

Jonathan DIt looks like you’ve got thoroughly mixed up, taking the fact that restriction morphisms correspond to (i.e. are the mappping of) restrictions in the topological space, and trying to equate that to some sort of restriction elsewhere.

The difference between covariant and contravariant functors is nothing to do with constraining inputs rather than outputs and everything to do with what Sophie points out you omitted – a contravariant functor turns the morphisms round in the other direction. The composition reversal is simply part of this – there’s only one way you can compose F(g):F(z)->F(y) and F(f):F(y)->F(z).

If our morphisms are functions, then reversing the arrows swaps inputs for outputs, but, as Sean suggests, your comments about inputs and outputs don’t make any sense while we’re talking about the preservation of composition property. That just tells us that we get the same result whether we compose before or after applying the functor. Anything more fundamental than that (restricting results so that composition is possible) comes from the definitions of F(f) and a category itself.

The presheaf could just easily be described as a covariant functor, if we start with the opposite of our original category – that is, the one with a single arrow a->b iff a contains b rather than is included in it. Probably the ony reason to choose the category you have is because although you didn’t describe it this way, it is concrete – the morphisms can be simply the inclusion maps.

I agree that it’s nifty to sum up the presheaf definition in categorical language, but restriction morphisms aren’t embodied in the structure of a contravariant functor so much as guaranteed by taking a functor from a category with the relevant structure, which just happens to be defined back-to-front. There’s no need to make it sound much more complicated than the original definition!

DanIn addition to looking at topoi from their topological roots, you may also want to take a more axiomatic approach by studying “elementary topos theory” – there are a lot of good introductions and lecture notes out there that take this perspective. If I was between jobs and trying to learn about topoi, I would probably try to approach from both these sides. Good luck!