0
$\begingroup$

Does anyone know of an algorithm for computing pushouts in $\sf FinSet$, the category of finite sets and mappings?

That is, given finite sets $X$, $Y$ and $Z$ with maps (of sets) $f: X \to Z$ and $g: X \to Y$, is there an algorithm for computing the object $C$ and the maps from $Z$ to $C$ and $Y$ to $C$ which together form the pushout of the original diagram?

$\endgroup$
  • $\begingroup$ Two issues: 1) Which environment category are you considering (sets with total functions, finite sets with total functions, etc)? 2) If you know how to calculate coproducts and coequalizers then there is a well known method explaining how to calculate pushouts (and indeed all colimits); a good summary of the method is given in mathoverflow.net/questions/171920/… $\endgroup$ – boumol Sep 5 '15 at 8:16
  • $\begingroup$ HSN: Yes! The question should be fixed now. $\endgroup$ – bump2pass Sep 8 '15 at 15:27
  • $\begingroup$ Boumol: I mean the category Finite Set, where an object is a finite set and a map is a map of sets. I will read through that construction you sited. $\endgroup$ – bump2pass Sep 8 '15 at 15:31
  • 1
    $\begingroup$ If you want to notify someone of your comment, you need to use the '@' sign, cf. here. Anyway, you still haven't explained what you mean by "compute"; surely you don't just want the description $Z \cup_X Y = (Z \sqcup Y) / (f(x) \sim g(x))$? $\endgroup$ – Najib Idrissi Sep 8 '15 at 15:48
  • $\begingroup$ @NajibIdrissi Thanks for asking what do I mean by compute. If I asked for a computation for say, the sum (in Finite Set) of two objects, the description alone is good enough. But in the case of pushouts, I think the description is not the entire story. I think the answer is in boumol's comment: the proof is constructive and can be used to generate an algorithm. What I was hoping for was a very specific discussion of an algorithm for pushouts. A good example which I think indicates why one would want an algorithm to compute pushouts is Exercise 2.6.2.4 from arxiv.org/abs/1302.6946 $\endgroup$ – bump2pass Sep 8 '15 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.