“His sheaf was neither miserly nor spiteful”

Over at the Weblog, Dominic Fox recently had a thought-provoking post about the application of category theory to relationships of a nonmathematical kind. I’ve been on tenterhooks with that crew, stemming from semi-advertently insulting the virtue, breeding, and manners of the estimable Infinite Thought; but I think some analyses are terminable, and so I’m going to give my version of category-theoretic romance. This isn’t the first time categories have turned up in the Rubardian corpus: “Between Beck and Chuck D: The Performativity of Male Heterosexuality” (the title being a simultaneous homage to Habermas and slash fiction) used some concepts gleaned from Saunders MacLane. Adjoint functors were addressed, though in a slightly lower register than Fox’s, and there’s a sidelong reference to Beck’s theorem for you pervs: but in general it’s a picture of me five years ago, casting around for whatever formal concept could be integrated into a critical-theoretic joke, and there’s something more serious to be said.

In this post I’m going to develop a hierarchy of categorical models with increasing expressive resources for representing logical structure: the major point of reference is Robert Goldblatt’s Topoi: The Categorical Analysis of Logic (now available in an inexpensive Dover edition and online at the Historical Math Monographs), though of course he shouldn’t be held responsible for what I’ve done with his ideas. Let’s begin with the basic components of any categorical analysis: objects and arrows with identity and composition. An object can be any mathematical entity, and an arrow any mathematical transformation from one object to another: but for a collection of objects and arrows to form a category there must be identity arrows which map an object onto itself and a rule for composition of arrows which regulates the equivalence of “paths” utilizing multiple arrows in a category diagram. (Since I still haven’t learned TeX there will be no diagrams in this post, but I expect the reader will find “abstract nonsense” enough).

What can you do with this basic set-up? Comprehend mathematical “morphisms” or transformations which one might find in analysis, topology, or algebra — including Boolean “truth-functions” such as form the stuff of propositional logic. A Boolean algebra contains two objects, the truth-values 0 (“false”) and 1 ( “true”), and the functions of inversion (equivalent to logical negation), union (equivalent to logical disjunction), and intersection (equivalent to logical conjunction). These functions can be modeled as arrows, with the resulting category being a “preorder” or partially ordered category: in this category 0 is the “initial object” and 1 the “terminal” or “final” object, since there is only one morphism from 0 to 1 and one morphism from 1 to 0 (negation) — and every element of the algebra has a truth-value which is greater than, less than, or equal to any given other.

Union/conjunction is modeled using the category-theoretic notion of “product”. In the overarching category Set product is the Cartesian product formed by the set of ordered pairs, with “projection morphisms” that produce the first or second element out of an ordered pair. But in the more limited purview of Boolean algebra product is the the greatest lower bound (the lowest value found in the two conjuncts) and coproduct the lowest upper bound (the highest value found in the two disjuncts). Now, “propositional logic” might seem like an obvious candidate for a funny interpretation, but obvious it would be; we should probably ask what real meaning “zero-order” logic has for the topic of romance — let’s not cheat just yet.

Boolean algebras are equivalent in expressive power to the finite state automata (“finite state machines”) of computation theory, finite automata having been invented in 1948 by McCulloch and Pitts to model “neural nets” processing statements of propositonal logic. The CS geeks all know that FSMs “accept” or reject regular expressions, which are the set of possible strings formed from an alphabet which could be as simple as 0 and 1 by operations of concatenation (where one symbol must follow another), alternation (where either of two symbols can appear in a certain position) and the Kleene “star” operator (which indicates that a set of symbols can be repeated as many times as one likes). The keener-eyed among you have noticed that there are three operations: since we know that FSMs and BAs are equivalent, how do they map onto the logical connectives? The answer is that they don’t, exactly: they’re “duals” of the propositional connectives, since the Kleene star, which indicates a set of symbols can be repeated indefinitely, is the “opposite” of negation, which indicates a statement may not be asserted even once (conjunction and disjunction are already duals of each other, so their mapping onto concatenation and alternation is relatively straightforward).

What do finite state automata let you do? They let you parse things, for example determining whether a statement in a program is well-formed. What can’t they do? They can’t handle recursion. But there’s a very simple addition we can make to the preorder category that gives us that expressive ability. If we add exponentiation (also known as “power objects” or “function objects”), we get what is known as a “cartesian closed category”. Like the preorder category, cartesian closed categories have terminal objects and product morphisms: exponentiation adds the ability to map the power set of objects to an object, and an object and a function to the power set. These operations are category-theoretic equivalents of application and abstraction of “curried” functions in the lambda calculus, and on account of this Cartesian closed categories are commonly used as models for programming languages.

Dr. Thought asked Dominic about relations in connection with his post, and this is quite insightful: although monadic predicate logic can be modeled in a Cartesian closed category (being decidable), relations cannot. To have a category-theoretic model of first-order logic, we add “subobject classifiers” to Cartesian closed categories and get a topos. A subobject is a generalization of the concept of subset: the subobjects of an object are equivalent to morphisms to a subobject classifier. This is like the definition of predicates and relations in Tarskian model theory, a “characteristic function” which maps collections (ordered pairs, triples, etc.) of constants in the universe of discourse onto truth (1) or falsity (0); and indeed toposes can be used to model first-order logic. To keep up the connection to computability theory, the truths of first-order logic are not recursive (decidable) but they are recursively enumerable — there is a mechanical test for first-order validity, just not first-order invalidity. What happens when we go beyond that?

To answer that question, we’re going to have to return to more purely category-theoretic concepts and introduce the notion of a sheaf. In topology, an open set is one with limit points outside that set: in other words, it reaches right up to the limit (as in the “lesser than” operation) without actually including it (that would be a “closed” set). A pre-sheaf takes a partially ordered series of open sets and assigns an object from a category F to each one; it becomes a sheaf when a terminal object F(Ø) and a “gluing axiom” is added. The gluing axiom is related to the topological concept of “covering”; subsets of an open set “cover” that set if it can be reconstructed out of them. The gluing axiom states that an object F(U) is constructed out of “restrictions” to compatible elements in the covering set; that is, the global character of the object is determined by the “local” character of the elements it depends on.

For that reason, toposes with the extra structure imposed by a sheaf on a topology (Grothendieck topoi) are very suitable for modeling logics which depend on the local validity of statements: modal logics, where the necessity of a statement is a function of its truth in all possible worlds, and intuitionistic logics, where the truth of a statement is a function of the information available at a point in reasoning (what has already been proven). The Kripke-Joyal semantics for intuitionistic logic is a famous application of sheaves to render Kripke’s semantics for intuitionistic logic in a category-theoretic framework, but the point about local validity is more general than that (I am given to understand that this property of sheaves plays an important role in Badiou’s Logics of Worlds, but being rather innocent of both French and the appropriate bibliotheques I don’t know for sure). With the introduction of this structure, though, we go from logics which are undecidable but complete (classical first-order logics) to ones which are incomplete (intuitionistic predicate logic, second-order logic).

That concludes the introduction of the “categorical hierarchy”, which I have shown has not a little relation to the Kleene-Mostowski or “arithmetical” hierarchy in recursion theory; what does it mean for relationships? Well, category theory doesn’t really allow you to do more mathematics than set theory; there are many analogues between categorical definitions and set-theoretical ones (identity is like equality, adjunction is like equipollence, and so on). The power category theory offers us, perhaps unsurprisingly given its origins in homological algebra, is the ability to describe similarities and interrelations between levels of structure whose set-theoretical definitions are difficult to conceptually compare: for example, the “forgetful functor” that collapses the structure of a group into its base set, or the “faithful functor” which preserves structure while mapping into a more complex category.

And by golly, the concepts have funny names, but the point of the triple development in terms of categories, logics and recursion theory is this: there is a correspondence between the structure of whatever we are interested in, the language we use to talk about it, and the plans we make for dealing with it — and the more complicated any of those elements get, the more complicated the corresponding elements get (often with undesirable results, like undecidability and incompleteness). “Mathematization” can’t really simplify elements of reality without a cost, or “save the appearances” without creating some confusion. How could that not have a bearing on relationships, which really involve almost everything? (I suppose that’s a little anticlimactic: so regarding the second part of Mr. Fox’s post, I will mention I think the Young Fresh Fellows said it best and throw in their “Amy Grant” as a token of my respect towards religion.)