# Pushout in the category of Sets: proof

Let $$f\colon Z\to X$$ and $$g\colon Z\to Y$$ be functions. What is a pushout of $$f$$ and $$g$$ in $$\mathsf{Set}$$? Different sources and questions on this site claim that it's the quotient of the disjoint union $$X\sqcup Y$$ by the equivalence relation $$\sim_R$$ generated by the relation $$R = \{ ((0,x),(1,y)) \in (X\sqcup Y)\times (X\sqcup Y) \mid \exists z \in Z, x = f(z)$$ and $$y = g(z) \}$$.

Define functions $$i_1\colon X\to X\sqcup Y/{\sim_R}$$ and $$i_2\colon Y\to X\sqcup Y/{\sim_R}$$ by setting $$i_1$$ to map each $$x \in X$$ to the equivalence class $$[(0,x)]$$ and $$i_2$$ to map each $$y \in Y$$ to the equivalence class $$[(1,y)]$$.

For $$X\sqcup Y/{\sim_R}$$ together with $$i_1$$ and $$i_2$$ to be a pushout in $$\mathsf{Set}$$, we first must have $$i_2\circ f = i_2\circ g$$. It's easy to check that it's so.

Now, let $$j_1\colon X\to Q$$ and $$j_2\colon Y\to Q$$ be functions so that $$j_1\circ f = j_2\circ g$$. We seek a function $$u\colon X\sqcup Y/{\sim_R} \to Q$$. $$u\circ i_1 = j_1$$ and $$u\circ i_2 = j_2$$. Of course, for these identities to hold, this hypothetical function $$u$$ must satisfy $$u([(0,x)]) = j_1(x)$$ and $$u([(1,y)]) = j_2(y)$$ for any $$x \in X$$ and $$y \in Y$$. But I'm not sure how to prove that this data indeed defines a function. We need to prove that it is independent of the choice of $$x$$ and $$y$$. Of course, this needs to use the fact that $$j_1\circ f = j_2\circ g$$.

It is clear that $$u$$ thus defined is really a function on all of the quotient space, because the quotient map is surjective. Whenever you define anything on a quotient by means of representatives, you check that it is well defined by considering different representatives.

If I denote by $$\pi$$ the quotient map, we want to show that if $$\pi((0,x)) = \pi((1,y))$$, then $$u(\pi((0,x))$$ = $$u(\pi((1,y))$$. The condition implies that there is a (possibly non-unique) $$z \in Z$$ with $$f(z) = x$$ and $$g(z) = y$$. Applying $$j_1$$ to the first and $$j_2$$ to the second equality yields $$j_1 (x) = j_2(y)$$ by the condition. But that implies precisely $$u(\pi((0,x))$$ = $$u(\pi((1,y))$$. Hence, $$u$$ is well defined. Can you explain why $$u$$ is also unique?

As a continuation, you may want to consider the following: this diagrammatic property of the pushout characterizes the pushout. If any other set $$P$$ has the pushout property, then there is a canonical bijection between the 'abstract' pushout you defined and the new pushout $$P$$. The proof of course uses the property of the pushout.

$$\textbf{Lemma}$$: If $$R$$ is a relation then the equivalence relation generated by $$R$$ denoted by $$Q$$ is given by the property

$$xQy \Leftrightarrow x=y\,\,\,\text{or if there is a chain}\,\,\, (a_1,\dots,a_{n+1})\,\,\, \text{satisfying}\,\,\, x=a_1,y=a_{n+1}\,\,\, \text{and for}\,\,\, 1\leq k \leq n\,\,\, (a_k,a_{k+1}) \in R\,\,\,\text{or}\,\,\,(a_{k+1},a_k) \in R$$

To prove that $$u$$ is well defined we need to prove three steps:

$$\textbf{1)}$$ If $$[(0,x_1)]=[(0,x_2)]$$ then $$j_1(x_1)=j_1(x_2)$$

$$\textbf{2)}$$ If $$[(1,y_1)]=[(1,y_2)]$$ then $$j_2(y_1)=j_2(y_2)$$

$$\textbf{3)}$$ If $$[(1,y)]=[(0,x)]$$ then $$j_1(x)=j_2(y)$$

I will prove only the third item, the other two follow by a analogue argument

$$\textbf{Proof:}$$ We will prove the claim by strong induction in the lenght of the chain that make $$(0,x)Q(1,y)$$.

$$\textbf{Base:}$$ If the chain have only two elements $$(a,b)$$ we have that $$(a,b)(\text{or} (b,a)) \in R$$ and that means that there exists an element $$z \in Z$$ such that $$f(z)=x$$ and $$g(z)=y$$, and by the fact that $$j_1 \circ f=j_2 \circ g$$ it follows that $$j_1(x)=j_2(y)$$, which is the desired conclusion.

$$\textbf{Induction Hypotesis:}$$ Suppose that if $$(0,x)Q(1,y)$$ by a chain of lenght $$n$$ or less then $$j_1(x) = j_2(y).$$

$$\textbf{Induction Step:}$$ If $$(0,x)Q(1,y)$$ by a chain $$(a_1,\dots{},a_{n+1})$$ we have that the subchain $$(a_1,\dots,a_{n-1})$$ satisfy the induction hypotesis and then denoting $$a_{n-1}$$ by $$(a_{n-1}',1)$$ we can conclude that $$j_1(x) = j_2(a_{n-1}')$$. Knowing that $$(a_{n-1},a_n) (\text{or} (a_n,a_{n-1})) \in R$$ we can find $$z \in Z$$ such that $$f(z)=a_n'$$ and $$g(z)=a_{n-1}'$$ which imply $$j_1(a_n')=j_2(a_{n-1}')$$. But by the same argument just described (now applied in the pair $$(a_{n+1},a_n)$$) we can conclude that $$j_2(y) = j_1(a_n')$$ and finally

$$j_2(y) = j_1(a_n')=j_2(a_{n-1}')=j_1(x)$$

• Sorry for the off-topic but I just wanted to let you know that I agree that the downvotes of your answer here (which I can see even though it is deleted due to the StackExchange user rights system) were not justified :) (somehow, the whole thread there was too hostile for no reason that I can see anyway). Jul 14, 2021 at 14:51
• I really like this site, and I'm ready to change my answer to make it better and acessible to people. But they refused to give me this oportunity. Thank you for the support. :) Jul 14, 2021 at 15:39
• On that note, some time ago, I also got downvoted and I am not sure why that is. But I wouldn't recommend taking downvotes (or votes in general) too seriously 🙂. Jul 14, 2021 at 15:41
• Sorry for the misunderstanding but I am not quite sure what you mean by "give up" and what reddit-post you are referring to 😅. Jul 14, 2021 at 15:45
• Ahh ok, yeah I wouldn't worry too much about things like that :) Jul 14, 2021 at 15:58