Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
3  
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). –  Spice the Bird Oct 8 '11 at 0:16
    
@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. –  Todd Trimble Oct 8 '11 at 13:26
1  
@vincenzoml: Have you tried to answer this by your own? –  Martin Brandenburg Oct 8 '11 at 16:51
    
@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. –  vincenzoml Oct 9 '11 at 8:14

1 Answer 1

up vote 13 down vote accepted

General pushouts, no; pushouts of pairs of epis, yes. In fact, yes to pushouts of pairs where only one of the arrows of the pair is epi.

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.

share|improve this answer
    
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. –  vincenzoml Oct 8 '11 at 9:35
    
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. –  vincenzoml Oct 8 '11 at 10:39
    
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$... –  Todd Trimble Oct 8 '11 at 13:00
    
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). –  Todd Trimble Oct 8 '11 at 13:05
    
(Hm, need to modify the assertion of monicity of $\sum_i F(A_i) \to F(\sum_i A_i)$, to avoid the case where the polynomial endofunctor $F$ has a constant term.) –  Todd Trimble Oct 8 '11 at 13:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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