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.

## Update

Apologies for the lack of posts recently; I’m on Spring Break and trying to relax and get some work done instead of blogging.

In other news, Stack Exchange offered me, and I accepted, an applied-mathematics internship with them this summer. (Procrastinating on math.SE finally paid off!)

I have learned some interesting things about mathematics education from seeing the types of questions which pop up most commonly on math.SE. If I can think of a way to coherently summarize my thoughts I might write a post about it.

## Pi is still wrong

In anti-honor of “Pi Day,” I’d like to direct your attention to Michael Hartl’s The Tau Manifesto. The Manifesto is inspired by Bob Palais’ article $\pi$ is wrong! and presents a list of simple, but compelling, reasons that $2 \pi$, not $\pi$, is the more fundamental constant.

These ideas have been discussed on the blathosphere before, e.g. on Bill Gasarch and Lance Fortnow’s blog Computational Complexity. There Terence Tao makes the following remark:

It may be that $2 \pi i$ is an even more fundamental constant than $2 \pi$ or $\pi$. It is, after all, the generator of $\log(1)$. The fact that so many formulae involving $\pi^n$ depend on the parity of $n$ is another clue in this regard.

The basic argument for this point of view can be summarized as follows: $e^z : \mathbb{C} \to \mathbb{C}$ is a special function because it is the unique eigenvector of eigenvalue $1$ of the derivative operator acting on, say, complex-analytic functions on $\mathbb{C}$, and this function has period $2 \pi i$. So we see that this constant pops directly out of a definition of $\mathbb{C}$ and a definition of the derivative of a complex-analytic function: no arbitrary choices were necessary. (The closest thing to an arbitrary choice here is the decision to identify the tangent space of a point in a vector space with the vector space itself, but this is completely invariant.)

The $2 \pi$ here is precisely the circumference of a unit circle, which is distinguished among all circles because in $\mathbb{C}$ it is the only circle of positive radius closed under multiplication. This is a fundamental number because of the relationship between the unit circle and Pontrjagin duality (which has the Fourier transform and Fourier series as special cases), and is responsible for all appearances of $2 \pi$ in mathematics that I know of.

For example, the reason there is a factor of $\sqrt{2\pi}$ in the definition of the Gaussian distribution (which is where the factor of $\sqrt{2\pi}$ comes from in Stirling’s formula) is that the Gaussian distribution is its own Fourier transform. This factor is commonly cited as an application of $\pi$ that has nothing to do with circles, but of course the Fourier transform has everything to do with circles.

Edit, 3/15/11: Vi Hart also explains the wrongness of $\pi$ in video form. I have to admit I think I read the title of her post and then promptly forgot I had done so when writing this post.

## John Baez interviews Eliezer Yudkowsky

There’s a lot of food for thought in John Baez’s latest post on Azimuth, an interview with AI researcher Eliezer Yudkowsky.

Eliezer Yudkowsky happens to be one of the most interesting people I know of. In addition to his work on friendly AI, he helped found the community blog Less Wrong. The material in his Sequences there describes what Yudkowsky calls “the art of rationality,” but if you’re not up to reading several long sequences of blog posts, you might be interested in his enormously popular Harry Potter fanfic, Harry Potter and the Methods of Rationality, which explores many of the same ideas in a more fun and accessible setting. I think this was an enormously clever ploy on his part.

Since this is a math blog, I’d also like to highlight the following part of the interview above:

In Silicon Valley a failed entrepreneur still gets plenty of respect, which Paul Graham thinks is one of the primary reasons why Silicon Valley produces a lot of entrepreneurs and other places don’t. Robin Hanson is a truly excellent cynical economist and one of his more cynical suggestions is that the function of academia is best regarded as the production of prestige, with the production of knowledge being something of a byproduct. I can’t do justice to his development of that thesis in a few words (keywords: hansom academia prestige) but the key point I want to take away is that if you work on a famous problem that lots of other people are working on, your marginal contribution to human knowledge may be small, but you’ll get to affiliate with all the other prestigious people working on it.

Words to ponder in light of the refusal of famous mathematicians like Grothendieck and Perelman to associate with academia.

Edit, 3/14/11: Part two of the interview is up.