Now on ScienceBlogs: Let the War on Christmas being. Atheist style.

Seed Media Group

Collective Imagination

Good Math, Bad Math

Finding the fun in good math; Shredding bad math and squashing the crackpots who espouse it.

Search

Profile

markcc.jpg
Mark Chu-Carroll (aka MarkCC) is a PhD Computer Scientist, who works for Google as a Software Engineer. My professional interests center on programming languages and tools, and how to improve the languages and tools that are used for building complex software systems.

Donors Choose

Other Information

Add this blog to my Technorati Favorites!

Recent Posts

Recent Comments

Categories

Blogroll

Old Topic Indices

Great Online Books

« Really Silly Wine Woo | Main | Big to Small, Small to Big: Topological Properties through Sheaves (part 2) »

Big to Small, Small to Big: Topological Properties through Sheaves (part 1)

Category: category theorytopology
Posted on: December 12, 2006 5:19 PM, by Mark C. Chu-Carroll

Suppose we've got a topological space. So far, in our discussion of topology, we've tended to focus either very narrowly on local properties of T (as in manifolds, where locally, the space appears euclidean), or on global properties of T. We haven't done much to connect those two views. How do we get from local properties to global properties?

One of the tools for doing that is a sheaf (plural "sheaves"). 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.

As I said, 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 F of sets on a topological space T can be defined in terms of the category Set of sets as:

  • ∀ open set O ∈ T, the sheaf has a mapping F(O) ∈ Obj(Set) to an object in the category of sets.
  • ∀ open sets N,O ∈ T where N ⊆ O, a morphism ρN,O : F(O) → F(N) in Set, called a restriction morphism, which must have the following properties:
    • ∀ open set M ∈ T, ρM,M = idF(M). (The restriction morphism must be the identity morphism if N=O.)
    • ∀ open sets M, N, O ∈ T: ρM,N º ρN,O = ρM,O. *(The mapping to restriction morphisms must compose properly.)

The restriction morphisms are the really important thing in that definition. What we're doing with the presheaf is providing a way of taking some statement about T as a whole, and providing a way of restricting it to one of the open sets of T. The properties of the restriction morphisms basically say (1) if you restrict a subset to itself, none of its properties change; and (2) if you restrict from the space down to an open set N, and then restrict the results of that down to a smaller open space M, you end up with the same property as if you restricted directly to M without going through N. So we've got a structure-preserving mapping that allows us to view properties of small parts of T.

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.

To remind you (or in case you're a new reader who didn't read my posts on category theory), I'll quickly review the definition of functor (or you can go back and look at my original post on functors):

Suppose you've got two categories, C and D. A (covariant) functor F from C to D is a mapping that associates every object o in C with an object F(o) in D; and each morphism m : x → y in C with a morphism F(M) : F(x) → F(y) in D. The functor mapping F must preserve the composition structure of C, meaning that ∀ o ∈ Obj(C), F(ido) = idF(o); and ∀ f : x → y, g : y → z ∈ C, F(g º f) = F(g) º F(f).

A contravariant functor is the same thing, except that the second property of the morphism mapping, which defines how the structure of composition is preserved is reversed: ∀ f : x → y, g : y → z ∈ C, F(gºf) = F(f) º F(g). To understand this, think of the normal way that composition works in categories (or in functions); a contravariant functor reverses 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 m from f to g in a category will compose with arrows from g 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 m ends. But it doesn't say anything about what happens when the morphism is composed with something that ends where m 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 A, every function f : AB will be mapped to a function whose results are acceptable as inputs to the mappings of things that that used to compose with f. 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, in some sense, 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 S, we can define a category over the open sets of S, TopS, where the objects in the category are the open sets of S, and where for any two objects a,b ∈ S, there is an arrow from a to b if/f a ⊆ b. Now, take a category, C, 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 TopS to C.

The neat thing about this is that the presheaf is supposed to include restricting morphisms. The contravariant functor from TopS to C guarantees that moving to subsets will restrict the values in C. 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 :-)

Share this: Stumbleupon Reddit Email + More

Comments

1

To explore the category theory a little further: once you've seen that a sheaf on a topological space is just a functor (presheaf) which respects certain limits (gluing properties I'm assuming will be described in a later post) there's no reason the course category has to be the poset of subspaces of a topological space. All you need is a coherent sense of what it means for a collection of subspaces to "cover" another space.

Okay, a subspace of a topological space can be identified with the continuous map from the subspace into the whole space. That is, we aren't really dealing with collections of subspaces, we're dealing with collections of morphisms. Now if we've got any category and a notion of which collections of morphisms with a common target X "cover" a given morphism with source X, we call the notion of covering a "Grothendieck topology", and a category with a Grothendieck topology is a "site".

So for any site C, we can consider which presheaves on C (functors from Cop) are sheaves by mimicking the gluing properties for a sheaf on a topological space.

Now the really cool thing is that there's a category of such sheaves! Since the sheaves are special kinds of functors, the morphisms of sheaves are natural transformations of functors. (exercise: work out what a morphism of presheaves of sets on a topological space should look like)

Not only that, the category has extra structure making it into something we call a "topos": there are nice notions of limits -- in particular there are products of sheaves. There's a notion of the sheaf of morphisms between two sheaves, not just a set of them. There's even something technical called the "subobject classifier" floating around. Why do we care? Because these are all things that we have in the category of sets. We can do logic on Sh(C) just like we can do it in Set. Topoi are, in particular, Cartesian closed, which means they give Lambda calculi!

Posted by: John Armstrong | December 12, 2006 6:08 PM

2

n.b.: evidently the "sup" tag is disabled. "Cop" above should be C^{op}.

Posted by: John Armstrong | December 12, 2006 6:09 PM

3

There is an interesting paper linking big and small through 'Cartan-type gauge theory' by
Derek K Wise, 'MacDowell-Mansouri gravity and Cartan geometry [34 pages, 5 figures]
http://arxiv.org/abs/gr-qc/0611154

More discussion at 'Helpful new paper by Derek Wise' on Physics Forums.
http://www.physicsforums.com/showthread.php?t=146142

Posted by: Doug | December 13, 2006 8:17 AM

4

Hi Mark, I've been meaning to read up on category theory for a while now, and I was wondering whether you (or any of your readers) would recommend any particular book(s) on the subject? A quick Amazon search turns up a whole bunch, and it's hard to know which are particularly good. Being a computer scientist, I'm preferably looking for something coming from the computer science point of view (although not at the price of sacrificing mathematical rigor -- I'd rather have a solid, non-CS book on category theory than a watered-down CS one, if that makes sense).

Thanks! (and BTW, I love your blog. =)

Posted by: Brent | December 13, 2006 11:48 AM

5

Brent:

That's a question that I've been asked a lot. Unfortunately, I haven't found a book that I liked. "Category Theory for the Working Computer Scientist" is OK as far as it goes, but the problem is, it doesn't go nearly far enough. The classic text for computer scientists is the book by Asperti and Longo, but I find it almost impenetrable. And that seems to be the pattern: the books on cat theory seem to be either very shallow, not covering enough material in enough depth; or they're the incredibly formal kind of math text that's very hard to follow, and doesn't do nearly enough to give you any intuition about *why* any of it matters.

Posted by: Mark C. Chu-Carroll | December 13, 2006 11:57 AM

6

MarkCC mourned:

That's a question that I've been asked a lot. Unfortunately, I haven't found a book that I liked.

The solution should be trivially obvious to the most casual observer. It's time to write a textbook.

(-;

Posted by: Blake Stacey | December 13, 2006 12:38 PM

7

Blake:

I'll admit that the thought of writing a book has crossed my mind more than once. :-) But writing a book takes a huge amount of time, much more time than writing this blog, and I don't think that even if I were to give up the blog (which I have no intention of doing) that my real job would leave me with enough time to do a book.

On the other hand, I probably will try to collect up material from the blog into a book at some point. (Anyone who knows a publisher (a real publisher, not a scammy self-publisher like PA) who might be interested, feel free to let me know.)

Posted by: Mark C. Chu-Carroll | December 13, 2006 12:59 PM

8

A minor quibble:

A contravariant functor is the same thing, except that the second property of the morphism mapping, which defines how the structure of composition is preserved is reversed: ∀ f : x → y, g : y → z ∈ C, F(gºf) = F(f) º F(g).
Should probably be:
A contravariant functor is the same thing, except that it associates every morphism m: x → y in C with a morphism F(M) : F(y) → F(x) in D. This also means that second property of the morphism mapping, which defines how the structure of composition is preserved, is reversed: ∀ f : x → y, g : y → z ∈ C, F(gºf) = F(f) º F(g).

You can't really reverse the composition property without first reversing the direction of the arrows.

Posted by: Daniel Martin | December 13, 2006 1:17 PM

9

MarkCC:

I'll admit that the thought of writing a book has crossed my mind more than once. :-) But writing a book takes a huge amount of time, much more time than writing this blog, and I don't think that even if I were to give up the blog (which I have no intention of doing) that my real job would leave me with enough time to do a book.

Glad to hear that GM/BM will keep going! :-)

On the other hand, I probably will try to collect up material from the blog into a book at some point. (Anyone who knows a publisher (a real publisher, not a scammy self-publisher like PA) who might be interested, feel free to let me know.

In connection with this, that and the other, I've actually done a little work on seeing how easily a content-rich blog can be turned into something resembling a book. When I'm done with my feasibility tests, I might have good news.

I assume that "PA" = "PublishAmerica" (as described here in the Washington Post)? Yikes — we should certainly be able to find better than that. (Interestingly, the Lulu people, who are at least honest about their self-publishing nature, is sponsoring a "Blooker Prize" for the best "blook", i.e., book made from a blog. Sure, it's a marketing scheme, but it's also a neat idea.)

Posted by: Blake Stacey | December 13, 2006 2:06 PM

10

The "Grothendieck topology" that John Armstrong mentions is explained at wikipedia at length, beginning:
http://en.wikipedia.org/wiki/Grothendieck_topology

"In category theory, a branch of mathematics, a Grothendieck topology is a structure on a category C which makes the objects of C act like the open sets of a topological space. Grothendieck topologies axiomatize the notion of an open cover. Using the notion of covering provided by a Grothendieck topology, it becomes possible to define sheaves on a category and their cohomology. This was first done in algebraic geometry and algebraic number theory by Alexandre Grothendieck to define the étale cohomology of a scheme. It has been used to define many other cohomology theories since then, such as l-adic cohomology, flat cohomology, and crystalline cohomology. While Grothendieck topologies are most often used to define cohomology theories, they have found other applications as well, such as to John Tate's theory of rigid analytic geometry."

"Grothendieck topologies are not comparable to the classical notion of topological spaces. While it is possible to interpret sober spaces in terms of Grothendieck topologies, more pathological spaces have no such representation. Conversely, not all Grothendieck topologies correspond to topological spaces."

Wikipedia goes over the history (starting with Andre Weil), sites, sheaves, Zariski, examples, references.

At a higher level, see also:
Topological representation of sheaf cohomology of sites, by Carsten Butz and Ieke Moerdijk
http://www.math.uiuc.edu/K-theory/0201/

And as to the application in Logic, which Mark may well be leading us towards, see:
TOPOLOGICAL SEMANTICS FOR FIRST-ORDER MODAL LOGIC
http://www.pitt.edu/~kok6/work/pdf/060520.pdf

Grothendieck himself was a bizarre and amazing genius. At the height of his fame, he completely dropped out of Mathematics to take up leftist politics in France, where he was active and influential, having started from total ignorance even if what an election accomplishes in France.

He is the rare example of a Mathematician who almost always solved things by making them more generalized, whereas most people narrow things down to specifics. But it was not generality for its own sake, but in ways that had fascinating theorems on structure, structure of structure, and so forth.

Posted by: Jonathan Vos Post | December 13, 2006 2:10 PM

11

Mark:

Thanks for the response. Maybe I'll get a couple different books to start and refer to both. Or something.

If you did write a book, I'd definitely buy it, but I certainly understand how much work that would be! Maybe I'll write one instead. ;)

Posted by: Brent | December 13, 2006 3:07 PM

12

I am a mathematician, not a computer scientist (so I actually liked CFTWM), but I have heard good things about:

Category Theory in four easy movements
http://www.cs.man.ac.uk/~hsimmons/BOOKS/CatTheory.pdf

and

Category Theory as Coherently Contructive Lattice Theory
http://citeseer.ist.psu.edu/cache/papers/cs/12973/http:zSzzSzwww.cs.nott.ac.ukzSz~rcbzSzpaperszSz..zSzMPCzSzCatTheory.pdf/backhouse98category.pdf

Posted by: michael | December 21, 2006 5:37 PM

13

From a programmer's perspective, some texts I've found useful are;
"Conceptual Mathematics: A first introduction to Categories" by Bill Lawvere et al. - this is a magnificent introduction, which is big on didactic teaching and concrete examples. A very easy read, suitable for covering the basic issues.

"Category Theory for Computing Science" by Michael Barr and Charles Wells, which I found very clear and well written, with an emphasis on computation.

One text which is describes itself as a bridge to the classic work "Categories for the Working Mathematician", is "Arrows, Structures, and Functors: The Categorical Imperative" by Michael Arbib, which covers both the nuts-and-bolts of Categories with applications in many different domains of Mathematics.

Posted by: Stuart | January 6, 2007 8:02 PM

Post a Comment

(Email is required for authentication purposes only. On some blogs, comments are moderated for spam, so your comment may not appear immediately.)






Stats

ScienceBlogs

Search ScienceBlogs:

Go to:

Advertisement
Enter to win a free copy of The Monty Hall Problem
Visit the Collective Imagination blog
Advertisement
Collective Imagination

© 2006-2009 Seed Media Group LLC. ScienceBlogs is a registered trademark of Seed Media Group. All rights reserved.

Sites by Seed Media Group: Seed Media Group | ScienceBlogs | SEEDMAGAZINE.COM