Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

June 20, 2009

Kan Lifts

Posted by David Corfield

I’ve been thinking more about organising principles operating in mathematics. I remember Steenrod wrote a very illuminating sketch of algebraic topology in terms of extensions and lifts, which I can’t now retrieve. That got me wondering, if with Mac Lane we say

The notion of Kan extensions subsumes all the other fundamental concepts of category theory,

whatever happened to Kan lifts?

So a little Google research takes me to a sci.math discussion about extension-lift duality and there’s our very own Todd saying

…specialists in category theory speak of left and right [Kan] extensions and [Kan] lifts in 2-categories.

So why don’t we have a big nLab page for the lifts as we do for the extensions, and if

The notion of Kan extensions subsumes all the other fundamental concepts of category theory,

how do we complete this

The notion of Kan lifts _ _ _ _ ?

Posted at June 20, 2009 9:21 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1998

39 Comments & 0 Trackbacks

Re: Kan Lifts

I haven’t been aware of “Kan lift” as a technical term.

Am I right in guessing that what is meant is just Kan extension in an opposite 2-category?

Googling, by the way, reveals experts on Kan lifts here

a Kan lift

Posted by: Urs Schreiber on June 20, 2009 12:35 PM | Permalink | Reply to this

Re: Kan Lifts

Here’s another expert on Kan lifts.

Posted by: John Baez on June 20, 2009 1:10 PM | Permalink | Reply to this

Re: Kan Lifts and Kan’s response

Last week I sent Dan Kan a printout of the then current version of this topic. Dan was amused, especially by the picture!

Dan is alive and well (though recovering for surgery on a damaged Achilles’ tendon) and has at least 3 papers in the mill.

Posted by: jim stasheff on July 6, 2009 12:15 AM | Permalink | Reply to this

Re: Kan Lifts

Wow, I’ve never ever heard about ‘Kan lifts’. Let me figure out what they must be. Alas, I’m too lazy to draw really beautiful diagrams here.

An extension problem arises when we have a morphism g:XYg: X \to Y — imagine it as an inclusion, but it doesn’t have to be — and a morphism h:XZh: X \to Z. The problem is to extend ff to g:YZg : Y \to Z so that the obvious equation holds:

f=gh f = g h

This makes sense in any category. A right or left Kan extension is a ‘best approximation’ to a solution of this problem in a 2-category.

A lifting problem arises when we have a morphism g:XYg: X \to Y — imagine it as a surjection, but it doesn’t have to be — and a morphism f:ZYf: Z \to Y. The problem is to lift gg to h:ZXh: Z \to X such that the obvious equation holds:

f=gh f = g h

This also makes sense in any category. So, a right or left ‘Kan lift’ should be a ‘best approximation’ to a solution of this problem in a 2-category.

The ‘best approximation’ idea has to do with adjunctions: given a functor going one way, I like to think of its left and right adjoints, if they exist, as ‘best approximations’ to its possibly nonexistent inverse.

In the Kan extension problem, the functor we’re trying to invert is ‘right composition with hh’: we’re given ff and hh, and we’d like to solve for gg here:

f=gh f = g h

This would be easy if we could undo right composition with hh. But even if right composition with hh lacks an inverse, it may still have a left or right adjoint. Then we get a left or right Kan extension.

In the Kan lifting problem, the functor we’re trying to invert is ‘left composition with gg’: we’re given ff and gg, and we’d like to solve for hh here:

f=gh f = g h

This would be easy if we could undo left composition with gg. But even if right composition with gg lacks an inverse, it may still have a left or right adjoint. Then we get a left or right Kan lift.

You’ll notice that Kan extensions and Kan lifts look suspiciously similar. Indeed one turns into the other if we turn around all the morphisms in our 2-category CC. That’s called taking the op of our 2-category. A Kan extension in CC is a Kan lift in C opC^{op}, and vice versa.

Left and right Kan extensions are also suspiciously similar. Indeed one turns into the other if we turn around all the 2-morphisms in our 2-category CC. That’s called taking the co of our 2-category. A left Kan extension in CC is a right Kan extension in C coC^{co}, and vice versa.

So in fact, viewed from a sufficient height, left and right Kan extensions and left and right Kan lifts are all the same bloody thing. The only difference is whether we’re working in CC, C opC^{op}, C coC^{co}, or C coopC^{co op}.

But this doesn’t really explain why people talk about Kan extensions a lot and Kan lifts very little.

Posted by: John Baez on June 20, 2009 1:07 PM | Permalink | Reply to this

Re: Kan Lifts

John wrote and linked

A right or left Kan extension is a ‘best approximation’ to a solution of this problem in a 2-category.

The nnLab entry [[Kan extension]] deserves to be linked to, here. My impression is that it is also better than the Wikipedia entry in several respects.

Posted by: Urs Schreiber on June 20, 2009 2:30 PM | Permalink | Reply to this

Re: Kan Lifts

So should the Kan extension entry be generalised to all 2-categories just as we have done with adjunctions?

Posted by: David Corfield on June 20, 2009 3:24 PM | Permalink | Reply to this

Re: Kan Lifts

Yes, certainly. I’m sure one of us nLab authors will get to it by and by.

Posted by: Todd Trimble on June 20, 2009 5:50 PM | Permalink | Reply to this

Re: Kan Lifts

I have created an entry on Kan lifts at the nLab.

Posted by: Todd Trimble on June 22, 2009 12:19 AM | Permalink | Reply to this

Re: Kan Lifts

So if you have a functor from AA to BB, then left and right Kan lifts of the identity functor 1 B1_B are adjoints?

Posted by: David Corfield on June 20, 2009 3:36 PM | Permalink | Reply to this

Re: Kan Lifts

I guess this is what you were saying:

Given a functor f:ABf : A \to B, the left and right Kan lifts of 1 B:BB1_B : B \to B to functors from BB to AA are the left and right adjoints of ff, respectively — if they exist.

It sounds right to me.

Posted by: John Baez on June 20, 2009 8:40 PM | Permalink | Reply to this

Re: Kan Lifts

Sorry, it’s not quite right. But if ff preserves the lift, then I think it’s right (I’ll explain in a minute).

As I was saying below, right Kan lifts (Rifts) of bimodules between small categories (and again let’s work with Cauchy complete ones) always exist. But that doesn’t mean Rift f1 BRift_f 1_B will be the right adjoint of f:ABf: A \to B, because f:ABf: A \to B may not be a left adjoint. (It is so when the bimodule is given by a ring map f:ABf: A \to B.)

The best you get out of the bargain is that you get a canonical arrow

ε:fRift f1 B1 B\varepsilon: f \circ Rift_f 1_B \Rightarrow 1_B

which would be the counit, if fRift f1 Bf \dashv Rift_f 1_B.

However, there is a canonical map

θ:(Rift f1 B)fRift ff\theta: (Rift_f 1_B) \circ f \Rightarrow Rift_f f

corresponding to the map

εf:(fRift f1 B)f1 Bf=f\varepsilon \circ f: (f \circ Rift_f 1_B) \circ f \Rightarrow 1_B \circ f = f

and it is also true that Rift ffRift_f f is a monad. If θ\theta above is an isomorphism (in which case we say that ff preserves the right Kan lift), then I think we have an adjunction fRift f1 Bf \dashv Rift_f 1_B.

(I’m going on memory here without checking it carefully; maybe someone should check up on that.)

Posted by: Todd Trimble on June 20, 2009 10:27 PM | Permalink | Reply to this

Re: Kan Lifts

I said earlier

But that doesn’t mean Rift f1 BRift_f 1_B will be the right adjoint of f:ABf: A \to B, because f:ABf: A \to B may not be a left adjoint. (It is so when the bimodule is given by a ring map f:ABf: A\to B.)

I should have said, “when the bimodule is given by a functor f:ABf: A \to B”.

My point was that in the bicategory of small categories and bimodules between them, left adjoints r:ABr: A \to B in the bicategory are essentially the same as bimodules of the form

hom B(,f):B op×ASethom_B(-, f-): B^{op} \times A \to Set

where f:ABf: A \to B is a functor. Technically, that’s not quite correct, unless the categories in question are Cauchy complete, which is why I threw in that assumption.

Posted by: Todd Trimble on June 21, 2009 2:09 PM | Permalink | Reply to this

Re: Kan Lifts

But even if right composition with h lacks an inverse, it may still have a left or right adjoint. Then we get a left or right Kan extension.

What if right composition does have an inverse? You still get a Kan extension, right?

I added the linear map examples to [[functor]] because I was going to try to use those in an example of Kan extension.

If that goes through, it seems it might also provide a nice simple example of Kan lift.

Posted by: Eric on June 20, 2009 6:04 PM | Permalink | Reply to this

Re: Kan Lifts

Eric wrote:

What if right composition does have an inverse? You still get a Kan extension, right?

Yes, because when a functor has an inverse, this inverse is its adjoint — both its left and right adjoint!

Posted by: John Baez on June 20, 2009 8:31 PM | Permalink | Reply to this

Examples of Kan Lifts

Let me give just one class of examples of Kan lifts, to show they are familiar objects in some cases.

Take for example the bicategory of rings, bimodules B:RTB: R \to T (left BB right TT bimodules), and bimodule homomorphisms. Then given B:RTB: R \to T, A:STA: S \to T, the right Kan lift of BB through AA exists, and is

hom T(C,A):RShom_T(C, A): R \to S

where the hom is of right TT-modules. This example holds more generally in any biclosed bicategory, where composition on either side has a right adjoint. In particular, it holds in the bicategories RelRel, SpanSpan, ProfProf (profunctors or bimodules between small categories, enriched in SetSet or in any other suitably nice VV), as well as in any biclosed monoidal category.

In my original draft of this comment, I was going to give some other examples of Kan lift as they arise in the theory of yoneda structures, which were discussed back here in connection with 2-topos theory. But I think I’ll hold off on that, as they might seem a bit more recondite.

Posted by: Todd Trimble on June 20, 2009 7:56 PM | Permalink | Reply to this

Re: Kan Lifts

Back here John wrote

But this doesn’t really explain why people talk about Kan extensions a lot and Kan lifts very little.

My rough impression is that Kan extensions show up very often in contexts where one has a rich environment DD (I’m following Jim Dolan in his video lectures on algebraic geometry, using the word ‘environment’ to refer to codomains: receiving categories in which ‘theories’, or domain categories, are interpreted), and one wants to extend one ‘model’ m:CDm: C \to D of a ‘theory’ CC to a model of another theory CC' along a theory morphism t:CCt: C \to C', and do this in a universal way.

An archetypal example of this is left Kan extension along a Yoneda embedding: given a functor f:CDf: C \to D (with CC small), the left Kan extension

f^=Lan yCf:Set C opD\hat{f} = Lan_{y C} f: Set^{C^{op}} \to D

exists provided that DD is cocomplete. In other words, an interpretation ff of a theory CC in an environment DD can be extended (universally) to an interpretation f^\hat{f} of a richer theory C^=Set C op\hat{C} = Set^{C^{op}}, if the environment DD supports that. This basic example extends in a variety of directions; for example the theory CC could be a monoidal or symmetric monoidal theory, and the interpretations are to preserve the monoidal structure, and we consider the extension to a richer monoidal or symmetric monoidal category Set C opSet^{C^{op}}, obtained by freely adjoining colimits (= weights on CC).

In any case, Kan extensions are from this point of view about extensions of models, extending a model of one theory to a model of another, but within the same environment.

What about Kan lifts? This time the theory CC remains the same, but we change the environment, i.e., we have a situation like

D p C f D\array{ & & D' \\ & & \downarrow p \\ C & \overset{f}{\to} & D }

where we are trying to lift an interpretation ff of CC in DD to a (maybe richer) environment DD' – for example, DD' may be a category of algebras over DD. Now the Kan lift may very well exist and be important, but maybe we recognize it by another name. For example, suppose we want the left Kan lift of a functor ff through UU in the situation

MAlg U C f Set\array{ & & M-Alg \\ & & \downarrow U \\ C & \overset{f}{\to} & Set }

where MM-AlgAlg is the category of algebras of a monad MM, and UU is the underlying set functor. Then the left Kan lift exists, but it’s obtained just by composing ff with the free functor F:SetMAlgF: Set \to M-Alg. In other word, the lifting problem is solved in a trivial way, so we don’t particularly refer to it as a Kan lift – it just is what it is.

So to wrap up this story: part of the asymmetry here may be due to the fact that in practice, theories are often “small” (e.g., sites), whereas the environments in which they are interpreted are often “big”, or “rich” – categories like SetSet or perhaps a sup-lattice like 2\mathbf{2}. And whereas Kan extensions draw attention to themselves by being constructed by a process which is interesting in its own right, Kan lifts don’t stand out so much because they are often effected by some simple process like postcomposing with some arrow which is “there” because the environments accommodate it.

I’m obviously not attempting a complete explanation here, and obviously some of this is to be taken with a grain of salt.

Posted by: Todd Trimble on June 21, 2009 9:46 PM | Permalink | Reply to this

Re: Kan Lifts

That makes good sense. I wonder whether you attribute what you portray in your penultimate paragraph to the habits of mathematicians (which may display some historical inertia) or to objective features of CatCat as a 2-category.

I seem to keep knocking up against the issue of symmetry in mathematics, as with the discussion on coalgebra. We have in the nLab entry for Set

This category has many marvelous properties, which make it a common choice for serving as a ‘foundation’ of mathematics.

I take it that with some of these properties it would not be possible to find an interesting category which had them and their duals. So why do we prefer these properties to their dual versions? And, is the drive towards relations and profunctors motivated by a desire for duality?

John mentioned above the 3 duals of a 2-category CC, namely, C opC^{op}, C coC^{co} and C coopC^{co op}. If Set opSet^{op} is equivalent to the category of Complete atomic boolean algebras, is there any way to describe Cat opCat^{op}, Cat coCat^{co} or Cat coopCat^{co op} as a 2-category of some kind of categories?

Posted by: David Corfield on June 22, 2009 9:40 AM | Permalink | Reply to this

Re: Kan Lifts

Wow, those are hard questions. I guess I lean to the position (really a truism) that so much of mathematics as we know it is dictated by the way humans are wired – the way in which cognitive processes are rooted in vision and in physical actions, and driven by emotional needs, that it seems much safer to me to suppose these sorts of imbalances are due to human habits or characteristics. In other words, if computers were one day to do independent mathematical research, they might explore all sorts of possibilities which would seem very strange or would never occur to us, and redress some of the apparent imbalances.

But to me this is awfully (and unsatisfyingly) speculative; I’d like to know how one might approach these questions more rigorously.

Your own line of questioning hints to me that you think the imbalance between Kan extensions and Kan lifts could be due to some objective feature of CatCat, but that the preference for SetSet or CatCat (over say Set opSet^{op} or Cat opCat^{op}) might itself be based on human habit. For example, maybe the preference for relations which are functions is based on the need for definiteness, for unique specification (I am going to place this ball in that box; this billiard ball is going in that direction). Tim Gowers had a recent post on well-definedness of functions; in one of his comments he was saying how composition of functions is for him more intuitive than composition of relations. If one sees composition of relations as akin to matrix multiplication, which itself is akin to a Feynman-like “sum over all histories” process, and if one remembers how late in the history of science both matrix mechanics and Feynman’s insight came (and how revolutionary and mind-bending they were), then one begins to see how strong the force of mental habit can be.

At the same time, the principle of duality (now there’s an organizing principle!) in category theory is very liberating, and once can’t help think that such drives toward symmetry (in this case, toward the presence of duality involutions) also has a lot to do with the ascent of RelRel, ModMod, and so on. A key feature of these 2-categories is concentrated in compactness, a type of symmetry one finds in many modern-day physical theories (as emphasized for instance by Baez, Coecke, and others, and seen also in e.g. TQFT). From the standpoint of conducting flexible calculations, compactness (or its relative *-autonomy) is very powerful indeed.

I’d like to come back to dual relatives of CatCat a little later. But these are good, thought-provoking questions.

Posted by: Todd Trimble on June 22, 2009 3:59 PM | Permalink | Reply to this

Re: Kan Lifts

SH: I’ve mentioned before that defining causality can be seen as the core issue:

http://en.wikipedia.org/wiki/Causality
“The Nobel Prize holder Herbert Simon and Philosopher Nicholas Rescher[20]
claim that the asymmetry of the causal relation is unrelated to the asymmetry
of any mode of implication that contraposes. Rather, a causal relation is not
a relation between values of variables, but a function of one variable (the
cause) on to another (the effect). So, given a system of equations, and a set
of variables appearing in these equations, we can introduce an asymmetric
relation among individual equations and variables that corresponds perfectly
to our commonsense notion of a causal ordering. The system of equations must
have certain properties, most importantly, if some values are chosen arbitrarily,
the remaining values will be determined uniquely through a path of serial
discovery that is perfectly causal. They postulate the inherent serialization of
such a system of equations may correctly capture causation in all empirical fields,
including physics and economics.”
——————————————

Todd Trimble wrote Re: Kan Lifts
“Wow, those are hard questions. I guess I lean to the position (really a truism) that so much of mathematics as we know it is dictated by the way humans are wired – the way in which cognitive processes are rooted in vision and in physical actions, and driven by emotional needs, that it seems much safer to me to suppose these sorts of imbalances are due to human habits or characteristics. In other words, if computers were one day to do independent mathematical research, they might explore all sorts of possibilities which would seem very strange or would never occur to us, and redress some of the apparent imbalances.” —————

SH: “if computers were one day to do independent mathematical research”.
Remember that computers do what humans can do with pencil paper and eraser.
Of course they do it much faster which enables proofs which exhaust all the
possible counter-examples, proofs that might exceed a human lifetime, but
still they are in the same class of quantitative combinatorial results. So
one question is, does faster mean more intelligent? I think you mean by
“independent research”, a qualitative change in intelligence; a new range of
proofs that are not accessible or reachable by the combinatorial scaffolding
of computable proofs to which both humans and computers now eventually obtain?
I think you may be considering a non-human intelligence, not a formal system?
Anyway, I think there is a similarity between my causality quote and the
pointer you provided regarding the difficulty of how to “define” functions
and defining/creating algorithms for AI neo-theorem-proving programs. __________

http://gowers.wordpress.com/2009/06/08/why-arent-all-functions-well-defined/
“But it seems only fair, if one is going to laugh at such sentences, to provide
examples of functions that are well defined and functions that aren’t, so that
the difference can be made clear. But now we have a problem: any putative example
of a function that is not well defined is not a function at all. So it begins to
seem as though all functions are well defined. But in that case, what are people
doing when they check that a function is well defined? The real question we are
asking is this: when we use the words “well defined”, what are we referring to?”

JB mentioned the enigma of the Arrow of Time. I cobbled together this description.
‘The problem in determining the reason for the arrow of time is created by the
indistinguishability between whether time reversal non-invariant laws of nature or
temporally asymmetric boundary conditions describe reality or our perception of it.’ —————————–

“The second kind of story about how entropy increase might ground our ordinary intuitions of an arrow of time is David Lewis’s account of the asymmetry in counterfactuals.”

“The point of defending Humean Supervenience is not to support reactionary physics, but rather to resist philosophical arguments that there are more things in heaven and earth than physics has dreamt of.”

“It may be that universal history is the history of the different intonations given a handful of metaphors.” :-)

Echoes of a fractal drum,
Stephen

Posted by: Stephen Harris on June 24, 2009 3:21 PM | Permalink | Reply to this

Re: Kan Lifts

Stephen, I don’t know whether we’re really talking about the same things, but:

Yes, regarding “computers doing independent mathematical research”, I really more or less meant (science-fictional) non-human intelligences capable of formulating and attaining mathematics research goals independently of humans; I just didn’t feel like referring to grays, so I projected onto computers instead, at some indeterminate point in the future.

But any such discussion seems to me a bit academic at this point. My own feeling, not based on intimate knowledge of the current state of AI, is that computers are nowhere close to the point I just sketched above. (I would also feel a need to qualify heavily the statement that computers can do what humans do with pencil and paper. A lot of what we do with pencil and paper is formulate research goals to ourselves, or jot down shorthand in order to evoke mental images.) I was just musing that if they could do mathematics independently, it would probably look radically different from mathematics as we humans know it, and they might bump into instances of Kan lifts in CatCat which would never have occurred to us (this in response to David Corfield’s question about whether the asymmetry between extensions and lifts is attributable to an objective feature of CatCat).

Posted by: Todd Trimble on June 24, 2009 6:32 PM | Permalink | Reply to this

Re: Kan Lifts

Yes Todd, you are right, about the current capability of AI as well as I left out part of the definition, especially the “by rote, ingenuity and insight” aspects. Your posts are interesting.

“Originally the term ‘computer’ did not refer to a machine, but a human being

* A mathematical assistant who calculated ‘by rote’ in accordance with some ‘effective method’.

* A method is ‘effective’ iff:
+ … it demands no insight or ingenuity from the human computer.
+ … produces a result in a finite number of steps.”

Posted by: Stephen Harris on June 24, 2009 7:26 PM | Permalink | Reply to this

Re: Kan Lifts

Todd wrote:

Tim Gowers had a recent post on well-definedness of functions; in one of his comments he was saying how composition of functions is for him more intuitive than composition of relations. If one sees composition of relations as akin to matrix multiplication, which itself is akin to a Feynman-like “sum over all histories” process, and if one remembers how late in the history of science both matrix mechanics and Feynman’s insight came (and how revolutionary and mind-bending they were), then one begins to see how strong the force of mental habit can be.

I’m glad you mentioned this, because it gives me an opening to say what I think causes the asymmetry that David’s interested in.

It’s the arrow of time!

Why is SetSet so different than Set opSet^{op}? It’s because the morphisms are functions: relations that can be many-to-one, but not one-to-many.

Why do many-to-one but not one-to-many relations get singled out for single treatment and dubbed ‘functions’? Because functions are supposed to be ‘deterministic’: the cause must determine the effect. We don’t care if the effect fails to determine the cause.

Why does our customary concept of determinism have this asymmetry built in? Well, we see it a lot in ordinary life. It’s often (though not always) true that the initial state of an experiment determines the final outcome. But it’s much less common for the final outcome to determine the initial state… at least, not in an easily visible way.

For example, take a heat distribution and run it forwards to equilibrium. We always get the same equilibrium, regardless of the initial conditions.

This asymmetry is built into equations like the heat equation, but it seems absent from the fundamental laws of physics — so far, anyway. This leads to a big puzzle: “why is there this ‘arrow of time’?”

Nobody knows the answer, except “that’s how this universe is: there’s a low-entropy big bang in the past, and a high-entropy expansion in the future, as far as we can see.”

So, the beautiful time-symmetric formalism of quantum theory, so nicely modelled by the dagger-categories we’ve learned to love, is far removed from common experience, where functions rule the roost.

Posted by: John Baez on June 22, 2009 10:37 PM | Permalink | Reply to this

Re: Kan Lifts

Restricting things to why functions are prevalent in general mathematics (rather than whether they ought to be prevalent in category theory).

I wonder if this view is partly influenced by your interest in mathematics arising from physics? I’d be inclined to say that my feeling is that the fundamental issue is not that functions are deterministic but that they are “definite decisions”. Part of my reasons is that language, from which many higher mental functions seem to be evolved, can cope with resolving quite deep “stacks” of definite elements but are very poor at resolving much less deep “stacks” which involve tracking multiple different possibilities at each level. (I know that working with relationships in mathematics would generally be dealt more by being specified by predicates, but I think this comes later than developing the comfortable “intuition” about relations.)

A more minor piece of evidence comes from the ways we model computer programs: people, particularly practicing computer programmers, are generally quite comfortable using languages/specification languages having non-deterministic choices that fit some criterion but there’s much less work (AFAIK) dealing with all the possible states consistent with the criteria. (Of course, part of that is potential combinatorial explosion, but that need not be a problem in all practical cases or when working symbolically.) One highly speculative explanation MIGHT relate this to the above language ability issue.

Posted by: bane on June 23, 2009 1:04 AM | Permalink | Reply to this

Re: Kan Lifts

Bane wrote:

I wonder if this view is partly influenced by your interest in mathematics arising from physics? I’d be inclined to say that my feeling is that the fundamental issue is not that functions are deterministic but that they are “definite decisions”.

My views are very much influenced by my interest in physics. But I guess I didn’t explain myself very well: I didn’t mean that people got interested in functions because they were working on physics. What I meant is that living in a world where the future and past are so drastically different, people are bound to come up with math that has this asymmetry built in.

Part of my reasons is that language, from which many higher mental functions seem to be evolved, can cope with resolving quite deep “stacks” of definite elements but are very poor at resolving much less deep “stacks” which involve tracking multiple different possibilities at each level.

I agree, but I again see the arrow of time here. We need to predict the future much more than we need to postdict the past. Why? Because we want to keep on surviving in the future, not the past. Why? It’s an arrow of time thing.

So, trees of possibilities that branch forwards in the future are more worrisome than trees that branch backwards into the past. So, we find it very nice when a cause has just one possible effect: it simplifies our life. We don’t care as much whether an effect has just one possible cause — unless we’re doing a little piece of detective work, or history.

In short, we don’t need to think about physics explicitly to develop a preference for functions over cofunctions: the physics of the world we live in almost guarantees it.

On the contrary, it’s only when we start thinking about physics explicitly that we notice that the laws are time-symmetric, or nearly so, and we start developing an interest in categories that are self-dual. First the additive group of real numbers: the time line, which stretches symmetrically in both directions. Then the concept of groups, where every element has an inverse. Then the idea that time evolution is a symmetry, i.e. the action of a group. Then the development of matrix mechanics, where every operator has an adjoint. Then the realization that dagger-categories are important in physics, and the idea of ‘reversible computing’.

I’m exaggerating for effect here, but it would be fun to work out these ideas more carefully.

Posted by: John Baez on June 23, 2009 7:08 AM | Permalink | Reply to this

Re: Kan Lifts

All I meant by the physics comment was that these are clearly issues at the forefront of the mind of anyone working in physics, whilst they don’t really enter the context of people who don’t work in physics who seem to display the same traits in preferring definite (sometiems arbitrary) choices. Of course earlier in the history of mathematics it was much rarer to have someone involved in mathematics who wasn’t also involved in physics in some way.

Your argument sounds very plausible, and clearly there’s a “trivial” sense in which it must be true in that it’s difficult to imagine complex physical beings arising in a universe without an initial low entropy, and human brains evolved to deal with a “deterministic at the gross level” universe. It just strikes me that from my knowledge of both geometry and computer programming, both areas where a priori there’s no direct connection with entropy, people are still very uncomfortable with dealing with many-to-many issues directly and to try to “view everything as definite choices (ie, many to one) and then fix-up multiple valuedness at the end”.

Of course, that might well be that this mental preference has evolved for the kind of reasons you say and then gets applied everywhere.

Posted by: bane on June 23, 2009 9:48 AM | Permalink | Reply to this

Re: Kan Lifts

By the way, David — Cat opCat^{op}, Cat coCat^{co} and Cat coopCat^{co op} are all very well and good, but if you really want to let duality infect the concept of category, try thinking about cocategories!

Posted by: John Baez on June 22, 2009 10:40 PM | Permalink | Reply to this

Re: Kan Lifts

I was going to bring up the subject of cocategories at some point, and had started to jot down some references.

Posted by: David Corfield on June 23, 2009 8:46 AM | Permalink | Reply to this

Re: Kan Lifts

Can’t resist adding that intervals are not just homotopy cocategories, they are A A_\infty cocategories. See here and here.

Posted by: Todd Trimble on June 23, 2009 1:21 PM | Permalink | Reply to this

Re: Kan Lifts

David: Todd was too modest to emphasize it here, but the observation that the closed unit interval is an A A_\infty-cocategory is key to his definition of \infty-categories.

Here are some of the basic ideas, too basic too be explained so far in the nnLab entry.

An arrow looks like an interval. So, the theory of categories and even nn-categories should have a lot to do with the interval — especially when it comes to applications to topology!

In a category we can glue arrows together, ‘composing’ them. But an interval can be chopped apart or ‘decomposed’ into a bunch of intervals. So, there should be a cocategory or something like that lurking around here.

In fact the closed unit interval gives an A A_\infty-cocategory: a cocategory where the laws hold up to homotopy, where the homotopies satisfy nice laws up to homotopy, ad infinitum.

The space of maps out of an A A_\infty-cocategory into something should form an A A_\infty-category. So, the space of maps out of an interval into a space forms an A A_\infty-category. And this is an important first step in how Todd constructs the fundamental nn-groupoid of a space!

But the really cool part is how this construction goes hand in hand with his definition of nn-categories, in an inductive kind of way.

Posted by: John Baez on June 26, 2009 12:08 PM | Permalink | Reply to this

Re: Kan Lifts

Here are some of the basic ideas, too basic to be explained so far in the nnLab entry.

It’s there now. I have copy-and-pasted your blog comment into the entry for you.

Posted by: Urs Schreiber on June 26, 2009 4:19 PM | Permalink | Reply to this

Re: Kan Lifts

A lot of this must simply be habit. Proof: SetSet is just as derivable from RelRel (at least with all of its structure as an allegory) as RelRel is from SetSet, so objectively it's perfectly correct to say that mathematics is founded in RelRel (or at least as correct as to say that it's founded in SetSet).

Posted by: Toby Bartels on June 23, 2009 5:56 AM | Permalink | Reply to this

Re: Kan Lifts

Right, but there’s a symmetry breaking required when we go from RelRel to SetSet, and I think that’s what David is trying to understand — that ‘force of habit’ that makes us prize functions over cofunctions.

Posted by: John Baez on June 23, 2009 7:12 AM | Permalink | Reply to this

Re: Kan Lifts

Yes: functions are precisely those relations which are left adjoints in RelRel. Why the focus on these, and not as much on the right adjoints?

Similarly, Set C opSet^{C^{op}} is the free cocompletion of a category CC (via Yoneda), whereas (Set op) C op(Set^{op})^{C^{op}} is the free completion (via the opposite of Yoneda). But in some sense the free cocompletion gets much more attention.

I like John’s arrow-of-time or entropy idea, where in favoring many-to-one relations (functions), we are just doing the normal human thing, putting different things into one box [which may be a physical box, like this morning when I was picking up my kids’ toys, or a mental box, i.e., an abstraction], and thus disregarding or losing information or distinctions which we deem irrelevant or unimportant for the time being. It may be superfluous to give examples, but one of the first that comes to mind is putting all fractions that represent the same rational number together in a box: 2/6 and 1/3 are for all intents and purposes regarded as the same.

Decategorification is a kind of normal human act where we identify (and forget) by way of abstracting. Categorification can be seen as an act of remembering where the abstractions originally came from.

It may seem as though words like entropy, losing information, forgetting, and decategorifying are being used here as pejoratives, but of course I don’t mean that: life, and science in particular, would be impossible without such basic maneuvers. There’s that haunting short story by Borges, Funes the Memorious, where a young Uraguayan savant gets thrown off a horse and is in a coma for a few days; when he comes to, he is physically paralyzed but endowed with an infallible memory. He can retrieve, with perfect fidelity, anything he has ever seen, heard, felt, thought, etc., down to the most minute detail:

The voice of Funes, out of the darkness, continued. He told me that toward 1886 he had devised a new system of enumeration and that in a very few days he had gone before twenty-four thousand. He had not written it down, for what he once meditated would not be erased. The first stimulus to his work, I believe, had been his discontent with the fact that “thirty-three Uruguayans” required two symbols and three words, rather than a single word and a single symbol. Later he applied his extravagant principle to the other numbers. In place of seven thousand thirteen, he would say (for example) Máximo Perez; in place of seven thousand fourteen, The Train; other numbers were Luis Melián Lafinur, Olimar, Brimstone, Clubs, The Whale, Gas, The Cauldron, Napoleon, Agustín de Vedia. In lieu of five hundred, he would say nine. Each word had a particular sign, a species of mark; the last were very complicated… . I attempted to explain that this rhapsody of unconnected terms was precisely the contrary of a system of enumeration. I said that to say three hundred and sixty-five was to say three hundreds, six tens, five units: an analysis which does not exist in such numbers as The Negro Timoteo or The Flesh Blanket. Funes did not understand me, or did not wish to understand me.

Locke, in the seventeenth century, postulated (and rejected) an impossible idiom in which each individual object, each stone, each bird and branch had an individual name; Funes had once projected an analogous idiom, but he had renounced it as being too general, too ambiguous. In effect, Funes not only remembered every leaf on every tree of every wood, but even every one of the times he had perceived or imagined it. He determined to reduce all of his past experience to some seventy thousand recollections, which he would later define numerically. Two considerations dissuaded him: the thought that the task was interminable and the thought that it was useless. He knew that at the hour of his death he would scarcely have finished classifying even all the memories of his childhood.

The two projects I have indicated (an infinite vocabulary for the natural series of numbers, and a usable mental catalogue of all the images of memory) are lacking in sense, but they reveal a certain stammering greatness. They allow us to make out dimly, or to infer, the dizzying world of Funes. He was, let us not forget, almost incapable of general, platonic ideas. It was not only difficult for him to understand that the generic term dog embraced so many unlike specimens of differing sizes and different forms; he was disturbed by the fact that a dog at three-fourteen (seen in profile) should have the same name as the dog at three-fifteen (seen from the front). His own face in the mirror, his own hands, surprised him on every occasion. Swift writes that the emperor of Lilliput could discern the movement of the minute hand; Funes could continuously make out the tranquil advances of corruption, of caries, of fatigue. He noted the progress of death, of moisture. He was the solitary and lucid spectator of a multiform world which was instantaneously and almost intolerably exact. Babylon, London, and New York have overawed the imagination of men with their ferocious splendour; no one, in those populous towers or upon those surging avenues, has felt the heat and pressure of a reality as indefatigable as that which day and night converged upon the unfortunate Ireneo in his humble South American farmhouse. It was very difficult for him to sleep. To sleep is to be abstracted from the world; Funes, on his back in his cot, in the shadows, imagined every crevice and every moulding of the various houses which surrounded him. (I repeat, the least important of his recollections was more minutely precise and more lively than our perception of a physical pleasure or a physical torment.) Toward the east, in a section which was not yet cut into blocks of homes, there were some new unknown houses. Funes imagined them black, compact, made of a single obscurity; he would turn his face in this direction in order to sleep. He would also imagine himself at the bottom of the river, being rocked and annihilated by the current.

Without effort, he had learned English, French, Portuguese, Latin. I suspect, nevertheless, that he was not very capable of thought. To think is to forget a difference, to generalize, to abstract. In the overly replete world of Funes there were nothing but details, almost contiguous details.

The equivocal clarity of dawn penetrated along the earthen patio.

Then it was that I saw the face of the voice which had spoken all through the night. Ireneo was nineteen years old; he had been born in 1868; he seemed as monumental as bronze, more ancient than Egypt, anterior to the prophecies and the pyramids. It occurred to me that each one of my words (each one of my gestures) would live on in his implacable memory; I was benumbed by the fear of multiplying superfluous gestures.

Ireneo Funes died in 1889, of a pulmonary congestion.

Posted by: Todd Trimble on June 23, 2009 5:29 PM | Permalink | Reply to this

Funes, forgetting, Plato, Socrates; Re: Kan Lifts

“Funes” is one of my favorite stories.

“Categorification can be seen as an act of remembering where the abstractions originally came from.”

This is oddly Classical – Plato’s notion that [all?] learning is remembering (Socrates; The Meno – the slave boy dialogue - shows that the boy had implicit knowledge of Geometry - knowing without conscious awareness, implicit memory, the unconscious). Plato suggests that we cannot come to know something unless we already know it.

Forgetful functor induced by transmigration of the soul.

You and I may disbelieve some of the assumptions, but find Socratic Method a very powerful tool.

Posted by: Jonathan Vos Post on June 23, 2009 5:41 PM | Permalink | Reply to this

Re: Kan Lifts

Right, but there’s a symmetry breaking required when we go from Rel to Set, and I think that’s what David is trying to understand — that ‘force of habit’ that makes us prize functions over cofunctions.

Yes, I agree entirely (and I think that your suggestion that it's related to the psychological arrow of time is a good one). I just mean to give a more rigorous proof that it is our convention, not anything forced upon us by what is mathematically possible.

Posted by: Toby Bartels on June 24, 2009 12:37 AM | Permalink | Reply to this

Re: Kan Lifts

That raises the question of why allegories are not too visible. We might have been the nn-Allegory Café by now.

Or is it that we might as well go straight to spans, and take relation-like things to be specific kinds of span?

Posted by: David Corfield on June 23, 2009 8:54 AM | Permalink | Reply to this

Re: Kan Lifts

Back here we were thinking about kinds of morphism between sets as {0,1}\{0, 1\}-valued matrices:

  • Unnormalised: Rel;
  • Row normalised: Set;
  • Column normalised: Set opSet^{op};
  • Row and column normalised: Permutations.

And with values in [0,1][0, 1] we have (right/left/doubly) stochastic matrices, etc.

So taking profunctors as a kind of Set-valued matrix, normalisation via unions of entries having cardinality 1 seems to be all that’s on offer.

With groupoid-valued matrices, as in spans of groupoids, could normalisation be considered?

Posted by: David Corfield on June 24, 2009 9:32 AM | Permalink | Reply to this

Re: Kan Lifts

From the examples, I’d almost prefer to take matrices in a topology, and call a column/row normal if it covers the whole space.

Posted by: some guy on the street on July 3, 2009 5:10 AM | Permalink | Reply to this

A slightly different example

Thinking more of that maxim “all concepts are Kan extensions”, the sort of concept that comes to mind most readily is diagramatic constructions — usually initial objects among terminal extensions or vice-versa; and in this case the environment is the place we like to have universal constructions living.

Talking of Kan lifts, though, it seems the sorts of things you want to lift are colorings of a category — if I were patient I’d prove (or disprove — can’t tell right now which) that there ought to be a terminal finitely complete cocomplete category 𝒞\mathcal{C} with 2-of-3-and-retract-closed essentially surjective subcategory 𝒲\mathcal{W} giving a ground-floor picture of localizations; and similarly that there ought to be a terminal model category \mathcal{M} which by terminality of 𝒞\mathcal{C} sits over \mathcal{M}; and then a category 𝒞\mathcal{C}' with weak equivalences 𝒲\mathcal{W}' we want to localize admits a model structure iff there is a lift of the proper functor to 𝒞\mathcal{C} through \mathcal{M}.

Anyway, I can’t tell just yet if that works, but if it did, that’s the sort of thing I’d want to ask of Kan lifts.

Posted by: some guy on the street on July 1, 2009 9:59 PM | Permalink | Reply to this

Post a New Comment