This is part 12 of Categories for Programmers. Previously: Declarative Programming. See the Table of Contents.

It seems like in category theory everything is related to everything and everything can be viewed from many angles. Take for instance the universal construction of the product. Now that we know more about functors and natural transformations, can we simplify and, possibly, generalize it? Let us try.

The construction of a product starts with the selection of two objects `a`

and `b`

, whose product we want to construct. But what does it mean to *select objects*? Can we rephrase this action in more categorical terms? Two objects form a pattern — a very simple pattern. We can abstract this pattern into a category — a very simple category, but a category nevertheless. It’s a category that we’ll call **2**. It contains just two objects, 1 and 2, and no morphisms other than the two obligatory identities. Now we can rephrase the selection of two objects in *C* as the act of defining a functor D from the category **2** to *C*. A functor maps objects to objects, so its image is just two objects (or it could be one, if the functor collapses objects, which is fine too). It also maps morphisms — in this case it simply maps identity morphisms to identity morphisms.

What’s great about this approach is that it builds on categorical notions, eschewing the imprecise descriptions like “selecting objects,” taken straight from the hunter-gatherer lexicon of our ancestors. And, incidentally, it is also easily generalized, because nothing can stop us from using categories more complex than **2** to define our patterns.

But let’s continue. The next step in the definition of a product is the selection of the candidate object `c`

. Here again, we could rephrase the selection in terms of a functor from a singleton category. And indeed, if we were using Kan extensions, that would be the right thing to do. But since we are not ready for Kan extensions yet, there is another trick we can use: a constant functor Δ from the same category **2** to *C*. The selection of `c`

in *C* can be done with Δ_{c}. Remember, Δ_{c} maps all objects into `c`

and all morphisms into `id`

._{c}

Now we have two functors, Δ_{c} and D going between **2** and *C* so it’s only natural to ask about natural transformations between them. Since there are only two objects in **2**, a natural transformation will have two components. Object 1 in **2** is mapped to `c`

by Δ_{c} and to `a`

by D. So the component of a natural transformation between Δ_{c} and D at 1 is a morphism from `c`

to `a`

. We can call it `p`

. Similarly, the second component is a morphism `q`

from `c`

to `b`

— the image of the object 2 in **2** under D. But these are exactly like the two projections we used in our original definition of the product. So instead of talking about selecting objects and projections, we can just talk about picking functors and natural transformations. It so happens that in this simple case the naturality condition for our transformation is trivially satisfied, because there are no morphisms (other than the identities) in **2**.

A generalization of this construction to categories other than **2** — ones that, for instance, contain non-trivial morphisms — will impose naturality conditions on the transformation between Δ_{c} and D. We call such transformation a *cone*, because the image of Δ is the apex of a cone/pyramid whose sides are formed by the components of the natural transformation. The image of D forms the base of the cone.

In general, to build a cone, we start with a category *I* that defines the pattern. It’s a small, often finite category. We pick a functor D from *I* to *C* and call it (or its image) a *diagram*. We pick some `c`

in *C* as the apex of our cone. We use it to define the constant functor Δ_{c} from *I* to *C*. A natural transformation from Δ_{c} to D is then our cone. For a finite *I* it’s just a bunch of morphisms connecting `c`

to the diagram: the image of *I* under D.

Naturality requires that all triangles (the walls of the pyramid) in this diagram commute. Indeed, take any morphism `f`

in *I*. The functor D maps it to a morphism `D f`

in *C*, a morphism that forms the base of some triangle. The constant functor Δ_{c} maps `f`

to the identity morphism on `c`

. Δ squishes the two ends of the morphism into one object, and the naturality square becomes a commuting triangle. The two arms of this triangle are the components of the natural transformation.

So that’s one cone. What we are interested in is the *universal cone* — just like we picked a universal object for our definition of a product.

There are many ways to go about it. For instance, we may define a *category of cones* based on a given functor D. Objects in that category are cones. Not every object `c`

in *C* can be an apex of a cone, though, because there may be no natural transformation between Δ_{c} and D.

To make it a category, we also have to define morphisms between cones. These would be fully determined by morphisms between their apexes. But not just any morphism will do. Remember that, in our construction of the product, we imposed the condition that the morphisms between candidate objects (the apexes) must be common factors for the projections. For instance:

p' = p . m q' = q . m

This condition translates, in the general case, to the condition that the triangles whose one side is the factorizing morphism all commute.

We’ll take those factorizing morphisms as the morphisms in our category of cones. It’s easy to check that those morphisms indeed compose, and that the identity morphism is a factorizing morphism as well. Cones therefore form a category.

Now we can define the universal cone as the *terminal object* in the category of cones. The definition of the terminal object states that there is a unique morphism from any other object to that object. In our case it means that there is a unique factorizing morphism from the apex of any other cone to the apex of the universal cone. We call this universal cone the *limit* of the diagram D, `Lim D`

(in the literature, you’ll often see a left arrow pointing towards *I* under the `Lim`

sign). Often, as a shorthand, we call the apex of this cone the limit (or the limit object).

The intuition is that the limit embodies the properties of the whole diagram in a single object. For instance, the limit of our two-object diagram is the product of two objects. The product (together with the two projections) contains the information about both objects. And being universal means that it has no extraneous junk.

## Limit as a Natural Isomorphism

There is still something unsatisfying about this definition of a limit. I mean, it’s workable, but we still have this commutativity condition for the triangles that are linking any two cones. It would be so much more elegant if we could replace it with some naturality condition. But how?

We are no longer dealing with one cone but with a whole collection (in fact, a category) of cones. If the limit exists (and — let’s make it clear — there’s no guarantee of that), one of those cones is the universal cone. For every other cone we have a unique factorizing morphism that maps its apex, let’s call it `c`

, to the apex of the universal cone, which we named `Lim D`

. (In fact, I can skip the word “other,” because the identity morphism maps the universal cone to itself and it trivially factorizes through itself.) Let me repeat the important part: given any cone, there is a unique morphism of a special kind. We have a mapping of cones to special morphisms, and it’s a one-to-one mapping.

This special morphism is a member of the hom-set `C(c, Lim D)`

. The other members of this hom-set are less fortunate, in the sense that they don’t factorize the mapping of cones. What we want is to be able to pick, for each `c`

, one morphism from the set `C(c, Lim D)`

— a morphism that satisfies the particular commutativity condition. Does that sound like defining a natural transformation? It most certainly does!

But what are the functors that are related by this transformation?

One functor is the mapping of `c`

to the set `C(c, Lim D)`

. It’s a functor from *C* to **Set** — it maps objects to sets. In fact it’s a contravariant functor. Here’s how we define its action on morphisms: Let’s take a morphism `f`

from `c'`

to `c`

:

f :: c' -> c

Our functor maps `c'`

to the set `C(c', Lim D)`

. To define the action of this functor on `f`

(in other words, to lift `f`

), we have to define the corresponding mapping between `C(c, Lim D)`

and `C(c', Lim D)`

. So let’s pick one element `u`

of `C(c, Lim D)`

and see if we can map it to some element of `C(c', Lim D)`

. An element of a hom-set is a morphism, so we have:

u :: c -> Lim D

We can precompose `u`

with `f`

to get:

u . f :: c' -> Lim D

And that’s an element of `C(c', Lim D)`

— so indeed, we have found a mapping of morphisms:

contramap :: (c' -> c) -> (c -> Lim D) -> (c' -> Lim D) contramap f u = u . f

Notice the inversion in the order of `c`

and `c'`

characteristic of a *contravariant* functor.

To define a natural transformation, we need another functor that’s also a mapping from *C* to **Set**. But this time we’ll consider a set of cones. Cones are just natural transformations, so we are looking at the set of natural transformations `Nat(Δ`

. The mapping from _{c}, D)`c`

to this particular set of natural transformations is a (contravariant) functor. How can we show that? Again, let’s define its action on a morphism:

f :: c' -> c

The lifting of `f`

should be a mapping of natural transformations between two functors that go from *I* to *C*:

Nat(Δ_{c}, D) -> Nat(Δ_{c'}, D)

How do we map natural transformations? Every natural transformation is a selection of morphisms — its components — one morphism per element of *I*. A component of some α (a member of `Nat(Δ`

) at _{c}, D)`a`

(an object in *I*) is a morphism:

α_{a}:: Δ_{c}a -> D a

or, using the definition of the constant functor Δ,

α_{a}:: c -> D a

Given `f`

and α, we have to construct a β, a member of `Nat(Δ`

. Its component at _{c'}, D)`a`

should be a morphism:

β_{a}:: c' -> D a

We can easily get the latter from the former by precomposing it with `f`

:

β_{a}= α_{a}. f

It’s relatively easy to show that those components indeed add up to a natural transformation.

Given our morphism `f`

, we have thus built a mapping between two natural transformations, component-wise. This mapping defines `contramap`

for the functor:

c -> Nat(Δ_{c}, D)

What I have just done is to show you that we have two (contravariant) functors from *C* to **Set**. I haven’t made any assumptions — these functors always exist.

Incidentally, the first of these functors plays an important role in category theory, and we’ll see it again when we talk about Yoneda’s lemma. There is a name for contravariant functors from any category *C* to **Set**: they are called “presheaves.” This one is called a *representable presheaf*. The second functor is also a presheaf.

Now that we have two functors, we can talk about natural transformations between them. So without further ado, here’s the conclusion: A functor `D`

from *I* to *C* has a limit `Lim D`

if and only if there is a natural isomorphism between the two functors I have just defined:

C(c, Lim D) ≃ Nat(Δ_{c}, D)

Let me remind you what a natural isomorphism is. It’s a natural transformation whose every component is an isomorphism, that is to say an invertible morphism.

I’m not going to go through the proof of this statement. The procedure is pretty straightforward if not tedious. When dealing with natural transformations, you usually focus on components, which are morphisms. In this case, since the target of both functors is **Set**, the components of the natural isomorphism will be functions. These are higher order functions, because they go from the hom-set to the set of natural transformations. Again, you can analyze a function by considering what it does to its argument: here the argument will be a morphism — a member of `C(c, Lim D)`

— and the result will be a natural transformation — a member of `Nat(Δ`

, or what we have called a cone. This natural transformation, in turn, has its own components, which are morphisms. So it’s morphisms all the way down, and if you can keep track of them, you can prove the statement._{c}, D)

The most important result is that the naturality condition for this isomorphism is exactly the commutativity condition for the mapping of cones.

As a preview of coming attractions, let me mention that the set `Nat(Δ`

can be thought of as a hom-set in the functor category; so our natural isomorphism relates two hom-sets, which points at an even more general relationship called an adjunction._{c}, D)

## Examples of Limits

We’ve seen that the categorical product is a limit of a diagram generated by a simple category we called **2**.

There is an even simpler example of a limit: the terminal object. The first impulse would be to think of a singleton category as leading to a terminal object, but the truth is even starker than that: the terminal object is a limit generated by an empty category. A functor from an empty category selects no object, so a cone shrinks to just the apex. The universal cone is the lone apex that has a unique morphism coming to it from any other apex. You will recognize this as the definition of the terminal object.

The next interesting limit is called the *equalizer*. It’s a limit generated by a two-element category with two parallel morphisms going between them (and, as always, the identity morphisms). This category selects a diagram in *C* consisting of two objects, `a`

and `b`

, and two morphisms:

f :: a -> b g :: a -> b

To build a cone over this diagram, we have to add the apex, `c`

and two projections:

p :: c -> a q :: c -> b

We have two triangles that must commute:

q = f . p q = g . p

This tells us that `q`

is uniquely determined by one of these equations, say, `q = f . p`

, and we can omit it from the picture. So we are left with just one condition:

f . p = g . p

The way to think about it is that, if we restrict our attention to **Set**, the image of the function `p`

selects a subset of `a`

. When restricted to this subset, the functions `f`

and `g`

are equal.

For instance, take `a`

to be the two-dimensional plane parameterized by coordinates `x`

and `y`

. Take `b`

to be the real line, and take:

f (x, y) = 2 * y + x g (x, y) = y - x

The equalizer for these two functions is the set of real numbers (the apex, `c`

) and the function:

p t = (t, (-2) * t)

Notice that `(p t)`

defines a straight line in the two-dimensional plane. Along this line, the two functions are equal.

Of course, there are other sets `c'`

and functions `p'`

that may lead to the equality:

f . p' = g . p'

but they all uniquely factor out through `p`

. For instance, we can take the singleton set `()`

as `c'`

and the function:

p'() = (0, 0)

It’s a good cone, because `f (0, 0) = g (0, 0)`

. But it’s not universal, because of the unique factorization through `h`

:

p' = p . h

with

h () = 0

An equalizer can thus be used to solve equations of the type `f x = g x`

. But it’s much more general, because it’s defined in terms of objects and morphisms rather than algebraically.

An even more general idea of solving an equation is embodied in another limit — the pullback. Here, we still have two morphisms that we want to equate, but this time their domains are different. We start with a three-object category of the shape: `1->2<-3`

. The diagram corresponding to this category consists of three objects, `a`

, `b`

, and `c`

, and two morphisms:

f :: a -> b g :: c -> b

This diagram is often called a *cospan*.

A cone built on top of this diagram consists of the apex, `d`

, and three morphisms:

p :: d -> a q :: d -> c r :: d -> b

Commutativity conditions tell us that `r`

is completely determined by the other morphisms, and can be omitted from the picture. So we are only left with the following condition:

g . q = f . p

A pullback is a universal cone of this shape.

Again, if you narrow your focus down to sets, you can think of the object `d`

as consisting of pairs of elements from `a`

and `c`

for which `f`

acting on the first component is equal to `g`

acting on the second component. If this is still too general, consider the special case in which `g`

is a constant function, say `g _ = 1.23`

(assuming that `b`

is a set of real numbers). Then you are really solving the equation:

f x = 1.23

In this case, the choice of `c`

is irrelevant (as long as it’s not an empty set), so we can take it to be a singleton set. The set `a`

could, for instance, be the set of three-dimensional vectors, and `f`

the vector length. Then the pullback is the set of pairs `(v, ())`

, where `v`

is a vector of length 1.23 (a solution to the equation `sqrt (x`

), and ^{2}+y^{2}+z^{2}) = 1.23`()`

is the dummy element of the singleton set.

But pullbacks have more general applications, also in programming. For instance, consider C++ classes as a category in which morphism are arrows that connect subclasses to superclasses. We’ll consider inheritance a transitive property, so if C inherits from B and B inherits from A then we’ll say that C inherits from A (after all, you can pass a pointer to C where a pointer to A is expected). Also, we’ll assume that C inherits from C, so we have the identity arrow for every class. This way subclassing is aligned with subtyping. C++ also supports multiple inheritance, so you can construct a diamond inheritance diagram with two classes B and C inheriting from A, and a fourth class D multiply inheriting from B and C. Normally, D would get two copies of A, which is rarely desirable; but you can use virtual inheritance to have just one copy of A in D.

What would it mean to have D be a pullback in this diagram? It would mean that any class E that multiply inherits from B and C is also a subclass of D. This is not directly expressible in C++, where subtyping is nominal (the C++ compiler wouldn’t infer this kind of class relationship — it would require “duck typing”). But we could go outside of the subtyping relationship and instead ask whether a cast from E to D would be safe or not. This cast would be safe if D were the bare-bone combination of B and C, with no additional data and no overriding of methods. And, of course, there would be no pullback if there is a name conflict between some methods of B and C.

There’s also a more advanced use of a pullback in type inference. There is often a need to *unify* types of two expressions. For instance, suppose that the compiler wants to infer the type of a function:

twice f x = f (f x)

It will assign preliminary types to all variables and sub-expressions. In particular, it will assign:

f :: t0 x :: t1 f x :: t2 f (f x) :: t3

from which it will deduce that:

twice :: t0 -> t1 -> t3

It will also come up with a set of constraints resulting from the rules of function application:

t0 = t1 -> t2 -- because f is applied to x t0 = t2 -> t3 -- because f is applied to (f x)

These constraints have to be unified by finding a set of types (or type variables) that, when substituted for the unknown types in both expressions, produce the same type. One such substitution is:

t1 = t2 = t3 = Int twice :: (Int -> Int) -> Int -> Int

but, obviously, it’s not the most general one. The most general substitution is obtained using a pullback. I won’t go into the details, because they are beyond the scope of this book, but you can convince yourself that the result should be:

twice :: (t -> t) -> t -> t

with `t`

a free type variable.

## Colimits

Just like all constructions in category theory, limits have their dual image in opposite categories. When you invert the direction of all arrows in a cone, you get a co-cone, and the universal one of those is called a colimit. Notice that the inversion also affects the factorizing morphism, which now flows from the universal co-cone to any other co-cone.

A typical example of a colimit is a coproduct, which corresponds to the diagram generated by **2**, the category we’ve used in the definition of the product.

Both the product and the coproduct embody the essence of a pair of objects, each in a different way.

Just like the terminal object was a limit, so the initial object is a colimit corresponding to the diagram based on an empty category.

The dual of the pullback is called the *pushout*. It’s based on a diagram called a span, generated by the category `1<-2->3`

.

## Continuity

I said previously that functors come close to the idea of continuous mappings of categories, in the sense that they never break existing connections (morphisms). The actual definition of a *continuous functor* `F`

from a category *C* to *C’* includes the requirement that the functor preserve limits. Every diagram `D`

in *C* can be mapped to a diagram `F ∘ D`

in *C’* by simply composing two functors. The continuity condition for `F`

states that, if the diagram `D`

has a limit `Lim D`

, then the diagram `F ∘ D`

also has a limit, and it is equal to `F (Lim D)`

.

Notice that, because functors map morphisms to morphisms, and compositions to compositions, an image of a cone is always a cone. A commuting triangle is always mapped to a commuting triangle (functors preserve composition). The same is true for the factorizing morphisms: the image of a factorizing morphism is also a factorizing morphism. So every functor is *almost* continuous. What may go wrong is the uniqueness condition. The factorizing morphism in *C’* might not be unique. There may also be other “better cones” in *C’* that were not available in *C*.

A hom-functor is an example of a continuous functor. Recall that the hom-functor, `C(a, b)`

, is contravariant in the first variable and covariant in the second. In other words, it’s a functor:

C^{op}× C -> Set

When its second argument is fixed, the hom-set functor (which becomes the representable presheaf) maps colimits in *C* to limits in **Set**; and when its first argument is fixed, it maps limits to limits.

In Haskell, a hom-functor is the mapping of any two types to a function type, so it’s just a parameterized function type. When we fix the second parameter, let’s say to `String`

, we get the contravariant functor:

newtype ToString a = ToString (a -> String) instance Contravariant ToString where contramap f (ToString g) = ToString (g . f)

Continuity means that when `ToString`

is applied to a colimit, for instance a coproduct `Either b c`

, it will produce a limit; in this case a product of two function types:

ToString (Either b c) ~ (b -> String, c -> String)

Indeed, any function of `Either b c`

is implemented as a case statement with the two cases being serviced by a pair of functions.

Similarly, when we fix the first argument of the hom-set, we get the familiar reader functor. Its continuity means that, for instance, any function returning a product is equivalent to a product of functions; in particular:

r -> (a, b) ~ (r -> a, r -> b)

I know what you’re thinking: You don’t need category theory to figure these things out. And you’re right! Still, I find it amazing that such results can be derived from first principles with no recourse to bits and bytes, processor architectures, compiler technologies, or even lambda calculus.

If you’re curious where the names “limit” and “continuity” come from, they are a generalization of the corresponding notions from calculus. In calculus limits and continuity are defined in terms of open neighborhoods. Open sets, which define topology, form a category (a poset).

## Challenges

- How would you describe a pushout in the category of C++ classes?
- Show that the limit of the identity functor
`Id :: C -> C`

is the initial object. - Subsets of a given set form a category. A morphism in that category is defined to be an arrow connecting two sets if the first is the subset of the second. What is a pullback of two sets in such a category? What’s a pushout? What are the initial and terminal objects?
- Can you guess what a coequalizer is?
- Show that, in a category with a terminal object, a pullback towards the terminal object is a product.
- Similarly, show that a pushout from an initial object (if one exists) is the coproduct.

Next: Free Monoids.

## Acknowledgments

I’d like to thank Gershom Bazerman for checking my math and logic, and André van Meulebrouck, who has been volunteering his editing help.

Follow @BartoszMilewski

May 5, 2015 at 9:14 pm

Shouldn’t the double-colon be an equals sign here?

May 5, 2015 at 9:51 pm

Oops! Fixed, thanks.

May 8, 2015 at 6:42 pm

“A generalization of this construction to categories other tha[n] 2”

May 18, 2015 at 5:23 am

Do limits have to be unique? I’m guessing the answer is “no” since products only have to be “unique up to isomorphism”. Or is there some way the limit gets around this?

May 18, 2015 at 10:42 am

As with all universal constructions, they are unique up to a unique isomorphism.

July 27, 2015 at 3:32 am

Do these words “limits”, “Continuity” come from analysis? How do they coincide when taking analysis from the the point of view of Category?

July 27, 2015 at 12:37 pm

@ahala: Yes, indeed. More specifically from topology. Open subsets form a category in a topological space, with inclusions playing the role of morphisms.

Topis a category of topological spaces with continuous functions as morphisms.October 2, 2015 at 6:15 pm

Let G be the functor from C to Set that maps every c in C to the set of cones (for functor D) with apex c. IOW,

`G(c) = Nat(Δ`

. Next, for_{c}, D)anyX in C, let`F`

be the functor from C to Set that maps every c in C to the set C(c, X). Also, for any X in C, let_{X}`P`

stand for the assertion “there exists a natural isomorphism between the functors_{X}`F`

and G.” Finally, let T denote the theorem stated in the “Limit as natural isomorphism” section (right after “So without further ado, here’s the conclusion:…”. I can paraphrase T (or rather, my understanding of it) in two not-obviously-equivalent ways. Here’s the first one: “The functor D has a limit with apex X if and only if_{X}`P`

.” And the second one: “_{X}Anycone with apex X is a limit of D if and only if`P`

.” Maybe these two formulations can be made to coincide with a suitable insertion of “up to [unique] isomorphism” somewhere, but the question still remains: is either of them indeed equivalent to T?_{X}October 3, 2015 at 5:48 pm

In the example on pullbacks (the one where one of the morphisms is a function with image {42}), it’s not clear to me what the pullback d is in the end. AFAICT, it is the product e \times c, where e is the set {t | t \in a and f t = 42}. Is this correct? Either way, I think the example would be more useful to your readers if the pullback was fully spelled out. (BTW, sorry for the inept notation; I have not figured out how to render math in these comments.)

October 4, 2015 at 2:31 am

@weekendwarrior: Your first question boils down to: Is the limiting cone unique? The answer is: Like every universal construction, it’s unique up to unique isomorphism.

As for your second question, I added a parenthetical remark that should clear the confusion (the image of g is not a set — it’s a number — an element of the set of numbers).

October 4, 2015 at 3:58 am

We must be using different definitions. I’ve always seen the “image of a function” g defined as the

subsetof the function’s codomain consisting of the elements g(x), as x ranges over the function’s domain. In the example it so happens that the set corrsponding to this description is a singleton, but it is still a set. But maybe we’re talking past each other. I think your point is that in the example, the category C where the pullback lives is not the category Set, but rather something else. Haskell types? If so, I’m even more curious now to know what exactly is the pullback (i.e. the object d and morphisms p and q) in that example.October 4, 2015 at 8:51 pm

You’re right about the image. Thank you for keeping me on my toes.

I rewrote the example so it’s more explicit. I hope it helps.

October 6, 2015 at 12:44 am

Yes, the new version is very clear. Thanks!

July 13, 2016 at 2:26 am

When you say that the terminal object is the limit making I the empty category, how does delta_c picks the apex of the cone? If I is the empty category no object of I can be used to get to c using delta_c. What am I missing?

July 13, 2016 at 9:52 am

@Juan: Good point! This is one of these tricky limiting cases, like dividing zero by zero. On the one hand, you can’t get to

`c`

because the source category is empty. On the other hand, the constant functor ignores its argument, so it shouldn’t matter.The best explanation is that the const functor trick is more of a motivation for the rigorous definition of a limit as a natural isomorphism:

Let’s analyze the right hand side. There is only one functor from the empty category to

C— the empty functor. So both`Δ`

and_{c}`D`

are empty functors. There is only one natural transformation between empty functors — the identity natural transformation. The right hand side is therefore a singleton set, for any choice of`c`

. Which means that all the hom-sets`C(c, Lim D)`

must be singletons. That makes`Lim D`

the terminal object.July 14, 2016 at 12:02 am

Thanks for your explanation. I can’t say I fully understand it but at least makes perfect sense.

Somehow this reminds me of an scene of the film Matrix when a child says: “there is no spoon”. But here we have an identity natural transformation between two no-spoons (empty functors).

Mindboggling.

September 7, 2016 at 2:27 pm

How is it that a cone is entirely determined by its apex when D is fixed? Couldn’t there be multiple natural transformations from Δc to D, which means multiple cones corresponding to the same c?

September 7, 2016 at 4:20 pm

Shimin Guo: You’re absolutely right. In fact I later talk about a set of natural transformations

`Nat(Δ`

. I’m removing this statement from the post. Thank you for spotting this._{c}, D)October 23, 2016 at 1:22 pm

Sorry to come in so long after the post went up, but I wanted to point out a slight error in terminology. When discussing pull-backs, the diagram you’re talking about is related to spans, but is not ITSELF a span.

A span in a category is a diagram of the form

(I’m hoping that works, but just in case: A1 A2)

Given A1 and A2, the spans between them form a category as you might expect: morphisms are the ones taken from hom(B, B’) that make both side triangles commute. They look like product cones, actually.

What does this have to do with pull-backs? well, spans can be composed! Say we’ve got two of them:

We can chain them up in the middle:

And now we can pull back the middle part to get an object C with morphisms to B1 and B2 that make the square in the middle commute. Composing with the outer morphisms we get morphisms from C to A1 and A3, which makes a span:

Does this mean that spans form a category? well, not quite. The problem is that this composition by pull-backs isn’t quite associative. But if we consider the morphisms between spans (the ones that look like product cone morphisms from before), then this composition of spans (as 1-morphisms) is associative

up to a canonical 2-morphism, making this a “weak” 2-category. The specific 2-morphism is defined by a natural isomorphism called the “associator”, the existence of which should follow from other material in this very post!Similarly, in push-outs the diagrams you mention are not quite co-spans, but the ideas are related, mutatis mutandis, as above.

October 23, 2016 at 10:01 pm

You’re right, I confused spans with cospans. Fixed!

I just talked about bicategories in my last lecture. This would be a good example.

BTW, I had no idea latex would work in WordPress. Must be a new thing.

October 24, 2016 at 5:56 am

I used to use it when I was still math-blogging at unapologetic.wordpress.com. Seems to be on by default here!

October 24, 2016 at 5:11 pm

You mention “category 13” in your post where you introduce spans. I assume that’s an html quoting error, where the arrows have turned into comments and eaten the object “2”.

October 24, 2016 at 7:17 pm

@eschnett: Exactly! Thanks for noticing.

November 25, 2016 at 7:16 am

After reviewing the Wikipedia article on

coequalizer, as well as a few of the references it points to, I’m still not clear on its significance in programming. Can you offer any hints?November 25, 2016 at 1:55 pm

This blog post by Phil Freeman provides some intuitions about equalizers and coequalizers.

April 5, 2017 at 2:20 pm

I would like to dive deeper into your Hindley-Milner pullback example. Do you have any references I can look at?

I’m really enjoying the videos, thanks for the good work!

April 8, 2017 at 5:56 am

“The intuition is that the limit embodies the properties of the whole diagram in a single object.”

this intuition seems misleading to me in the case of equalizer

May 23, 2017 at 3:38 pm

@Bartosz,

It seems that there is a problem with ‘precomposing’ word. You have two statements:

1). We can precompose f with u to get: u . f :: c’ -> Lim D

2). We can easily get the latter from the former by precomposing it with f: βa = αa . f

And obviously one of them must be wrong.

To solve the problem you need to change, for example, the second one to:

“We can easily get the latter from the former by composing it with f: βa = αa . f”

or

“We can easily get the latter from the former by precomposing f with αa: βa = αa . f”

May 24, 2017 at 8:21 am

@karkunow: Yes, this is an ongoing problem. I think I will, from now on, use precompose f to mean “first act with f” which, incidentally means that f will be on the right of the dot (that’s where the confusion comes from: it’s “post” dot).

September 21, 2017 at 9:06 am

Hello, I have watched ur videos(first part), and these videos(first part) is very interesting to me.I am a programmer,I am very interesting in Functor, Monad, product and co-product.

Then I decided to watched the rest videos(second part).But I find these stuff, like limit and free monoid, is so abstract,and I don’t know what is the use of these things?

I am curious what problem can these stuff solved?

How I can benefit from learning these stuff to help me understating world?

September 21, 2017 at 10:22 am

I don’t understand this: “This special morphism is a member of the hom-set C(c, Lim D). The other members of this hom-set are less fortunate, in the sense that they don’t factorize the mapping of cones.” It seems to me that any morphisms from c to Lim D would have to factorize the mapping of cones. Am I on the wrong layer of abstraction?

I’m taking Lim D to be the apex of the cone of the limit (a single object or set of isomorphic objects), and c to be the single chosen object in C to be the apex of some cone.

September 21, 2017 at 12:10 pm

The limiting cone has projections

`p`

: morphisms from_{i}`Lim D`

to`i`

. Some other cone with apex`c`

has projections`q`

. Since_{i}`Lim D`

is a limit, there is a unique morphism`h`

from`c`

to`Lim D`

with the property:for all

`i`

. That’s the special member of`C(c, Lim D)`

I’m talking about. If you try any other morphism`h'`

in`C(c, Lim D)`

, you’ll see that there is an`i`

such that`p`

is not equal to_{i}. h'`q`

._{i}It might help to keep in mind that a cone is defined not only by its apex, but also by its edges (projections). It’s possible to have more than one cone with the same apex but different edges.

September 21, 2017 at 9:12 pm

I won’t lie to you. There are some things in category theory that have immediate application in programming, and others that don’t. Here’s some motivation why you might want to learn things that are not immediately useful. You can be a professional programmer who is very skilled in creating beautiful programs for your clients. It’s a wonderful gift and it’s very appreciated. But what’s an even rarer gift is the ability to innovate. Innovation is not something that can be taught the same way you teach a language or an algorithm. An innovator has to have an open mind and the ability to make connections between previously unrelated things. If you only learn things that have immediate application, you won’t be challenging yourself. You’ll be stuck in a rut. You might miss a great opportunity.

September 30, 2017 at 7:37 am

Hello, I can’t understand this: “the naturality condition for this isomorphism is exactly the commutativity condition for the mapping of cones”

Doesn’t the commutativity condition come from the implementation of contra map for Nat(Δc, D)?

September 30, 2017 at 10:23 am

There are two commutativity conditions. One is internal to the cone: that one is taken care by the naturality of the transformation between Δ

_{c}and D. The other is the the commutativity of the triangles that sit between two cones — that’s the one that enforces the factorization of two sets of projections through h. That one is taken care by the naturality condition between C(c, Lim D) and Nat(Δ_{c}_{, D).}September 30, 2017 at 9:48 pm

I think I get it now,

In the second case, suppose there are two cones c, c’, and h :: c’ -> c

By the naturality condition, this diagram commutes:

starts from a vertex c, no matter we

1) get vertex c’ by precomposing h, then find the cones with vertex c’

2) find the cones with vertex c, then precompose them with h

we will get same set of cones, so every triangle {c, c’, D a} commutes

Did I do anything wrong?

July 8, 2018 at 5:40 am

Hello,

About question two of the challenges:

“Show that the limit of the identity functor Id :: C -> C is the initial object.”

Am I on the right track when I say that when we have two categories I and C, it is irrelevant which objects and morphisms are present in category I as the Id functor would map those objects and morphisms to themselves (that is in category I).

This would mean that we are only left with the apexes of cones in category C..

July 8, 2018 at 8:45 am

Hint: Replace the category I with C.

July 8, 2018 at 1:50 pm

Thank you, my attempt for answering the question after your hint:

In the category [C, C] there is always a unique natural transformation between the identity functor Id:: C -> C and any other functor present in [C, C].

That makes the initial object the limit of the identity functor

July 8, 2018 at 2:47 pm

Why don’t you just follow the definition of a limit, replacing I with C and the functor D with Id? There’s really not much more to it.

July 9, 2018 at 12:27 pm

I was on the wrong path.

The image of the Id functor is just C itself. Only initial objects can be the apex of a cone where the whole category is the base as there is a morphism to any object in the category only from the initial object(s) in a category i.e. there can be only a natural transformation between the Id functor and Δc when the image of Δc is an initial object.

When we have the limiting cone with apex c and another candidate cone with apex c’, that implies c’ is also an initial object which in turn implies that

there is a unique factorizing morphism from c’ to c. In this case any candidate is guaranteed to be a limiting cone.

July 9, 2018 at 10:57 pm

You’re on the right track. But there’s still one problem: How do you know that the morphism from the apex c of the limiting cone to any other object is unique (that’s part of the definition of the initial object, but not part of the definition of a cone). Hint: All triangles with the apex c commute, because they form the sides of the limiting cone.

July 11, 2018 at 1:34 pm

A cone is a natural transformation between functor Δc and functor Id in this case. This implies the morphisms from the apex c of the limiting cone to any other object are unique right?

Those morphisms are the components of the natural transformation.

July 11, 2018 at 1:48 pm

Not really, a natural transformation between functors f and g is a selection of morphisms, one per hom-set C(f a, g a). Uniqueness would require that those hom-sets be singletons, which, in general, is not true. What is guaranteed to be unique is the morphism from any other cone to the limiting cone– it’s a morphism that makes appropriate triangles commute. Again, there may be other morphisms between those apices that don’t make those triangles commute.

July 15, 2018 at 1:03 am

“Again, there may be other morphisms between those apices that don’t make those triangles commute.”

This is not possible in our case as far as I can see, because when switching to the category of our cones of interest, the objects are all cones of which the apex is an initial object in category C.

The morphims in that cone category are the unique morphisms from one initial object to another. There can’t be other morphisms between the apices.

July 15, 2018 at 9:25 am

Keep in mind what you are trying to prove: Suppose that the limit of the identity functor exists. Show that its apex defines the initial object. You can’t assume that the initial object exists–you have to prove it.

July 16, 2018 at 1:17 pm

Thank you for reminding me.

I guess I can still guarantee the morphisms between apices are unique without using the definition of the initial object, as the morphisms between the apices are (as you hinted) also part of the limiting cone.

The part of the definition of a cone that states that all triangles the pyramid consists of must commute (enfored by the naturality condition between functor Δc and the Id functor) makes those morphisms between apices unique.

October 12, 2018 at 2:19 am

I have a question. In category [I, C] we can have multiple morphisms (natural transformations) between Δ𝑐 and D. These are cones with the same apex c, but different projections? Why are those projections different if they are objects in C, mapped from using the same functor D? Are the starting objects from I different for these c apexed cones? Ty

October 12, 2018 at 11:27 am

I’m not sure what your question is. Projections are morphisms, and there may be many morphisms between the same two objects. Think of how many functions there are between any two types.

October 16, 2018 at 12:40 am

I was wondering if D can map in C different cone projections starting from the same i, k, j objects in I. Or by same c apexed cones, we mean cones with different projections (using D) starting from different objects in I. Sorry if the questions are silly, at some point I’m sure everything will settle down in my mind

May 6, 2019 at 11:33 pm

I can;t find the doc’s for this operator ~ e.g.:

`ToString (Either b c) ~ (b -> String, c -> String)`

Do anyone know where I can find it and what exactly it does with multiple arguments. If seen it only for one.

May 29, 2019 at 7:11 am

Could you please elaborate on it a bit. If, say, there are two index categories (one with two and the other one with three elements), there are two functors that pick elements from the main category using the index categories, then we end up with two distinct limits: canonically a pair and a tupple of three elements. There is no way to define an isomorphism between the limits. So there might be many limits in one category that are not isomorphic to each other, is my understanding correct?

May 29, 2019 at 8:41 am

We are talking about a universal construction for a particular functor. Limits for different functors are independent.

March 1, 2020 at 6:00 pm

Regarding the pullback of the C++ classes B and C from A: The fact that B and C are both subclasses of A does not at all affect how we find their pullback. Isn’t the pullback of B and C from A equivalent to the product of B and C?

May 25, 2020 at 8:39 am

[…] https://bartoszmilewski.com/2015/04/15/limits-and-colimits/ […]

September 6, 2020 at 8:26 am

I have trouble proving this.

I can prove (=>): if Lim D exists, then I can construct the natural isomorphism, but I’m stuck at (<=): if there’s a natural isomorphism C(c, c’) ≃ Nat(Δc, D), then c’ is the limit.

The trouble I have with (<=) is that I can’t prove that for two a cone c and c’, there is a unique isomorphism h: c -> c’. I don’t see how I can derive a contradiction from the statement “let’s also assume that we have two factorizers h,g: c -> c”.

Could you help me out?

September 6, 2020 at 3:26 pm

If you had two morphisms factorizing the same cone, they would both map to the same natural transformation, so it wouldn’t be a bijection.