Pushout in the category of Sets: proof

Question

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$.

Answer 1

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.

Answer 2

$\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)$$