Feeds:
Posts

## The free cocompletion I

Let $C$ be a (locally small) category. Recall that any such category naturally admits a Yoneda embedding

$\displaystyle Y : C \ni c \mapsto \text{Hom}(-, c) \in \widehat{C}$

into its presheaf category $\widehat{C} = [C^{op}, \text{Set}]$ (where we use $[C, D]$ to denote the category of functors $C \to D$). The Yoneda lemma asserts in particular that $Y$ is full and faithful, which justifies calling it an embedding.

When $C$ is in addition assumed to be small, the Yoneda embedding has the following elegant universal property.

Theorem: The Yoneda embedding $Y : C \to \widehat{C}$ exhibits $\widehat{C}$ as the free cocompletion of $C$ in the sense that for any cocomplete category $D$, the restriction functor

$\displaystyle Y^{\ast} : [\widehat{C}, D]_{\text{cocont}} \to [C, D]$

from the category of cocontinuous functors $\widehat{C} \to D$ to the category of functors $C \to D$ is an equivalence. In particular, any functor $C \to D$ extends (uniquely, up to natural isomorphism) to a cocontinuous functor $\widehat{C} \to D$, and all cocontinuous functors $\widehat{C} \to D$ arise this way (up to natural isomorphism).

Colimits should be thought of as a general notion of gluing, so the above should be understood as the claim that $\widehat{C}$ is the category obtained by “freely gluing together” the objects of $C$ in a way dictated by the morphisms. This intuition is important when trying to understand the definition of, among other things, a simplicial set. A simplicial set is by definition a presheaf on a certain category, the simplex category, and the universal property above says that this means simplicial sets are obtained by “freely gluing together” simplices.

In this post we’ll content ourselves with meandering towards a proof of the above result. In a subsequent post we’ll give a sampling of applications.

## The type system of mathematics

Occasionally I see mathematical questions that seem “grammatically incorrect” in some sense.

Example. “Is $[0, 1]$ open or closed?”
Example. “Is $\{ 1, 2, 3 \}$ a group?”
Example. “What’s the Fourier series of $\sin x + \sin \pi x$?”

Here are some sillier examples.

Example. “Is a rectangle prime?”
Example. “Is $17 \in 3$?”
Example. “What’s the Fourier series of the empty set?”

What all of these examples have in common is that they are type errors: they are attempts to apply some mathematical process to a kind of mathematical object it was never intended to take as input. If you tried to write a program in some highly mathematical programming language to answer these questions, it (hopefully!) wouldn’t compile.

Mathematical objects are usually not explicitly thought of as having types in the same way that objects in a programming language with a type system has types. Ordinary mathematics is supposed to be formalizable within Zermelo-Fraenkel (ZF) set theory, possibly with the axiom of choice, and in ZF every mathematical object is constructed as a set. In that sense they all have the same type. (In particular, the question “is $17 \in 3$?” is perfectly meaningful in ZF! This is one reason not to like ZF as a foundation of mathematics.) However, I think that in practice mathematical objects are implicitly thought of as having types, and that this is a mental habit mathematicians pick up but don’t often talk about.

Instead of thinking in terms of set theory, thinking of mathematical objects as having types allows us to import various useful concepts into mathematics, such as the notions of type safety, typecasting, subtyping, and overloading, that help us make more precise what we mean by a mathematical sentence being “grammatically incorrect.” The rest of this post will be a leisurely discussion of these and other type-based concepts as applied to mathematics in general. There are various categorical ideas here, but for the sake of accessibility we will restrict them to parenthetical remarks.

## Constructions vs. specifications

What does it mean to define a mathematical object?

Roughly speaking, there are two strategies you could use. One is to construct that object from other objects. For example, $\mathbb{R}$ can be constructed from $\mathbb{Q}$ using Cauchy sequences or Dedekind cuts.

Another is to give a list of properties that uniquely specify the object. For example, $\mathbb{R}$ can be defined as the unique Dedekind-complete totally ordered field.

Let’s call these strategies construction and specification. Construction has the advantage of concreteness, and it also proves that the object exists. However, it has the disadvantage that constructions are not unique in general and you might not be working with the most useful construction at a given time; to prove things about an interesting mathematical object you might have to switch between various constructions (while also proving that they all construct the same object).

Relying excessively on construction also has a curious disadvantage when talking to students about the object in question: namely, they might ask you how to show that object $X$ satisfies property $P$, and you might respond “well, it’s obvious if you use construction $A$,” and they might respond “but I was taught that $X$ is [construction $B$]!” The possibility of multiple different constructions of the same mathematical object makes construction somewhat unsatisfying in terms of describing what you even mean when you say “object $X$.”

This is the appeal of specification. Although specification is more abstract and harder to grasp at first, it has the advantage you don’t have to use any particular construction of an object to prove things about it: instead, you should in principle be able to prove everything from the properties alone, since those uniquely specify the object. This often leads to cleaner proofs. Specifications also usually give a better motivation for looking at an object: it’s easier to make sense of the claim that we want a mathematical object with various properties than to make sense of the claim that we want a mathematical object which is constructed in some arbitrary-looking (to the uninitiated) fashion.

Below we’ll go through a few examples of mathematical objects and some constructions and specifications of them.

## Writing a blog post every day is hard and possibly not a good idea

So: I’m happy that I’ve kept up MaBloWriMo for 13 days so far, but I’m running out of steam. I’ve gone through essentially all of the posts in my backlog that were relatively easy to write, and the things I’d like to write about at this point either

• really should be done with diagrams (and it’s not easy to finish a blog post with diagrams in a day) or
• might take more time than I allot for blogging in a day to work through the relevant concepts.

Sticking to one post a day at this point is likely to drive down quality, so I think I am going to stop doing it. It was a good goal for awhile in that it got me to write some posts that I’d wanted to write for a long time now, but unfortunately it is now doing the opposite of that.

## MaBloWriMo is upon us

Three years ago I thought it would be fun to write a blog post every day of November. I’m not sure why I didn’t do this in November 2010 or 2011 because I’m pretty sure I learned a lot from doing it in 2009, so I’d like to do it again. The posts will probably be shorter this time.

## Morality

Apologies for the lack of updates; I’ve been attempting to apply to graduate school. In the meantime, I want to link to a fantastic paper I just heard about by Eugenia Cheng on moral truth in mathematics. In private (or for me, on MathOverflow), mathematicians often say things like “well, morally, this should be true because…” and Cheng extensively discusses what this could mean and why it’s important.

I’m glad I finally have a word for this. I’ve cared about moral truth more than proof for awhile now, and that’s a major reason I’ve been trying to teach myself physics: even if it isn’t a good source of proofs, it seems like a great source of moral truths.