# What theorem constructs an initial object for this category? (Formerly “Integrability by abstract nonsense”)

Tom Leinster has a note here about how you can realize L^1[0,1] as the initial object of a certain category. You should really read his note because it is only 2.5 pages and is much more charming than what I am going to write below as background, but if you don't want to click on the link here is the idea:

We work in the category of Banach spaces with contractive maps, where we are defining $X \oplus Y$ to have the norm $|| (x,y) || = \frac{1}{2}(||x|| + ||y||)$. Consider triples $(X, \xi, u)$ where $X$ is a Banach space, $u \in X$ has norm at most 1, $\xi:X \oplus X \to X$ is a map of Banach spaces with $\xi(u,u) = u$. A morphism of such triples is a map of Banach spaces commuting with all structure in sight. The it turns out that the initial object in this category is $(L^1[0,1], \gamma, 1)$ where $\gamma(f,g)$ smushes $f$ and $g$ by a factor of two horizontally and then puts them side by side. Essentially this is because once you know where the constant function 1 goes, you can determine where any piecewise constant function whose discontinuities are at dyadic rationals goes, and then by density you get a unique map out of $L^1$.

Leinster mentions that there are some abstract results which actually construct an initial object for a category like this. I have looked through Barr and Wells, but I do not see what exactly I should be using here. The only general initial object construction I know (The one at the beginning of the adjoint functor theorem chapter of Categories for the Working Mathematician), doesn't seem to apply (maybe it does but I am not seeing it). Does anyone know such a general construction which applies here? How does that construction look when you apply it to this situation? Does it look anything like the usual construction of $L^1[0,1]$?

-
Unless I've misunderstood your question, it is not really about "integrability by abstract nonsense", but about finding a reference for & explanation of the general result which constructs an initial object. If that is the case then (a) perhaps you could consider amending the title of your question (b) the note you link to says that such a result should be somewhere in Barr and Wells' book, which is freely available online, see tac.mta.ca/tac/reprints/articles/12/tr12abs.html –  Yemon Choi Apr 30 '10 at 22:25
You forgot $\xi(u,u) = u$. Also the exact norm for $X \oplus X$ is crucial. I would say: it is not actually $[0,1]$ we are "constructing" but it is $\{0,1\}^\mathbb{N}$ with i.i.d. Bernoulli product measure. (Which is essentially the same thing.) –  Gerald Edgar May 1 '10 at 0:06
While I do think TL's note is interesting & thought-provoking (I still feel I should have guessed correctly when the question was posed at the start of that talk!) it feels like something better discussed in a blog post. OTOH, the closing question of this post seems a decent one for MO: I don't know offhand of the initial algebra theorem that's being used, but I'm sure passing category-theorists will. –  Yemon Choi May 1 '10 at 0:29
Upvoted for turning me on to this awesome note. ^_^ –  Vectornaut May 1 '10 at 3:35
@Yemon: I've been to Saskatoon in January. Clearly, just one beer is insufficient compensation for this type of weather experience. –  François G. Dorais May 1 '10 at 17:42

I hope this answers the question a bit more explicitely as the other one. The general theorem which applies here is the following:

Theorem: Let $C$ be a category which as an initial object and colimits of $\omega$-chains. Then for every functor $F : C \to C$ which preserves these colimits, there exists an initial $F$-algebra. Namely, you can take the colimit of $0 \stackrel{i}{\rightarrow} F(0) \stackrel{F(i)}{\rightarrow} F^2(0) \stackrel{F^2(i)}{\rightarrow} \cdots$.

Remark the similarity to other fixed point theorems, such as by Banach (for Banach spaces) or Tarski (for CPOs). The proof is easy and straight forward. In our case, we have the category of Banach spaces $B$ and consider the comma category $C=\mathbb{K} / B$. It has products and also colimits of $\omega$-chains (take the completion of the colimit of the underlying normed spaces) and the functor $F : C \to C,~ X \mapsto X \times X$ preserves them. Thus we can apply the Theorem.

The sequence $\mathbb{K} \to \mathbb{K}^{\{0,1\}^1} \to \mathbb{K}^{\{0,1\}^2} \to \dotsc$ identifies with the sequence of inclusions $X_0 \subseteq X_1 \subseteq X_2 \subseteq \dotsc$, where $X_n$ is the space of step functions $[0,1[ \to \mathbb{K}$ which are constant on every intervall of the $n$-th dyadic subdivision of the interval. The norm becomes the usual $\mathrm{L}^1$-norm. The union $\cup_n X_n$ consists of those step functions which are locally constant with respect to some dyadic subdivision and is endowed with the $\mathrm{L}^1$-norm. All step functions can be approximated by these dyadic step functions. The completion is thus, indeed, $\mathrm{L}^1[0,1]$. Also some inspection gives us that the algebra structure consists of the constant function $1$ and the map $(f,g) \mapsto f \star g$, which squeezes and juxtaposes.

So basically this construction is very similar to the usual one of $\mathrm{L}^1[0,1]$, but we don't have to care about any ambiguity of choices since all the involved universal properties ensure this automatically. Besides, it avoids the general measure theory.

-
I missed this question when it first appeared. Yes, Martin, that's exactly the construction I had in mind. Thanks. The initial algebra theorem is the simplest of all initial algebra theorems. The only complication is that you have to apply it to an endofunctor of a coslice of Ban, not to an endofunctor of Ban itself. –  Tom Leinster Oct 16 '11 at 13:50
+1: This is indeed an easier proof. A few remarks: (1) the general theorem has been attributed to Adamek. (2) $\mathbb{K}$ denotes the ground field (usually $\mathbb{R}$ or $\mathbb{C}$, but sometimes another local field), and $B$ is, as before, the category of Banach spaces appropriate to that ground field, with morphisms contractive maps. (3) For the notion of algebra and initial algebra of an endofunctor, one may consult the nLab: nlab.mathforge.org/nlab/show/initial+algebra –  Todd Trimble Oct 16 '11 at 14:10

The category you described can be written as a lax limit of a diagram in the 2-category of categories. The diagram in question consists of accessible categories and accessible functors, so its limit is again accessible by a theorem of Makkai and Paré. It is obvious from the construction that the category has all small limits (they are computed as in the category of Banach spaces and nonexpanding maps), so it is in fact locally presentable. This means that it has all colimits and in particular an initial object.

Here are some more details and references. Let $\mathbf{Ban}_1$ be the category of Banach spaces and nonexpanding maps. This category is locally $\aleph_1$-presentable (see e.g. Borceux, Handbook of Categorical algebra, Volume II, 5.2.2.e). Let

$F \colon \mathbf{Ban}_1 \rightarrow \mathbf{Ban}_1$

be the functor which sends a Banach space $X$ to $\mathbb{R}+X\oplus X$, where + stands for the coproduct. A morphism f of Banach spaces gets sent to $\mathrm{id}_{\mathbb{R}}+f\oplus f$. Let $U \colon \mathbf{Ban}_1 \rightarrow \mathbf{Set}$ be the functor which sends a Banach space to its underlying set. Since $\aleph_1$-filtered colimits are computed as in the category of sets (see e.g. Borceux, Handbook of Categorical algebra, Volume II, 5.2.2.e) we know that the composite UF preserves $\aleph_1$-filtered colimits. By the open mapping theorem it follows that $F$ preserves $\aleph_1$-filtered colimits.

By the theorem of Makkai and Paré (see e.g. Adámek, Rosický, Locally Presentable and accessible categories, Theorem 2.77), the inserter $\mathcal{C}$ of $F$ and the identity functor on $\mathbf{Ban}_1$ is again an accessible category. The objects of $\mathcal{C}$ are triples $(X,\xi,u)$ where $\xi\colon X\oplus X \rightarrow X$ and $u\colon \mathbb{R} \rightarrow X$ are nonexpanding (i.e., u corresponds to an element of $X$ of norm less than or equal one). The morphisms are morphisms of Banach spaces which are compatible with $u$ and $\xi$. Thus $\mathcal{C}$ is almost the category we are interested in; the only thing that's missing is the requirement that $\xi(u,u)=u$.

Let

$G \colon \mathcal{C} \rightarrow \mathbf{Ban_1}$

be the functor which sends every object to $\mathbb{R}$ and every morphism to $\mathrm{id}_{\mathbb{R}}$. This is clearly a functor which preserves $\aleph_1$-filtered colimits. Let

$H \colon \mathcal{C} \rightarrow \mathbf{Ban_1}$

be the functor which sends $(X,\xi,u)$ to $X$ and a morphism to itself; this is again a functor which preserves $\aleph_1$-filtered colimits. There are two natural transformations $\alpha,\beta \colon G \Rightarrow H$, whose component at $(X,xi,u)$ is given by $u$ and $\xi(u,u)$ respectively. The equifier of $G$ and $H$ is precisely the category we are looking for, and from our construction we can conclude that it is accessible.

The obvious forgetful functor to Banach spaces creates limits, so this category is complete. Thus it is locally presentable, and therefore also cocomplete. In particular, it follows that our category has an initial object.

-
Thank you for the incredibly informative answer. I do not really understand it currently, but the references you cite seem like good places to learn about this stuff. Thanks! –  Steven Gubkin May 13 '10 at 0:35
A side question would be: is THIS simple enough to combine with the remarks in the question to make a construction of the integral that turns out to be simpler than the standard one? –  Gerald Edgar May 13 '10 at 12:04