6
$\begingroup$

In the category Set of sets and functions, consider the functor F(X) = X * X where * is the product (its action on arrows is just F(f) = f * f). Does this functor preserve pushouts? Or at least pushouts of pairs of epimorpisms?

$\endgroup$
4
  • 5
    $\begingroup$ I cannot tell you the answer off the top of my head, but the one of the first things that I do when I have problems like this is to try it on some simple examples (finite set examples). $\endgroup$ Oct 8, 2011 at 0:16
  • 1
    $\begingroup$ @Spice: I follow that advice myself very frequently. Sometimes one should, at the outset, ignore fancy category theory and draw humble little pictures of things, to get one's bearings. That's certainly what I had to do here. $\endgroup$
    – Todd Trimble
    Oct 8, 2011 at 13:26
  • 1
    $\begingroup$ @vincenzoml: Have you tried to answer this by your own? $\endgroup$ Oct 8, 2011 at 16:51
  • $\begingroup$ @martin: yes I did. I get easily confused when reasoning on equivalence classes. But the categorical proof would also clarify what specific features of the category Set one has to use, so how general is the fact that the unique arrow in the lemma is mono. $\endgroup$
    – vincenzoml
    Oct 9, 2011 at 8:14

1 Answer 1

15
$\begingroup$

General pushouts, no; pushouts of pairs of epis, yes.

It's very easy to see the answer is no for general pushouts: since a coproduct $A + B$ is the pushout of a pair $A \leftarrow 0 \to B$, and since the squaring functor preserves $0$, the squaring functor would preserve this pushout only if it preserved the coproduct. But we all know that for finite cardinalities, $a^2 + b^2$ is generally not equal to $(a+b)^2$; therefore squaring cannot preserve coproducts.

But in general, we can say that for the category of sets, given a pair of functions

$$A \stackrel{f_1}{\leftarrow} P \stackrel{f_2}{\to} B,$$

the canonical arrow

$$\phi: A^2 +_{P^2} B^2 \to (A +_P B)^2$$

is monic. (Lemma to be proved.) Assuming this, suppose for example that $f_2: P \to B$ is epic. Then the pushout of $f_2$ along $f_1$ is also epic (well-known fact); let $A \to C$ denote this epi (so $C$ is shorthand for $A +_P B$). Then $A^2 \to C^2$ is also epic, and since this obviously factors as

$$A^2 \to A^2 +_{P^2} B^2 \stackrel{\phi}{\to} C^2$$

we see $\phi$ is also epi. But it is monic by the lemma, hence $\phi$ is an isomorphism, as we wanted to show.

To prove the lemma, it helps to have a clear picture of how pushouts are formed in $Set$. The pushout $C$ is the set of equivalence classes on $A + B$ where $x \in A + B$ is deemed equivalent to $x' \in A + B$ iff there is a zig-zag path

$$x = x_0 \stackrel{f_{i_1}}{\leftarrow} p_0 \stackrel{f_{i_2}}{\to} x_1 \leftarrow \ldots x_{n-1} \stackrel{f_{i_{n-1}}}{\leftarrow} p_{n-1} \stackrel{f_{i_n}}{\to} x_n = x'$$

where for each $k$, either $p_k$ belongs to $P$ and the arrows out of $p_k$ alternate between $f_1$ and $f_2$, or we are in a "holding pattern" where $p_k$ belongs to $A$ or $B$ and the two arrows out of $p_k$ are both identities. Now it is not hard to convince yourself that given $(x, y)$ in $A^2$ or $B^2$, and $(x', y')$ in $A^2$ or $B^2$, if there is a zig-zag path from $x$ to $x'$, and a zig-zag path from $y$ to $y'$, then there is a zig-zag path from $(x, y)$ to $(x', y')$ with respect to the pair of maps

$$A \times A \stackrel{f_1 \times f_1}{\leftarrow} P \times P \stackrel{f_2 \times f_2}{\to} B \times B;$$

all we do is pair together zig-zag paths in the separate $x$- and $y$-components. (Note that if the zig-zag to get from $y$ to $y'$ is longer than the zig-zag from $x$ to $x'$, we can always insert a holding pattern in the $x$-component so that the zig-zag in the $y$-component can "catch up", i.e., so that the lengths of the zig-zags match up.) But this means precisely that the map $\phi$ is monic.

Edit: In answer to vincenzoml's questions in the comments, I wrote up a proof of the more general desired result which applies to a general $\infty$-pretopos, here.

$\endgroup$
17
  • $\begingroup$ I have 2 more related questions 1) the argument seems to extend without problems to wide pushouts of epis, can you confirm this? 2) can the lemma be proved categorically (a reference is sufficient)? I am convinced of it but can't really write down a simple proof, reasoning about elements of quotients is difficult. $\endgroup$
    – vincenzoml
    Oct 8, 2011 at 9:35
  • $\begingroup$ And a third question (perhaps I should open a new one, but I may edit this one with the more general answer): it seems obvious to me that the functor FX = X+X preserves coproducts and coequalisers. Other generalisations of the above arguments lead me to state the following: All polynomial functors preserve wide pushouts if at least one of the arrows in the cocone is epic. I ask for a confirmation, but it seems quite easy to prove it. $\endgroup$
    – vincenzoml
    Oct 8, 2011 at 10:39
  • $\begingroup$ I had a feeling you might be asking such questions.:-) I don't have a reference for this; in fact, only the day before yesterday I had to prove that very lemma. @your questions: let me point out that finite power functors $Set \to Set$ do preserve reflexive coequalizers; in particular, the coequalizer of the pair of projections from an equivalence relation on $X$ to $X$. If $F$ is a finitary polynomial endofunctor on $Set$ (or say on a pretopos), then the canonical map $\sum_i F(A_i) \to F(\sum_i A_i)$ is monic, and I think this induces a monic $(\sum_i)_{FP} F(A_i) \to F((\sum_i)_P A_i$... $\endgroup$
    – Todd Trimble
    Oct 8, 2011 at 13:00
  • $\begingroup$ for the corresponding wide pushouts, with the help of the result about reflexive coequalizers. But I'd really like to think about this some more. I think it's a handy lemma to have around, and it should be properly archived at the nLab. So perhaps I could discuss this with colleagues, write it up properly, and then edit with a pointer to an nLab article. Two more remarks: yes, $F(X) = X + X = 2 \times X$ certainly preserves colimits, and modulo the more general lemma stated in these comments, I confirm the isomorphism if one of the arrows is epic (working now in a general pretopos). $\endgroup$
    – Todd Trimble
    Oct 8, 2011 at 13:05
  • 1
    $\begingroup$ Hi @ToddTrimble, I believe it is not sufficient to assume that merely one leg is epic. Consider the inclusion of a nonempty subset $A \subseteq B$, then the pushout of the span $1 \leftarrow A \to B$ is the quotient $B/A = (B \setminus A) + 1$ which collapses $A$ to a point. But in general $(B/A)^2 \not \cong B^2/A^2$ for cardinality reasons. $\endgroup$ Oct 31, 2023 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.