Pullback-homomorphisms

August 1, 2010

Posted by Tom Leinster

$MathML-enabled post (click for more details).$

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 $T$ on some category. A $T$ -algebra is, of course, an object $A$ together with a map $T A \to A$ satisfying some axioms, and a map $f : A \to B$ of $T$ -algebras is a commutative square $\begin{matrix} T A & \overset{T f}{\to} & T B \\ ↓ & ↓ \\ A & \overset{f}{\to} & B . \end{matrix}$ Call $f$ 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?

$MathML-enabled post (click for more details).$

You can get a feel for pullback-homomorphisms by working out what they are for various familiar monads $T$ . 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 $T$ on $Set$ . We have a group homomorphism $f : A \to B$ , and the question is whether the square above is a pullback. That would mean:

for every $a \in A$ and every word $w$ in $B$ that evaluates to $f (a)$ , there is a unique word $v$ in $A$ that evaluates to $a$ and satisfies $(T f) (v) = w$ .

For example, this says that for every $a \in A$ and $b_{1}, b_{2} \in B$ such that $f (a) = b_{1}^{- 3} b_{2}$ , there exist unique $a_{1}, a_{2} \in A$ such that $a = a_{1}^{- 3} a_{2}$ , $f (a_{1}) = b_{1}$ , and $f (a_{2}) = b_{2}$ .

In particular, we can take $a = 1$ . For every $b \in B$ we have $b^{- 1} b = 1 = f (1)$ , so there exist unique $a_{1}, a_{2} \in A$ such that $a_{1}^{- 1} a_{2} = 1$ , $f (a_{1}) = b$ , and $f (a_{2}) = b$ . It follows quickly that $f$ 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 $T$ on $Set$ 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 $ω$ satisfying the equation $ω (x, x, y) = y$ — a ‘one-sided Mal’cev operation’.)

$G$ -sets Fix a group $G$ and let $T$ be the monad $G \times -$ on $Set$ . A map $f : A \to B$ of $G$ -sets is a pullback-homomorphism if and only if:

for all $a \in A$ , $g \in G$ and $b' \in B$ such that $g b' = f (a)$ , there exists a unique $a' \in A$ such that $f (a') = b'$ and $g a' = a$ .

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

So for $G$ -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$ and a category $B$ with pullbacks and small coproducts. Then the functor category $B^{A}$ is monadic over $B^{ob A}$ . Explicitly, the monad $T$ is given by $(T X) (a) = \sum_{u : a' \to a} X a'$ ( $X \in B^{ob A}$ , $a \in A$ ).

A $T$ -algebra is a functor $A \to B$ . A map of $T$ -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 ( $G$ -sets) is a special case. When $A$ is a groupoid, every natural transformation between functors out of $A$ is cartesian. This is why every map of $G$ -sets is a pullback-homomorphism.

Pointed sets Take the monad $1 + -$ on $Set$ , 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 $T$ -algebras and pullback-homomorphisms is equivalent to $Set$ . I think the same is true of the monad $T = E + -$ for any set $E$ .

Sup-lattices Take the powerset monad $T$ on $Set$ . A $T$ -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 $A \to B$ is a pullback-homomorphism if and only if it embeds $A$ as a downwards-closed subset of $B$ .

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

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

given a map $u$ in $A$ and a factorization $F u = v_{2} v_{1}$ in $B$ , there is a unique pair $(u_{1}, u_{2})$ of maps in $A$ such that $F u_{1} = v_{1}$ , $F u_{2} = v_{2}$ , and $u = 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 $T$ be the ultrafilter monad on $Set$ , 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: http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2249

29 Comments & 0 Trackbacks

Re: Pullback-homomorphisms

$MathML-enabled post (click for more details).$

Unrolling the compact Hausdorff space example, pullback homomorphisms imply a reflection of limits-type property. Let $f$ be a pullback homomorphism from $T A \to A$ to $T B \to B$ .

For any ultrafilter $F$ in $T B$ , if there is some $a \in A$ such that $\lim_{B} (F) = f (a)$ , then there exists a unique $F'$ in $T A$ such that $(T f) (F') = F$ and $\lim_{A} (F') = a$ .

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

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

Re: Pullback-homomorphisms

$MathML-enabled post (click for more details).$

I think what can be said is that $f$ 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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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_{1}$ and exponentiable.

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

Re: Pullback-homomorphisms

$MathML-enabled post (click for more details).$

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 $f$ is said to be stably purple if (not only $f$ but also) every pullback of $f$ 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 $f$ of $T$ -algebras is stably a pullback-homomorphism, or more briefly a stable PH, if every pullback of $f$ 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 $T$ preserves pullbacks then a map of $T$ -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.
$G$ -sets: every map is a pullback-homomorphism, and $G \times -$ preserves pullbacks, so every map is a stable PH.
Functors: more generally, the above-mentioned monad on $B^{ob A}$ , whose category of algebras is $B^{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 + -$ (and more generally, $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

$MathML-enabled post (click for more details).$

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 $U ↪ B$ , the inclusion into $B$ of an open subset $U$ . (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

$MathML-enabled post (click for more details).$

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 $A \overset{f}{\to} B \overset{g}{\to} C$ are homomorphisms and $g$ is a pullback-homomorphism, then $f$ is a pullback-homomorphism if and only if $g 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

$MathML-enabled post (click for more details).$

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 $T$ whatsoever, there is a generic-free factorisation system on $Kl (T)$ . If the monad lives on a locally $λ$ -presentable category $𝒞$ , 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 : A \to T 1$ where $A$ is $λ$ -presentable. Now $T / 1 : 𝒞 \to 𝒞 / T 1$ has a left adjoint $L$ say; and the unit of this adjunction at $a$ is a map $η_{a} : A \to T \tilde{a}$ over $T 1$ . This corresponds to a map of free $T$ -algebras $T A \to T \tilde{a}$ ; and from the set $J$ of all such maps we can generate an orthogonal factorisation system $(ℒ, ℛ)$ on $T$ - $Alg$ with $J \subset ℒ$ . I claim that $ℛ$ is the class of pullback-homomorphisms.

Indeed, the class $ℛ$ certainly includes all free maps — those of the form $T f : T X \to T Y$ for some $f : A \to B$ — since every map in $J$ is generic. But now if $X$ and $Y$ are $T$ -algebras, and $f$ a pullback-homomorphism, then the algebra map square

$\begin{matrix} T X & \overset{x}{\to} & X \\ T f ↓ & ↓ f \\ T Y & \overset{y}{\to} & Y \end{matrix}$

is a pullback in $T$ -Alg, and since $T f$ is in $ℛ$ , it follows easily that $f$ is too. So every pullback-homomorphism is in the right class of this factorisation system. Conversely, suppose that $f \in ℛ$ . To show that it’s a pullback homomorphism, it suffices to show that for every commutative square

(1)

\begin{matrix} A & \overset{h}{\to} & X \\ k ↓ & ↓ f \\ T Y & \overset{y}{\to} & Y \end{matrix}

in $𝒞$ , with $A$ a $λ$ -presentable object of $𝒞$ , there’s a unique factorisation through $T X$ . But letting $a : A \to T 1$ be the composite

$A \overset{h}{\to} T X \overset{!}{\to} T 1$

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

$\begin{matrix} A & \overset{h}{\to} & X \\ η_{a} ↓ & ↓ f \\ \tilde{a} & \overset{\bar{k}}{\to} & Y \end{matrix}$

and that to give a factorisation of (1) through $T X$ is equally well to give a diagonal filler for this square. But since $f \in ℛ$ , there’s a unique such filler, and so $f$ is a pullback-homomorphism as required.

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

Re: Pullback-homomorphisms

$MathML-enabled post (click for more details).$

Actually, the argument I just gave that $ℛ$ contains the pullback-homomorphisms is faulty. I claimed that every free map is in $ℛ$ : but that would imply that the multiplication of the monad were cartesian. However, this is easy to fix. To show that $ℛ$ 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

$MathML-enabled post (click for more details).$

Thanks, Joachim and Richard.

These general results tell us, in particular, that

the ULF functors form the right class of a factorization system on $Cat$
for (suitable) categories $A$ and $B$ , the cartesian natural transformations form the right class of a factorization system on $B^{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

$MathML-enabled post (click for more details).$

For the second example, yes: they’re just those functors $A \to B$ whose component at $1$ is an isomorphism.

For the first example: it seems hard. The left class contains the following two maps: the inclusion ${0 < 2} \to {0 < 1 < 2}$ and the surjection ${0 < 1, 1' < 2} \to {0 < 1 < 2}$ (where $1$ and $1'$ are incomparable, and both sent to $1$ ). 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

$MathML-enabled post (click for more details).$

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 $A \to B$ whose component at $1$ 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

$MathML-enabled post (click for more details).$

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 $T$ 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

$MathML-enabled post (click for more details).$

Layer 1

a_{0}

b_{0}

a_{1}

b_{1}

f_{0}

ids

ids

f_{1}

(1)

a_{1} \circ a_{1}

b_{1} \circ b_{1}

a_{1}

b_{1}

f * f

comp

comp

f_{1}

(2)

and

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

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

Layer 1

a_{0}

1_{0}

a_{1}

1_{1} .

1

ids

η_{1}

s

(1')

a_{0}

T a_{0}

!

η_{a_{0}}

T!

The right hand square is a pullback, so the whole thing is a pullback iff $(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_{1}

a_{1}

comp

s

(2')

T^{2} a_{0}

T a_{0}

μ_{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 $E$ lacks a terminal object.

The condition that $(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 $T$ -multicategory.

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

Layer 1

a

b

a'

b'

r

f

g

r'

⇓ h

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

Layer 1

x

y

a'

b'

k

f u

g v

r'

⇓ w

factors uniquely as

Layer 1

a

b

a'

b' .

r

f

g

r'

⇓ h

x

y

k

u

v

⇓ \hat{w}

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

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

Layer 1

a

b

r

p

q

a'

b'

r'

p'

q'

f

g

h

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

Layer 1

a

b

a'

b'

r'

p'

q'

f

g

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

Layer 1

a_{0}

a_{0}

a_{0}

1

1

a_{0}

T a_{0}

a_{1}

t

s

1

η_{a_{0}}

ids

gives precisely the condition that $(1')$ is a pullback. Similarly, the condition that $(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 $T$ -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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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_{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

$MathML-enabled post (click for more details).$

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_{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_{1}$ ).

Before launching into the proof proper, I need a lemma. Let $β$ be the ultrafilter monad. Let $X$ be a topological space, with convergence relation $R$ from $X$ to $β (X)$ , and let $S$ be a relation from $X$ to some set $Y$ . Take a point $x \in X$ and an ultrafilter $𝒱$ on $Y$ . Let’s show that $x (β (S) \cdot R) 𝒱$ iff for all open neighbourhoods $U$ of $x$ ${y \in Y ∣ (\exists x \in U) xSy} \in 𝒱$ .

For any ultrafilter $𝒰$ on $X$ , we have that $𝒰 β (S) 𝒱$ iff for any set $U \in 𝒰$ the set ${y \in Y ∣ (\exists x \in U) xSy}$ is in $𝒱$ . Equivalently, $𝒰$ must contain the complements of all sets which don’t have this property. That is, $𝒰$ must contain all sets $U$ such that ${y \in Y ∣ (\forall x \in X ∖ U) \neg xSy} \in 𝒱$ . The collection of such sets is a filter, which I’ll call $ℱ$ . Now $x (β (S) \cdot R) 𝒱$ iff there is an ultrafilter $𝒰$ with $xR 𝒰$ and $𝒰 β (S) 𝒱$ , that is, such that $𝒰$ contains all open neighbourhoods of $x$ and also extends $ℱ$ .

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

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

There is no ultrafilter which contains $V$ and fails to converge to any $u \in U$ .
There is no ultrafilter which contains $V$ and fails to contain some open neighbourhood $N_{u}$ of each $u$ in $U$ .
For any choice of open neighbourhoods $N_{u}$ of the $u$ in $U$ , there is no ultrafilter which contains $V$ and the complements of all the $N_{u}$ .
For any choice of open neighbourhoods $N_{u}$ of the $u$ in $U$ there is a finite subset $I$ of $U$ such that $V \cap ⋂_{i \in I} N_{i}^{c}$ is empty.
Any open cover of $U$ has a finite subset which covers $V$ .

So the composition cell of a topological space $(X, R)$ is cartesian iff for any $x \in X$ and any open neighbourhood $U$ of $x$ there is another open neighbourhood $V$ of $x$ with the property that any open cover of $U$ has a finite subset which covers $V$ . 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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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 $B$ ” are the generalized multicategories for the monad whose algebras are functors $B \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

$MathML-enabled post (click for more details).$

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

$MathML-enabled post (click for more details).$

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 $T$ -multicategory’ monads in my thesis. What I show is that a map $a \overset{f}{\to} b$ of $T$ -multicategories (in the style of Leinster) is unwirable iff the squares $\begin{matrix} a_{0} & \overset{f_{0}}{\to} & b_{0} & a_{1} \circ a_{1} & \overset{f_{1} ⋆ f_{1}}{\to} & b_{1} \circ b_{1} \\ ids ↓ & (1) & ↓ ids & and & comp ↓ & (2) & ↓ comp \\ a_{1} & \overset{f_{1}}{\to} & b_{1} & a_{1} & \overset{f_{1}}{\to} & b_{1} \end{matrix}$ are both pullbacks. In fact, we only need to require $(2)$ to be a pullback, since it follows from this that $(1)$ is as well.

First, a simplification. We can think of maps of $T$ -multicategories into $A$ as $(T / A)$ -multicategories for a suitably chosen monad $T / A$ , so (by changing the monad if necessary) we can work with $T$ -multicategories, rather than their maps. If $T$ is a pullback-preserving monad on a cartesian $E$ with finite limits, then there is a terminal $T$ -multicategory 1. We say a $T$ -multicategory $A$ is unwirable iff the unique map $!$ from $A$ 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 $T$ -multicategory is the component of $η$ at 1, and so in this case the square $(1)$ factors as $\begin{matrix} a_{0} & \overset{1}{\to} & a_{0} & \overset{!}{\to} & 1 \\ ids ↓ & (1') & ↓ η_{a_{0}} & ↓ η_{1} \\ a_{1} & \overset{s}{\to} & T a_{0} & \overset{T!}{\to} & T 1 . \end{matrix}$ The right hand square is a pullback, so the whole thing is a pullback iff $(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 $\begin{matrix} a_{1} \circ a_{1} & \to & T^{2} a_{0} \\ comp ↓ & (2') & ↓ μ_{a_{0}} \\ a_{1} & \overset{s}{\to} & T a_{1} \end{matrix}$ should be a pullback. This gives a slight generalisation of the notion of unwirable multicategory, since it still works even if the base category $E$ lacks a terminal object.

I’ll briefly review what that means. Recall that a 2-cell $\begin{matrix} a & \overset{r}{\to} & b \\ f ↓ & ⇓ h & ↓ g \\ a' & \overset{r'}{\to} & b' \end{matrix}$ in a weak double category is cartesian iff any 2-cell $\begin{matrix} x & \overset{k}{\to} & y \\ f u ↓ & ⇓ w & ↓ g v \\ a' & \overset{r'}{\to} & b' \end{matrix}$ factors uniquely as $\begin{matrix} x & \overset{k}{\to} & y \\ u ↓ & ⇓ \hat{w} & ↓ v \\ a & \overset{r}{\to} & b \\ f ↓ & ⇓ h & ↓ g \\ a' & \overset{r'}{\to} & b' . \end{matrix}$ A $T$ -multicategory is normalised iff its unit 2-cell is cartesian.

If we’re working with some monad $T$ on a category $E$ , then the context for Leinster-style multicategories is the weak double category of spans in $E$ . A 2-cell $\begin{matrix} a & \overset{p}{\leftarrow} & r & \overset{q}{\to} & b \\ f ↓ & ↓ h & ↓ g \\ a' & \overset{p'}{\leftarrow} & r' & \overset{q'}{\to} & b' \end{matrix}$ in this weak double category is cartesian iff $r$ is the limit of the diagram $\begin{matrix} a & b \\ f ↓ & ↓ g \\ a' & \overset{p'}{\leftarrow} & r' & \overset{q'}{\to} & b' \end{matrix}$ with p, h and q being legs of the limit cone. Applying this to the unit cell $\begin{matrix} a_{0} & \overset{1}{\leftarrow} & a_{0} & \overset{1}{\to} & a_{0} \\ 1 ↓ & ids ↓ & (1') & ↓ η_{a_{0}} \\ a_{0} & \overset{t}{\leftarrow} & a_{1} & \overset{s}{\to} & T a_{0} \end{matrix}$ gives precisely the condition that $(1')$ is a pullback. Similarly, the condition that $(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 $T$ -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:

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

$MathML-enabled post (click for more details).$

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

The n-Category Café

Skip to the Main Content

August 1, 2010