### 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 $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 &\stackrel{T f}{\to} &T B \\
\downarrow & &\downarrow \\
A &\stackrel{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?

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 $\omega$ satisfying the equation $\omega(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 $\mathbf{A}$ and a category
$\mathbf{B}$ with pullbacks and small coproducts. Then the functor category
$\mathbf{B}^\mathbf{A}$ is monadic over $\mathbf{B}^{ob\text{ }\mathbf{A}}$.
Explicitly, the monad $T$ is given by
$(T X)(a) = \sum_{u: a' \to a} X a'$
($X \in \mathbf{B}^{ob\text{ }\mathbf{A}}$, $a \in \mathbf{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 $\mathbf{A}$ is a
groupoid, *every* natural transformation between functors out of
$\mathbf{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.

## Re: Pullback-homomorphisms

Unrolling the compact Hausdorff space example, pullback homomorphisms imply a reflection of limits-type property. Let $f$ be a pullback homomorphism from $T A \rightarrow A$ to $T B \rightarrow 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.