View source for Pushout (category theory)

{{Short description|Most general completion of a commutative square given two morphisms with same domain}}
In [[category theory]], a branch of [[mathematics]], a '''pushout''' (also called a '''fibered coproduct''' or '''fibered sum''' or '''cocartesian square''' or '''amalgamated sum''') is the [[colimit]] of a [[diagram (category theory)|diagram]] consisting of two [[morphism]]s ''f'' : ''Z'' &rarr; ''X'' and ''g'' : ''Z'' &rarr; ''Y'' with a common [[Domain of a function|domain]]. The pushout consists of an [[object (category theory)|object]] ''P'' along with two morphisms ''X'' &rarr; ''P''  and ''Y'' &rarr; ''P'' that complete a [[commutative diagram|commutative square]] with the two given morphisms ''f'' and ''g''. In fact, the defining [[universal property]] of the pushout (given below) essentially says that the pushout is the "most general" way to complete this commutative square. Common notations for the pushout are <math>P = X \sqcup_Z Y</math> and <math>P = X +_Z Y</math>.

The pushout is the [[dual (category theory)|categorical dual]] of the [[pullback (category theory)|pullback]].

==Universal property==
Explicitly, the pushout of the morphisms ''f'' and ''g'' consists of an object ''P'' and two morphisms ''i''<sub>1</sub> : ''X'' &rarr; ''P'' and ''i''<sub>2</sub> : ''Y'' &rarr; ''P'' such that the diagram

:[[Image:Categorical pushout.svg|125px|class=skin-invert]]

[[commutative diagram|commutes]] and such that (''P'', ''i''<sub>1</sub>, ''i''<sub>2</sub>) is [[universal property|universal]] with respect to this diagram. That is, for any other such triple (''Q'', ''j''<sub>1</sub>, ''j''<sub>2</sub>) for which the following diagram commutes, there must exist a unique ''u'' : ''P'' &rarr; ''Q'' also making the diagram commute:

:[[Image:Categorical pushout (expanded).svg|225px|class=skin-invert]]

As with all universal constructions, the pushout, if it exists, is unique up to a unique [[isomorphism]].

==Examples of pushouts==
Here are some examples of pushouts in familiar [[category (mathematics)|categories]]. Note that in each case, we are only providing a construction of an object in the isomorphism class of pushouts; as mentioned above, though there may be other ways to construct it, they are all equivalent.

*Suppose that ''X'', ''Y'', and ''Z'' as above are [[set (mathematics)|sets]], and that ''f''&nbsp;:&nbsp;''Z''&nbsp;&rarr;&nbsp;''X'' and ''g''&nbsp;:&nbsp;''Z''&nbsp;&rarr;&nbsp;''Y'' are set functions. The pushout of ''f'' and ''g'' is the [[disjoint union]] of ''X'' and ''Y'', where elements sharing a common [[preimage]] (in ''Z'') are identified, together with the morphisms ''i''<sub>1</sub>, ''i''<sub>2</sub>  from ''X'' and ''Y'', i.e. <math>P = (X \sqcup Y)/\!\sim</math> where ''~'' is the [[Equivalence_relation#Comparing_equivalence_relations|finest equivalence relation]] {{xref|(See also [[Closure_(mathematics)#Binary_relations|Binary relation closures]])}} such that ''f''(''z'')&nbsp;~&nbsp;''g''(''z'') for all ''z'' in ''Z''. In particular, if ''X'' and ''Y'' are [[subset]]s of some larger set ''W'' and ''Z'' is their [[intersection (set theory)|intersection]], with ''f'' and ''g'' the inclusion maps of ''Z'' into ''X'' and ''Y'', then the pushout can be canonically identified with the [[union (set theory)|union]] <math> X \cup Y \subseteq W</math>.
**A specific case of this is the cograph of a function.  If <math>f \colon X \to Y</math> is a function, then the '''cograph''' of a function is the pushout of {{mvar|f}} along the identity function of {{mvar|X}}. In elementary terms, the cograph is the quotient of <math>X \sqcup Y</math> by the equivalence relation generated by identifying <math>x \in X \subseteq X \sqcup Y</math> with <math>f(x) \in Y \subseteq X \sqcup Y</math>. A function may be recovered by its cograph because each equivalence class in <math>X \sqcup Y</math> contains precisely one element of {{mvar|Y}}. Cographs are dual to graphs of functions since the graph may be defined as the pullback of {{mvar|f}} along the identity of {{mvar|Y}}.<ref>Riehl, ''Category Theory in Context'', p. xii</ref><ref>{{cite web | url=https://math.stackexchange.com/questions/1350657/does-the-concept-of-cograph-of-a-function-have-natural-generalisations-exten | title=Does the concept of "cograph of a function" have natural generalisations / Extensions? }}</ref>
*The construction of [[adjunction space]]s is an example of pushouts in the [[category of topological spaces]]. More precisely, if ''Z'' is a [[subspace topology|subspace]] of ''Y'' and ''g'' : ''Z'' &rarr; ''Y'' is the [[inclusion map]] we can "glue" ''Y'' to another space ''X'' along ''Z'' using an "attaching map" ''f'' : ''Z'' &rarr; ''X''. The result is the adjunction space <math>X \cup_{f} Y</math>, which is just the pushout of ''f'' and ''g''.  More generally, all identification spaces may be regarded as pushouts in this way.
*A special case of the above is the [[wedge sum]] or one-point union; here we take ''X'' and ''Y'' to be [[pointed space]]s and ''Z'' the one-point space. Then the pushout is <math>X \vee Y</math>, the space obtained by gluing the basepoint of ''X'' to the basepoint of ''Y''.
*In the [[category of abelian groups]], pushouts can be thought of as "[[direct sum of abelian groups|direct sum]] with gluing" in the same way we think of adjunction spaces as "[[disjoint union topology|disjoint union]] with gluing". The [[zero group]] is a [[subgroup]] of every [[group (mathematics)|group]], so for any [[abelian group]]s ''A'' and ''B'', we have [[homomorphism]]s <math>f : 0 \to A</math> and <math>g : 0 \to B</math>. The pushout of these maps is the direct sum of ''A'' and ''B''. Generalizing to the case where ''f'' and ''g'' are arbitrary homomorphisms from a common domain ''Z'', one obtains for the pushout a [[quotient group]] of the direct sum; namely, we [[Modulo (jargon)|mod out]] by the subgroup consisting of pairs (''f''(''z''),&nbsp;−''g''(''z'')). Thus we have "glued" along the images of ''Z'' under ''f'' and ''g''. A similar approach yields the pushout in the [[category of modules|category of ''R''-modules]] for any [[Ring (mathematics)|ring]] ''R''.
*In the [[category of groups]], the pushout is called the [[free product with amalgamation]]. It shows up in the [[Seifert–van Kampen theorem]] of [[algebraic topology]] (see below).
*In '''CRing''', the category of [[commutative rings]] (a [[full subcategory]] of the [[category of rings]]), the pushout is given by the [[tensor product]] of rings <math>A \otimes_{C} B</math> with the morphisms <math>g': A \rightarrow A \otimes_{C} B</math> and <math>f': B \rightarrow A \otimes_{C} B</math> that satisfy <math> f' \circ g = g' \circ f </math>. In fact, since the pushout is the [[colimit]] of a [[Span (category theory)|span]] and the [[Pullback (category theory)|pullback]] is the limit of a [[Span (category theory)|cospan]], we can think of the tensor product of rings and the [[Pullback (category theory)|fibered product of rings]] (see the examples section) as dual notions to each other. In particular, let ''A'', ''B'', and ''C'' be objects (commutative rings with identity) in '''CRing''' and let ''f'' : ''C'' &rarr; ''A'' and ''g'' : ''C'' &rarr; ''B'' be morphisms ([[ring homomorphism]]s) in '''CRing'''. Then the tensor product is:
::<math>A \otimes_{C} B = \left\{\sum_{i \in I} (a_i,b_i) \; \big| \; a_i \in A, b_i \in B \right\} \Bigg/ \bigg\langle (f(c)a,b) - (a,g(c)b) \; \big| \; a \in A, b \in B, c \in C \bigg\rangle </math>
*See [[Free product of associative algebras]] for the case of non-commutative rings.
*In the multiplicative [[monoid]] of positive [[integer]]s <math>\mathbf{Z}_+</math>, considered as a category with one object, the pushout of two positive integers ''m'' and ''n'' is just the pair <math>\left(\frac{\operatorname{lcm}(m,n)}{m}, \frac{\operatorname{lcm}(m,n)}{n}\right)</math>, where the numerators are both the [[least common multiple]] of ''m'' and ''n''. Note that the same pair is also the pullback.

==Properties==
*Whenever the pushout ''A''&thinsp;⊔<sub>''C''</sub> ''B'' exists, then ''B''&thinsp;⊔<sub>''C''</sub> ''A'' exists as well and there is a natural isomorphism ''A''&thinsp;⊔<sub>''C''</sub> ''B'' &cong; ''B''&thinsp;⊔<sub>''C''</sub> ''A''.
*In an [[abelian category]] all pushouts exist, and they preserve [[cokernel]]s in the following sense: if (''P'', ''i''<sub>1</sub>, ''i''<sub>2</sub>) is the pushout of ''f'' : ''Z'' &rarr; ''X'' and ''g'' : ''Z'' &rarr; ''Y'', then the natural map coker(''f'') &rarr; coker(''i''<sub>2</sub>) is an isomorphism, and so is the natural map coker(''g'') &rarr; coker(''i''<sub>1</sub>).
*There is a natural isomorphism (''A'' ⊔<sub>''C''</sub> ''B'')&thinsp;⊔<sub>''B''</sub> ''D'' &cong; ''A'' ⊔<sub>''C''</sub> ''D''. Explicitly, this means: 
** if maps ''f'' : ''C'' &rarr; ''A'', ''g'' : ''C'' &rarr; ''B'' and ''h'' : ''B'' &rarr; ''D'' are given and 
** the pushout of ''f'' and ''g'' is given by ''i'' : ''A'' &rarr; ''P'' and ''j'' : ''B'' &rarr; ''P'', and
** the pushout of ''j'' and ''h'' is given by  ''k'' : ''P'' &rarr; ''Q'' and ''l'' : ''D'' &rarr; ''Q'', 
** then the pushout of ''f'' and ''hg'' is given by ''ki'' : ''A'' &rarr; ''Q'' and  ''l'' : ''D'' &rarr; ''Q''. 
:Graphically this means that two pushout squares, placed side by side and sharing one morphism, form a larger pushout square when ignoring the inner shared morphism.

== Construction via coproducts and coequalizers ==
Pushouts are equivalent to [[coproduct|coproducts]] and [[coequalizer|coequalizers]] (if there is an [[initial object]]) in the sense that:
* Coproducts are a pushout from the initial object, and the coequalizer of ''f'', ''g'' : ''X'' &rarr; ''Y'' is the pushout of [''f'', ''g''] and [1<sub>''X''</sub>,&thinsp;1<sub>''X''</sub>], so if there are pushouts (and an initial object), then there are coequalizers and coproducts;
* Pushouts can be constructed from coproducts and coequalizers, as described below (the pushout is the coequalizer of the maps to the coproduct).

All of the above examples may be regarded as special cases of the following very general construction, which works in any category ''C'' satisfying:
* For any objects ''A'' and ''B'' of ''C'', their coproduct exists in ''C'';
* For any morphisms ''j'' and ''k'' of ''C'' with the same domain and the same target, the coequalizer of ''j'' and ''k'' exists in ''C''.

In this setup, we obtain the pushout of morphisms ''f'' : ''Z'' &rarr; ''X'' and ''g'' : ''Z'' &rarr; ''Y'' by first forming the coproduct of the targets ''X'' and ''Y''. We then have two morphisms from ''Z'' to this coproduct. We can either go from ''Z'' to ''X'' via ''f'', then include into the coproduct, or we can go from ''Z'' to ''Y'' via ''g'', then include into the coproduct. The pushout of ''f'' and ''g'' is the coequalizer of these new maps.

==Application: the Seifert–van Kampen theorem==
{{Main|Seifert-van Kampen theorem}}
The Seifert–van Kampen theorem answers the following question. Suppose we have a [[Connected_space#Path_connectedness|path-connected]] space <math>X</math>, covered by path-connected open subspaces <math>A</math> and <math>B</math> whose intersection <math>A \cap B</math> is also path-connected. (Assume also that the basepoint <math>\ast</math> lies in the intersection of ''A'' and ''B''.) If we know the [[fundamental group]]s of <math>A</math>, <math>B</math> and <math>A\cap B</math> can we recover the fundamental group of <math>X</math>? The answer is yes, provided we also know the induced homomorphisms
<math>\pi_1(A \cap B,*) \to \pi_1(A,*)</math>
and
<math>\pi_1(A \cap B,*) \to \pi_1(B,*).</math>
The theorem then says that the fundamental group of <math>X</math> is the pushout of these two induced maps. Of course, <math>X</math> is the pushout of the two inclusion maps of <math>A \cap B</math> into <math>A</math> and <math>B</math>. Thus we may interpret the theorem as confirming that the fundamental group functor preserves pushouts of inclusions. We might expect this to be simplest when <math>A \cap B</math> is [[simply connected]], since then both homomorphisms above have trivial domain. Indeed, this is the case, since then the pushout (of groups) reduces to the [[free product]], which is the coproduct in the category of groups. In a most general case we will be speaking of a [[free product with amalgamation]].

There is a detailed exposition of this, in a slightly more general setting ([[covering space|covering]] [[groupoid]]s) in the book by J. P. May listed in the references.

==References==
*[[J.P. May|May, J. P.]] ''A concise course in algebraic topology.'' University of Chicago Press, 1999.
*:An introduction to categorical approaches to algebraic topology: the focus is on the algebra, and assumes a topological background.

* [[Ronald Brown (mathematician)| Ronald Brown]] [http://groupoids.org.uk/topgpds.html  "Topology and Groupoids"]  pdf available Gives an account of some categorical methods in topology, use the fundamental groupoid on a set of base points to give a generalisation of the Seifert-van Kampen Theorem.

* Philip J. Higgins, [http://www.tac.mta.ca/tac/reprints/articles/7/tr7abs.html "Categories and Groupoids"  free download] Explains some uses of groupoids in group theory and topology.

==References==
{{Reflist}}

== External links ==
*[http://ncatlab.org/nlab/show/pushout pushout in nLab ]

{{Category theory}}

[[Category:Limits (category theory)]]