Patrick Stevens bio photo

Patrick Stevens

Former mathematics student at the University of Cambridge; now a software engineer.

Email Twitter Github Stackoverflow

Now we come to Chapter 6 of Awodey, on exponentials, pages 119 through 128. Supposedly, this represents a kind of universal property which is not of the form “for every arrow which makes this diagram commute, that arrow factors through this one”.

First, we define the currying of a function , producting a function - that is, a function . That is, we view , defining an isomorphism of homsets to .

Now, we try to generalise this construction, by generalising the “currying” construct to allow for more kinds of evaluation. We just need a way to take in a universal way. The resulting diagram is perhaps not something I could have come up with, but it is extremely reminiscent of the UMP of the free monoid.

The general definition of an exponential is then “a way of currying”, defined in terms of “a way of evaluating”. We get some terminology - the “evaluation” is the way of evaluating, and the “transpose” of an arrow is the curried form. We can also define the transpose of a curried arrow, by giving it a way of evaluating on any input; the UMP tells us that if we transpose twice, we recover the original arrow; therefore, the “curry me” operation is an isomorphism between and . (This is all probably very harmful, thinking of this in terms of currying, but so far I think it is helping.)

A category is then Cartesian closed if it has all finite products and exponentials. That is, if we can define multi-variable functions which curry. (Yes, arrows are usually not functions. This is for my beginner’s intuition.)

Then Example 6.4, showing that the product of two posets is a poset, and defining the exponential to be the Sets-exponential but with the pointwise ordering on arrows. There is work to do to show that the evaluation is an arrow and that the transpose of an arrow is an arrow.

Restricting to CPOs, we still need to show that is an CPO. Indeed, given an -chain in , we need to find an upper bound in . Say the chain was . Then for each , the chain with members has a least upper bound . This defines an order-preserving function because if then each , and weak inequalities respect the limiting operation. Therefore our prospective exponential is in fact in the category.

needs to be -continuous: it needs to respect least upper bounds. Let be an -chain in . (I’ll take it as read that products exist.) We need that evaluating the least upper bound, , yields the limit of . This follows from the lemma that if the LUB of is , and of is , then the least upper bound of is (which is true: it is an upper bound, while any other upper bound is bigger than it). Then while , so we do get the result: each because , while any other upper bound would have all so (fixing ) all , so all , so (releasing ) .

Finally, the transpose of an -continuous function needs to be -continuous: let be -continuous. Its transpose is given by . If weren’t -continuous, there would be a witness sequence which had ; plugging this into the definition of gives that is a witness against the -continuity of . Contradiction.

And now for something completely different: an exponential with more structure than previously. I just check the definition of the product graph, because I don’t think we had it in our Graph Theory course; it seems to be the obvious one, taking pairs of vertices and corresponding pairs of edges. Then the exponential graph. This is defined as to have vertices “set-exponential of the vertices”, and an edge between , is a -indexed collection of edges in which have “the source is where takes the corresponding -source” and “the target is where takes the corresponding -target”. It’s a way of embedding into along and .

The evaluation is the obvious one given those structures, and the transpose of a map is the curried version of that map. The different thing about this system is the fact that our maps have to have two parts (one for vertices and one for edges).

“Basic facts about exponentials”. The transpose of evaluation, without looking at the rest of the page: must transpose to with . If were monic, we could say that immediately, but it’s not monic. Ah, but we do have that is uniquely specified by the UMP, so it must be after all. Maybe that’ll help me remember things, if nothing else.

A proof that “exponentiation by a fixed object” is a functor: it starts in Set, which makes me worry that representable functors are going to be involved again (because we seem to be able to cast many things as Set-based things). Onwards: currying is certainly functorial in Set because application of functions is associative, and because we check that the identity curries in the right way.

In general, the definition of the exponential of an arrow is the obvious one: there’s only one way to make an element of given one in and a map , and that’s to “evaluate at , then do ”. This method does keep the identity map as an identity: causes to become , of course. It respects composition by just writing a couple of lines of symbol-manipulation.

Finally, the transpose of , which is a map . This takes a value and returns a function . Then some symbol shunting gives .

Calculating the exponential

Summary

This section is the one I’ve thought most concretely about so far. That’s probably something I’ll have to unlearn. It’s useful already being familiar with currying; this chapter would have been a lot harder without already having that intuition.