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.

August 1, 2010

Pullback-homomorphisms

Posted by Tom Leinster

Matías Menni and I have been having some interesting conversations about notions of Möbius inversion in categories, prompted by his talk at Category Theory 2010, his recent paper with Bill Lawvere, and my paper a while ago on Euler characteristic of categories.

This post is about an offshoot of our conversation. It solely concerns some very standard notions of category theory. Take a monad TT on some category. A TT-algebra is, of course, an object AA together with a map TAAT A \to A satisfying some axioms, and a map f:ABf: A \to B of TT-algebras is a commutative square TA Tf TB A f B. \begin{matrix} T A &\stackrel{T f}{\to} &T B \\ \downarrow & &\downarrow \\ A &\stackrel{f}{\to} &B. \end{matrix} Call ff a pullback-homomorphism if this square is a pullback.

How should we think about pullback-homomorphisms? What properties do they have? Are they a useful notion? (And is there a better name?)

Surely, surely, someone has looked into this before. Does anyone know anything about it?

You can get a feel for pullback-homomorphisms by working out what they are for various familiar monads TT. The rest of this post will be a bunch of examples of this type. One of them will be the example that led me into this, related to Möbius inversion.

Groups  Let’s begin with the free group monad TT on SetSet. We have a group homomorphism f:ABf: A \to B, and the question is whether the square above is a pullback. That would mean:

for every aAa \in A and every word ww in BB that evaluates to f(a)f(a), there is a unique word vv in AA that evaluates to aa and satisfies (Tf)(v)=w(T f)(v) = w.

For example, this says that for every aAa \in A and b 1,b 2Bb_1, b_2 \in B such that f(a)=b 1 3b 2f(a) = b_1^{-3} b_2, there exist unique a 1,a 2Aa_1, a_2 \in A such that a=a 1 3a 2a = a_1^{-3} a_2, f(a 1)=b 1f(a_1) = b_1, and f(a 2)=b 2f(a_2) = b_2.

In particular, we can take a=1a = 1. For every bBb \in B we have b 1b=1=f(1)b^{-1} b = 1 = f(1), so there exist unique a 1,a 2Aa_1, a_2 \in A such that a 1 1a 2=1a_1^{-1} a_2 = 1, f(a 1)=bf(a_1) = b, and f(a 2)=bf(a_2) = b. It follows quickly that ff is bijective, that is, an isomorphism. And for any monad, every isomorphism is a pullback-homomorphism.

So, for the group monad, the pullback-homomorphisms are just the isomorphisms.

Vector spaces, modules, Lie algebras, …  The same goes for any monad TT on SetSet that, thought of as a theory, contains the theory of groups. The pullback-homomorphisms are just the isomorphisms.

(You can pare it down further: e.g. the same argument also works whenever the theory contains a constant and a ternary operation ω\omega satisfying the equation ω(x,x,y)=y\omega(x, x, y) = y — a ‘one-sided Mal’cev operation’.)

GG-sets  Fix a group GG and let TT be the monad G×G \times - on SetSet. A map f:ABf: A \to B of GG-sets is a pullback-homomorphism if and only if:

for all aAa \in A, gGg \in G and bBb' \in B such that gb=f(a)g b' = f(a), there exists a unique aAa' \in A such that f(a)=bf(a') = b' and ga=ag a' = a.

This always holds: you can and must take a=g 1aa' = g^{-1} a.

So for GG-sets, every homomorphism is a pullback-homomorphism.

In the examples so far, the notion of pullback-homomorphism has been trivial in one sense or the other. It’s either included everything or (essentially) nothing. But in the next example, the notion is non-trivial.

Functors  Take a small category A\mathbf{A} and a category B\mathbf{B} with pullbacks and small coproducts. Then the functor category B A\mathbf{B}^\mathbf{A} is monadic over B ob A\mathbf{B}^{ob\text{ }\mathbf{A}}. Explicitly, the monad TT is given by (TX)(a)= u:aaXa (T X)(a) = \sum_{u: a' \to a} X a' (XB ob AX \in \mathbf{B}^{ob\text{ }\mathbf{A}}, aAa \in \mathbf{A}).

A TT-algebra is a functor ABA \to B. A map of TT-algebras is a natural transformation. And it can be shown that a natural transformation is a pullback-homomorphism if and only if it is cartesian, that is, its naturality squares are pullbacks.

The previous example (GG-sets) is a special case. When A\mathbf{A} is a groupoid, every natural transformation between functors out of A\mathbf{A} is cartesian. This is why every map of GG-sets is a pullback-homomorphism.

Pointed sets  Take the monad 1+1 + - on SetSet, whose algebras are pointed sets. The category of algebras is equivalent to the category of sets and partial functions. Under this equivalence, the pullback-homomorphisms correspond to the total functions.

So, the category of TT-algebras and pullback-homomorphisms is equivalent to SetSet. I think the same is true of the monad T=E+T = E + - for any set EE.

Sup-lattices  Take the powerset monad TT on SetSet. A TT-algebra is a sup-lattice, that is, a poset with all joins. A homomorphism is a join-preserving map. If my calculations are correct, a homomorphism ABA \to B is a pullback-homomorphism if and only if it embeds AA as a downwards-closed subset of BB.

Categories  This is the example that started me thinking about this. Take the free category monad TT on the category of directed graphs. A TT-algebra is a category, and a homomorphism of TT-algebras is a functor.

It’s not too hard to show that a functor F:ABF: A \to B is a pullback-homomorphism if and only if it has unique lifting of factorizations. This means:

given a map uu in AA and a factorization Fu=v 2v 1F u = v_2 v_1 in BB, there is a unique pair (u 1,u 2)(u_1, u_2) of maps in AA such that Fu 1=v 1F u_1 = v_1, Fu 2=v 2F u_2 = v_2, and u=u 2u 1u = u_2 u_1.

(You might expect this condition on binary composition to be accompanied by a condition on nullary composition, i.e. identities. But in fact that nullary condition comes for free.)

Having unique lifting of factorizations (ULF) is a crucial property in the study of Möbius categories, as Lawvere and Menni’s paper shows. It was in an effort to understand this property that I started thinking about pullback-homomorphisms. On page 230 they say that ‘the definition of ULF-functor should be compared with that of local homeomorphism’. I don’t know how literally to take this, but it made me consider the next (and final) example:

Compact Hausdorff spaces  Let TT be the ultrafilter monad on SetSet, whose algebras are compact Hausdorff spaces. What are the pullback-homomorphisms? I don’t know.

Posted at August 1, 2010 12:16 PM UTC

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

29 Comments & 0 Trackbacks

Re: Pullback-homomorphisms

Unrolling the compact Hausdorff space example, pullback homomorphisms imply a reflection of limits-type property. Let ff be a pullback homomorphism from TAAT A \rightarrow A to TBBT B \rightarrow B.

For any ultrafilter FF in TBT B, if there is some aAa \in A such that lim B(F)=f(a)\lim_B(F) = f(a), then there exists a unique FF' in TAT A such that (Tf)(F)=F(T f)(F') = F and lim A(F)=a\lim_A(F') = a.

I’m not much of a whiz with filters, but I suspect this property coincides with something pretty familiar, like ff being open.

Posted by: Aleks Kissinger on August 1, 2010 11:59 PM | Permalink | Reply to this

Re: Pullback-homomorphisms

I think what can be said is that ff is a local homeomorphism if and only if it, and any pullback of it, is a pullback-homomorphism. Cf. “Local homeomorphisms via ultrafilter convergence” by Clementino, Hofmann, and Janelidze.

Posted by: Mike Shulman on August 2, 2010 1:00 AM | Permalink | Reply to this

Re: Pullback-homomorphisms

How do you know these things, Mike?

Here’s a link to that paper of Clementino, Hofmann and Janelidze.

Posted by: Tom Leinster on August 2, 2010 1:06 AM | Permalink | Reply to this

Re: Pullback-homomorphisms

How do you know these things, Mike?

Do you mean, how did I happen to have read that particular paper? I think I stumbled upon it while reading about generalized multicategories, and in particular how interesting properties of topological spaces can be described by viewing them in that language.

In case anyone out there is curious, I believe I recall that open, proper, and proper+separated maps can be characterized in more or less the way you would expect: open maps have the nonunique lifting property similar to local homeomorphisms (I don’t remember whether there’s a pullback-stability here), proper maps have the lifting property in the other direction (an ultrafilter upstairs which converges downstairs must converge to something upstairs which maps down onto the limit downstairs), and proper+separated maps have unique forwards lifting.

Another one that I only learned recently is that if you view a topological space as a lax algebra for the ultrafilter monad in Rel, then it is a pseudo (= strict) algebra precisely when it is both T 1T_1 and exponentiable.

Posted by: Mike Shulman on August 2, 2010 7:08 AM | Permalink | Reply to this

Re: Pullback-homomorphisms

I wonder if pullback-homomorphisms are not quite the right thing to focus on.

To explain myself I need some terminology. Topos theorists use the following terminological system: if purple is a property of maps, then a map ff is said to be stably purple if (not only ff but also) every pullback of ff is purple. I get the impression that in topos theory, one often starts by thinking about purple maps, then realizes that it’s also necessary to think about stably purple maps.

So, we might say that a map ff of TT-algebras is stably a pullback-homomorphism, or more briefly a stable PH, if every pullback of ff is a pullback-homomorphism. This is, in general, a stronger property than being a pullback-homomorphism.

Mike pointed out that for the ultrafilter monad, the stable PHs are the local homeomorphisms.

Lemma  If TT preserves pullbacks then a map of TT-algebras is a pullback-homomorphism iff it is a stable PH.

The proof is a standard argument involving pasting of pullback squares.

In most of the examples of monads that I gave in the original post, every pullback-homomorphism is stably so.

  • Groups, vector spaces, modules, Lie algebras: the (stable) PHs are just the isomorphisms.
  • GG-sets: every map is a pullback-homomorphism, and G×G\times- preserves pullbacks, so every map is a stable PH.
  • Functors: more generally, the above-mentioned monad on B ob A\mathbf{B}^{ob\text{ }\mathbf{A}}, whose category of algebras is B A\mathbf{B}^\mathbf{A}, preserves pullbacks. So the stable PHs are the same as the PHs, which are the cartesian natural transformations.
  • Pointed sets: once more, the functor 1+1+- (and more generally, E+E + -) preserves pullbacks, so there’s no change here.
  • Categories: this is the example I really care about. And, once again, there’s no change: the free category monad on directed graphs preserves pullbacks, so the stable PHs are the same as the PHs, which are the functors with unique lifting of factorizations.

The last example together with the compact Hausdorff space example make rather precise Lawvere and Menni’s suggestion that functors with unique lifting of factorizations should be likened to local homeomorphisms. The only fly in the ointment is that for most of the local homeomorphisms that I, at least, usually think about (e.g. open covers), the domain is not compact Hausdorff.

Posted by: Tom Leinster on August 2, 2010 12:10 PM | Permalink | Reply to this

Re: Pullback-homomorphisms

Right — I agree with your intuition.

At first I was wondering whether the pullback-homomorphisms might literally be the local homeomorphisms. The trouble is, we’re dealing with compact Hausdorff spaces here. So, for instance, we’re never going to see a map like UBU \hookrightarrow B, the inclusion into BB of an open subset UU. (This is a simple example of a local homeomorphism.)

But I can’t think of any reason why the pullback-homomorphisms couldn’t be the open maps, as you suggest.

Posted by: Tom Leinster on August 2, 2010 1:00 AM | Permalink | Reply to this

Re: Pullback-homomorphisms

I meant to put the following in the original post, but it slipped my mind.

Pullback-homomorphisms satisfy a kind of “three for two” property. But it’s not the usual symmetric one; it’s more like the actual sitation in shops, where you only get the cheapest item for free.

That is: if AfBgC A \stackrel{f}{\to} B \stackrel{g}{\to} C are homomorphisms and gg is a pullback-homomorphism, then ff is a pullback-homomorphism if and only if gfg f is. This follows from a standard lemma about pullbacks.

I guess I already used, implicitly, the fact that algebras and pullback-homomorphisms form a category.

So, for instance, we might disprove the conjecture “pullback-homomorphisms of compact Hausdorff spaces are just local homeomorphisms” (see comments above) by showing that local homeomorphisms don’t have this three-for-two property.

Posted by: Tom Leinster on August 2, 2010 1:13 AM | Permalink | Reply to this

Re: Pullback-homomorphisms

I think that whenever T has rank, and the category it lives on is locally presentable, the pullback-homomorphisms will be the right class of an orthogonal factorisation system. The three-for-two property that you mention is a consequence of this.

Richard

Posted by: Richard Garner on August 2, 2010 2:00 PM | Permalink | Reply to this

Re: Pullback-homomorphisms

Hi Tom,

a few wild ideas that occurred to me, that might or might
not lead to anything. Or typically be plain wrong…

The pullback-homomorphisms should be related to Joyal’s
axiomatic notion of etale map (cf. Joyal-Moerdijk, ‘Completeness
theorems for open maps’). The main example of a notion of
etale map is in a presheaf topos to declare the cartesian
natural transformations to be etale, let’s just work with that
notion. (The paper shows that every class of etale maps in a
topos is induced from this example via some geometric morphism.)
So this is already related to your example of cartesian natural
transformations.

To find the relationship we could map the categories of
algebras into presheaf categories. For this we have your
nerve theorem, and its generalisations.

So suppose T is a local right adjoint cartesian monad on
a presheaf topos. Then there is a generic-free factorisation
system, and the free maps seem to be pullback-homomorphisms.
I conjecture (or at least speculate) that the pullback-
homomorphisms in the category of algebras have etale nerves,
or perhaps even are precisely the intersection of the image
of the nerve functor with the etale maps.

It seems to work for Cat and the ULF functors…

Some other of your examples are covered by the setup too,
and more if we generalise to cartesian monads with arities…

Cheers,
Joachim.

Posted by: Joachim Kock on August 2, 2010 10:01 PM | Permalink | Reply to this

Re: Pullback-homomorphisms

After some thought last night I came to a similar conclusion. I earlier said that having rank was enough to get a factorisation system with pullback-homomorphisms as the right class; I no longer think that’s right: you need to be parametric right adjoint.

For any parametric right adjoint monad TT whatsoever, there is a generic-free factorisation system on Kl(T)\mathbf{Kl}(T). If the monad lives on a locally λ\lambda-presentable category 𝒞\mathcal{C}, this factorisation system extends to one the category of algebras, whose right class is comprised of the pullback-homomorphisms.

To see this, consider the set of all (isomorphism classes of) maps a:AT1a \colon A \to T1 where AA is λ\lambda-presentable. Now T/1:𝒞𝒞/T1T/1 \colon \mathcal{C} \to \mathcal{C}/T1 has a left adjoint LL say; and the unit of this adjunction at aa is a map η a:ATa˜\eta_a \colon A \to T\tilde a over T1T1. This corresponds to a map of free TT-algebras TATa˜T A \to T \tilde a; and from the set JJ of all such maps we can generate an orthogonal factorisation system (,)(\mathcal{L}, \mathcal{R}) on TT-Alg\mathbf{Alg} with JJ \subset \mathcal{L}. I claim that \mathcal{R} is the class of pullback-homomorphisms.

Indeed, the class \mathcal{R} certainly includes all free maps — those of the form Tf:TXTYT f \colon T X \to T Y for some f:ABf \colon A \to B — since every map in JJ is generic. But now if XX and YY are TT-algebras, and ff a pullback-homomorphism, then the algebra map square

TX x X Tf f TY y Y \array{ T X & \stackrel{x}{\to} & X \\ T f\downarrow && \downarrow f \\ T Y & \stackrel{y}{\to} & Y }

is a pullback in TT-Alg, and since TfT f is in \mathcal{R}, it follows easily that ff is too. So every pullback-homomorphism is in the right class of this factorisation system. Conversely, suppose that ff \in \mathcal{R}. To show that it’s a pullback homomorphism, it suffices to show that for every commutative square

(1)A h X k f TY y Y \array{ A & \stackrel{h}{\to} & X \\ k\downarrow && \downarrow f \\ T Y & \stackrel{y}{\to} & Y }

in 𝒞\mathcal{C}, with AA a λ\lambda-presentable object of 𝒞\mathcal{C}, there’s a unique factorisation through TXT X. But letting a:AT1a \colon A \to T1 be the composite

AhTX!T1 A \stackrel{h}{\to} T X \stackrel{!}{\to} T1

we see that to give the commutative diagram (1) is equally well to give a commutative diagram

A h X η a f a˜ k¯ Y \array{ A & \stackrel{h}{\to} & X \\ \eta_a \downarrow && \downarrow f \\ \tilde a & \stackrel{\bar k}{\to} & Y }

and that to give a factorisation of (1) through TXT X is equally well to give a diagonal filler for this square. But since ff \in \mathcal{R}, there’s a unique such filler, and so ff is a pullback-homomorphism as required.

Posted by: Richard Garner on August 2, 2010 11:18 PM | Permalink | Reply to this

Re: Pullback-homomorphisms

Actually, the argument I just gave that \mathcal{R} contains the pullback-homomorphisms is faulty. I claimed that every free map is in \mathcal{R}: but that would imply that the multiplication of the monad were cartesian. However, this is easy to fix. To show that \mathcal{R} contains the pullback-homomorphisms, just run the argument showing the converse, in reverse.

Posted by: Richard Garner on August 3, 2010 12:10 AM | Permalink | Reply to this

Re: Pullback-homomorphisms

Thanks, Joachim and Richard.

These general results tell us, in particular, that

  • the ULF functors form the right class of a factorization system on CatCat
  • for (suitable) categories A\mathbf{A} and B\mathbf{B}, the cartesian natural transformations form the right class of a factorization system on B A\mathbf{B}^\mathbf{A}.

Can you describe the left classes any more directly than “they are what they have to be”?

Posted by: Tom Leinster on August 3, 2010 12:37 PM | Permalink | Reply to this

Re: Pullback-homomorphisms

For the second example, yes: they’re just those functors AB\mathbf{A} \to \mathbf{B} whose component at 11 is an isomorphism.

For the first example: it seems hard. The left class contains the following two maps: the inclusion {0<2}{0<1<2}\{0 \lt 2\} \to \{0 \lt 1 \lt 2\} and the surjection {0<1,1<2}{0<1<2}\{0 \lt 1, 1' \lt 2\} \to \{0 \lt 1 \lt 2\} (where 11 and 11' are incomparable, and both sent to 11). Moreover, anything in the left class is a countable composite of pushouts of these two maps. But I can’t see a simple characterisation…

Posted by: Richard Garner on August 4, 2010 12:16 PM | Permalink | Reply to this

Re: Pullback-homomorphisms

Re the second example: good. That’s nice and easy. (For the sake of posterity: I’m sure you mean those natural transformations between functors AB\mathbf{A} \to \mathbf{B} whose component at 11 is an isomorphism.)

Re the first example: thanks. There’s something similar in Ross Street’s paper ‘Categorical structures’, my copy of which I can’t find, but there’s a mention of the relevant result on page 2 of this paper of Krzysztof Worytkiewicz.

Posted by: Tom Leinster on August 5, 2010 12:09 AM | Permalink | Reply to this

Re: Pullback-homomorphisms

Nathan Bowler at Cambridge got in touch to tell me that he’s been studying what I call pullback-homomorphisms. He calls them unwirable maps. He sticks to the case where TT preserves pullbacks, and concentrates on free multicategory monads.

You can find this in his thesis, which is currently awaiting examination.

Posted by: Tom Leinster on August 14, 2010 2:35 PM | Permalink | Reply to this

Re: Pullback-homomorphisms

As Tom says, I pay particular attention to `free TT-multicategory’ monads in my thesis. What I show is that a map afba \stackrel{f}{\to} b of TT-multicategories (in the style of Leinster) is unwirable iff the squares

Layer 1 a 0a_0 b 0b_0 a 1a_1 b 1b_1 f 0f_0 idsids idsids f 1f_1 (1)(1) a 1a 1a_1 \circ a_1 b 1b 1b_1 \circ b_1 a 1a_1 b 1b_1 f*ff * f compcomp compcomp f 1f_1 (2)(2) and

are both pullbacks. In fact, we only need to require (2)(2) to be a pullback, since it follows from this that (1)(1) is as well.

This condition makes sense even if if there is no `free TT-multicategory’ monad, and we can take it as the definition of unwirable map of TT-multicategories (in the style of Leinster) for any cartesian monad TT. However, it turns out that we can generalise this definition a fair bit further.

First, a simplification. We can think of maps of TT-multicategories into AA as (T/A)(T/A)-multicategories for a suitably chosen monad T/AT/A, so (by changing the monad if necessary) we can work with TT-multicategories, rather than their maps. If TT is a pullback-preserving monad on a cartesian EE with finite limits, then there is a terminal TT-multicategory 1. We say a TT-multicategory AA is unwirable iff the unique map !! from AA to 1 is unwirable. The reliance on a terminal object is a little annoying, but in fact it can be avoided. After all, the unit map of the terminal TT-multicategory is the component of η\eta at 1, and so in this case the square (1)(1) factors as

Layer 1 a 0a_0 1 01_0 a 1a_1 1 1.1_1 \, . 11 idsids η 1\eta_1 ss (1)(1') a 0a_0 Ta 0T a_0 !! η a 0\eta_{a_0} T!T !

The right hand square is a pullback, so the whole thing is a pullback iff (1)(1') is a pullback. This makes no mention of the terminal object. We may similarly replace the second condition by the condition that the square

Layer 1 a 1*a 1a_1 * a_1 a 1a_1 compcomp ss (2)(2') T 2a 0T^2 a_0 Ta 0T a_0 μ a 0\mu_{a_0}

should be a pullback. This gives a slight generalisation of the notion of unwirable multicategory, since it still works even if the base category EE lacks a terminal object.

The condition that (1)(1') should be a pullback immediately generalises further, to multicategories in the sense of Cruttwell and Shulman. In fact, this condition is the specialisation to the case of multicategories in the sense of Leinster of Cruttwell and Shulman’s notion of a normalised TT-multicategory.

I’ll briefly review what that means. Recall that a 2-cell

Layer 1 aa bb aa' bb' rr ff gg rr' h\Downarrow h

in a weak double category is cartesian iff any 2-cell

Layer 1 xx yy aa' bb' kk fuf u gvg v rr' w\Downarrow w

factors uniquely as

Layer 1 aa bb aa' b.b' \, . rr ff gg rr' h\Downarrow h xx yy kk uu vv w^\Downarrow \widehat{w}

A TT-multicategory is normalised iff its unit 2-cell is cartesian.

If we’re working with some monad TT on a category EE, then the context for Leinster-style multicategories is the weak double category of spans in EE. A 2-cell

Layer 1 aa bb rr pp qq aa' bb' rr' pp' qq' ff gg hh

in this weak double category is cartesian iff rr is the limit of the diagram

Layer 1 aa bb aa' bb' rr' pp' qq' ff gg

with p, h and q being legs of the limit cone. Applying this to the unit cell

Layer 1 a 0a_0 a 0a_0 a 0a_0 11 11 a 0a_0 Ta 0T a_0 a 1a_1 tt ss 11 η a 0\eta_{a_0} idsids

gives precisely the condition that (1)(1') is a pullback. Similarly, the condition that (2)(2') is a pullback also corresponds to a simple condition in Cruttwell and Shulman’s world, namely that the composition 2-cell be cartesian. All of this motivates the definition:

A TT-multicategory (in the sense of Cruttwell and Shulman) is unwirable iff both the unit and composition 2-cells are cartesian.

There are now some very obvious questions to ask:

1. How much of what we can say about unwirable multicategories in the sense of Leinster carries over to this context? For example, does the condition that ids be cartesian follow from the condition that comp be cartesian?

2. Are there any interesting examples outside Leinster’s context? For example, what is an unwirable topological space?

Posted by: Nathan Bowler on August 16, 2010 1:51 PM | Permalink | Reply to this

Re: Pullback-homomorphisms

Hmm, is it just my browser? I can see the arrows in the diagrams, but none of the labels (vertices or edges). Can other people see the labels?

I’ll check on a more up-to-date browser soon.

Posted by: Tom Leinster on August 16, 2010 9:22 PM | Permalink | Reply to this

Re: Pullback-homomorphisms

I see the labels fine in Firefox 3.6.8.

Posted by: Rod McGuire on August 16, 2010 10:20 PM | Permalink | Reply to this

Re: Pullback-homomorphisms

OK, thanks. Sounds like it’s my problem.

Posted by: Tom Leinster on August 16, 2010 10:21 PM | Permalink | Reply to this

Re: Pullback-homomorphisms

That’s very interesting! I haven’t really thought about when the multiplication cell is cartesian.

One slightly odd thing is that if you view generalized multicategories as special sorts of lax algebras in the horizontal bicategory, then they are normalized iff they are normal lax algebras, but being a pseudo algebra is different than the multiplication cell being cartesian. A topological space is a pseudo algebra for the ultrafilter monad iff it is T 1T_1 (= normalized) and exponentiable. I’d be interested to hear if you or anyone else works out when a topological space is unwirable.

Posted by: Mike Shulman on August 20, 2010 4:47 AM | Permalink | Reply to this

Re: Pullback-homomorphisms

I’m sorry that I’ve taken so long to get back to this, but I have now worked out what an unwirable topological space is. In this case, it’s just the same as being a pseudo algebra for the ultrafilter monad: a topological space is unwirable iff it is T 1T_1 and exponentiable. Indeed, the composition cell of a topological space is cartesian iff that topological space is exponentiable. I’ll prove this at the end of the comment.

If we interpret topological spaces as the normalised multicategories in Mod(Rel) rather than the multicategories in Rel, we get that a topological space is exponentiable iff it is unwirable. Suggestively, this link to exponentiability also holds for all nice enough Leinster-type multicategories (this is partly explained in my thesis), but I haven’t yet worked out what can be said in your context.

We now have an answer to the second of the questions I asked, and also to the first. The indiscrete topological space on two points has cartesian composition cell (since it is exponentiable) but doesn’t have cartesian identity cell (since it isn’t T 1T_1).

Before launching into the proof proper, I need a lemma. Let β\beta be the ultrafilter monad. Let XX be a topological space, with convergence relation RR from XX to β(X)\beta(X), and let SS be a relation from XX to some set YY. Take a point xXx \in X and an ultrafilter 𝒱\mathcal{V} on YY. Let’s show that x(β(S)R)𝒱x (\beta(S) \cdot R) \mathcal{V} iff for all open neighbourhoods UU of xx {yY|(xU)xSy}𝒱\{y \in Y|(\exists x \in U) xSy\} \in \mathcal{V}.

For any ultrafilter 𝒰\mathcal{U} on XX, we have that 𝒰β(S)𝒱\mathcal{U} \beta(S) \mathcal{V} iff for any set U𝒰U \in \mathcal{U} the set {yY|(xU)xSy}\{y \in Y | (\exists x \in U) xSy\} is in 𝒱\mathcal{V}. Equivalently, 𝒰\mathcal{U} must contain the complements of all sets which don’t have this property. That is, 𝒰\mathcal{U} must contain all sets UU such that {yY|(xXU)¬xSy}𝒱\{y \in Y | (\forall x \in X \setminus U) \not xSy\} \in \mathcal{V}. The collection of such sets is a filter, which I’ll call \mathcal{F}. Now x(β(S)R)𝒱x (\beta(S) \cdot R) \mathcal{V} iff there is an ultrafilter 𝒰\mathcal{U} with xR𝒰xR\mathcal{U} and 𝒰β(S)𝒱\mathcal{U} \beta(S) \mathcal{V}, that is, such that 𝒰\mathcal{U} contains all open neighbourhoods of xx and also extends \mathcal{F}.

There is such an ultrafilter iff the union of \mathcal{F} with the set of open neighbourhoods of xx has the finite intersection property iff the intersection of any open neighbourhood of xx with any element of \mathcal{F} is nonempty iff the complement of any open neighbourhood of xx isn’t in \mathcal{F} iff every open neighbourhood UU of xx satisfies {yY|(xU)xSy}𝒱\{y \in Y|(\exists x \in U) xSy\} \in \mathcal{V}, as required.

Thus the composition cell of a topological space (X,R)(X, R) is cartesian iff for any xXx \in X and any ultrafilter 𝒱\mathcal{V} on β(X)\beta(X) containing all sets {𝒰|V𝒰}\{\mathcal{U} | V \in \mathcal{U}\} for VV an open neighbourhood of xx, 𝒱\mathcal{V} also contains all sets {𝒰|(xU)xR𝒰}\{\mathcal{U} | (\exists x \in U) xR\mathcal{U}\} for UU an open neighbourhood of xx. That is, for each open neighbourhood UU of xx there must be an open neighbourhood VV of xx such that for all ultrafilters 𝒰\mathcal{U} on XX V𝒰(xU)xR𝒰V \in \mathcal{U} \rightarrow (\exists x \in U) xR\mathcal{U}. This property of UU and VV reduces successively to the following properties:

  • There is no ultrafilter which contains VV and fails to converge to any uUu \in U.
  • There is no ultrafilter which contains VV and fails to contain some open neighbourhood N uN_u of each uu in UU.
  • For any choice of open neighbourhoods N uN_u of the uu in UU, there is no ultrafilter which contains VV and the complements of all the N uN_u.
  • For any choice of open neighbourhoods N uN_u of the uu in UU there is a finite subset II of UU such that V iIN i cV \cap \bigcap_{i \in I}N_i^c is empty.
  • Any open cover of UU has a finite subset which covers VV.

So the composition cell of a topological space (X,R)(X, R) is cartesian iff for any xXx \in X and any open neighbourhood UU of xx there is another open neighbourhood VV of xx with the property that any open cover of UU has a finite subset which covers VV. This condition, called quasi local compactness, is known to be equivalent to exponentiability.

Posted by: Nathan Bowler on September 28, 2010 6:21 PM | Permalink | Reply to this

Re: Pullback-homomorphisms

Nice! Are you going to write this up?

Posted by: Tom Leinster on October 2, 2010 4:24 PM | Permalink | Reply to this

Re: Pullback-homomorphisms

Yes, I plan to. However, I have a suspicion that there is something pretty general to be said here, so I’ll tinker with possibilities for that for a few weeks first. I’ll be talking about what sort of thing I think might be true at the Octoberfest.

Posted by: Nathan Bowler on October 4, 2010 12:58 PM | Permalink | Reply to this

Re: Pullback-homomorphisms

Will you post slides or notes online for those of us who can’t make it to Octoberfest?

Posted by: Mike Shulman on October 4, 2010 9:35 PM | Permalink | Reply to this

Re: Pullback-homomorphisms

Yes, I’ll put my slides up, together with any helpful responses I get from the audience.

Nathan

Posted by: Nathan Bowler on October 5, 2010 3:40 PM | Permalink | Reply to this

Re: Pullback-homomorphisms

Nathan, if you’re still following this thread – have you got any slides or notes from the Octoberfest yet? Geoff told me that you found that unwirability is equivalent to exponentiability in “most cases”, which sounds exciting. I started wondering today whether that includes Conduche functors, since “functors with codomain BB” are the generalized multicategories for the monad whose algebras are functors BCatB\to Cat, and as Tom mentioned above being unwirable for categories has something to do with factorization-lifting. Perhaps you’ve already considered that case?

Posted by: Mike Shulman on November 3, 2010 5:58 AM | Permalink | Reply to this

Re: Pullback-homomorphisms

Very cool. I don’t have time to work through your proof carefully, but it seems plausible. It’s quite neat that both notions turn out to be equivalent to exponentiability.

Posted by: Mike Shulman on September 30, 2010 8:55 PM | Permalink | Reply to this

Re: Pullback-homomorphisms

Sorry about that. Here’s how it might have looked in an alternate universe where I rendered the diagrams more crudely.

As Tom says, I pay particular attention to `free TT-multicategory’ monads in my thesis. What I show is that a map afba \stackrel{f}{\to} b of TT-multicategories (in the style of Leinster) is unwirable iff the squares a 0 f 0 b 0 a 1a 1 f 1f 1 b 1b 1 ids (1) ids and comp (2) comp a 1 f 1 b 1 a 1 f 1 b 1 \array{ \;\;\;\; a_0 & \stackrel{f_0}{\to} & b_0 &&&& \;\;\;\;\; a_1 \circ a_1 & \stackrel{f_1 \star f_1}{\to} & b_1 \circ b_1 \\ ids \downarrow &(1)& \;\; \downarrow ids && and && comp \downarrow &(2)& \;\;\;\; \downarrow comp \\ \;\;\;\; a_1 & \stackrel{f_1}{\to} & b_1 &&&& \;\;\;\;\;\;\;\; a_1 & \stackrel{f_1}{\to} & b_1 \\ } are both pullbacks. In fact, we only need to require (2)(2) to be a pullback, since it follows from this that (1)(1) is as well.

This condition makes sense even if if there is no `free TT-multicategory’ monad, and we can take it as the definition of unwirable map of TT-multicategories (in the style of Leinster) for any cartesian monad TT. However, it turns out that we can generalise this definition a fair bit further.

First, a simplification. We can think of maps of TT-multicategories into AA as (T/A)(T/A)-multicategories for a suitably chosen monad T/AT/A, so (by changing the monad if necessary) we can work with TT-multicategories, rather than their maps. If TT is a pullback-preserving monad on a cartesian EE with finite limits, then there is a terminal TT-multicategory 1. We say a TT-multicategory AA is unwirable iff the unique map !! from AA to 1 is unwirable. The reliance on a terminal object is a little annoying, but in fact it can be avoided. After all, the unit map of the terminal TT-multicategory is the component of η\eta at 1, and so in this case the square (1)(1) factors as a 0 1 a 0 ! 1 ids (1) η a 0 η 1 a 1 s Ta 0 T! T1. \array{ \;\;\;\; a_0 & \stackrel{1}{\to} & a_0 & \stackrel{!}{\to} & 1 \\ ids \downarrow &(1')& \;\;\downarrow \eta_{a_0} && \;\; \downarrow \eta_1 \\ \;\;\;\; a_1 & \stackrel{s}{\to} & T a_0 & \stackrel{T !}{\to} & \; T 1 \, .\\ } The right hand square is a pullback, so the whole thing is a pullback iff (1)(1') is a pullback. This makes no mention of the terminal object. We may similarly replace the second condition by the condition that the square a 1a 1 T 2a 0 comp (2) μ a 0 a 1 s Ta 1 \array{ \;\;\;\;\; a_1 \circ a_1 & \to & T^2 a_0 \\ comp \downarrow &(2')& \;\; \downarrow \mu_{a_0} \\ \;\;\;\;\;\;\;\; a_1 & \stackrel{s}{\to} & T a_1 \\ } should be a pullback. This gives a slight generalisation of the notion of unwirable multicategory, since it still works even if the base category EE lacks a terminal object.

The condition that (1)(1') should be a pullback immediately generalises further, to multicategories in the sense of Cruttwell and Shulman. In fact, this condition is the specialisation to the case of multicategories in the sense of Leinster of Cruttwell and Shulman’s notion of a normalised TT-multicategory.

I’ll briefly review what that means. Recall that a 2-cell a r b f h g a r b \array{ \;\; a & \stackrel{r}{\to} & b \\ f \downarrow & \Downarrow h & \; \downarrow g \\ \;\; a' & \stackrel{r'}{\to} & b' \\ } in a weak double category is cartesian iff any 2-cell x k y fu w gv a r b \array{ \;\;\;\; x & \stackrel{k}{\to} & y \\ f u \downarrow & \Downarrow w & \;\; \downarrow g v \\ \;\;\;\; a' & \stackrel{r'}{\to} & b' \\ } factors uniquely as x k y u w^ v a r b f h g a r b. \array{ \;\; x & \stackrel{k}{\to} & y \\ u \downarrow & \Downarrow \widehat{w} & \; \downarrow v \\ \;\; a & \stackrel{r}{\to} & b \\ f \downarrow & \Downarrow h & \; \downarrow g \\ \;\; a' & \stackrel{r'}{\to} & \; b' \, . \\ } A TT-multicategory is normalised iff its unit 2-cell is cartesian.

If we’re working with some monad TT on a category EE, then the context for Leinster-style multicategories is the weak double category of spans in EE. A 2-cell a p r q b f h g a p r q b \array{ \;\; a & \stackrel{p}{\leftarrow} & r & \stackrel{q}{\to} & b \\ f \downarrow & & \; \downarrow h & & \; \downarrow g \\ \;\; a' & \stackrel{p'}{\leftarrow} & r' & \stackrel{q'}{\to} & b' \\ } in this weak double category is cartesian iff rr is the limit of the diagram a b f g a p r q b \array{ \;\; a & & & & b \\ f \downarrow & & & & \; \downarrow g \\ \;\; a' & \stackrel{p'}{\leftarrow} & r' & \stackrel{q'}{\to} & b' \\ } with p, h and q being legs of the limit cone. Applying this to the unit cell a 0 1 a 0 1 a 0 1 ids (1) η a 0 a 0 t a 1 s Ta 0 \array{ \;\; a_0 & \stackrel{1}{\leftarrow} & \;\;\;\; a_0 & \stackrel{1}{\to} & a_0 \\ 1 \downarrow & & ids \downarrow & (1') & \;\; \downarrow \eta_{a_0} \\ \;\; a_0 & \stackrel{t}{\leftarrow} & \;\;\;\; a_1 & \stackrel{s}{\to} & T a_0 \\ } gives precisely the condition that (1)(1') is a pullback. Similarly, the condition that (2)(2') is a pullback also corresponds to a simple condition in Cruttwell and Shulman’s world, namely that the composition 2-cell be cartesian. All of this motivates the definition:

A TT-multicategory (in the sense of Cruttwell and Shulman) is unwirable iff both the unit and composition 2-cells are cartesian.

There are now some very obvious questions to ask:

1. How much of what we can say about unwirable multicategories in the sense of Leinster carries over to this context? For example, does the condition that ids be cartesian follow from the condition that comp be cartesian?

2. Are there any interesting examples outside Leinster’s context? For example, what is an unwirable topological space?

Posted by: Nathan Bowler on August 17, 2010 11:32 AM | Permalink | Reply to this

Re: Pullback-homomorphisms

Thanks! You didn’t have to do that—I was just going to fix my browser. Very kind of you.

Posted by: Tom Leinster on August 17, 2010 4:58 PM | Permalink | Reply to this

Post a New Comment