I am beginning to study category theory, and I think I need your help to find my way in this sea of uncertainty (!).
I have the following problem (n. $5.11$ from Aluffi's Algebra: Chapter $0$). Let $A$ and $B$ be two sets, each endowed with an equivalence relation $\sim_A$ resp. $\sim_B$. Define a relation $\sim$ on $A\times B$ by setting $(a_1,b_1)\sim(a_2,b_2)$ iff $a_1\sim_A a_2$ and $b_1\sim_B b_2$.
The question is: prove that $(A\times B)/\!\sim\ \cong\ (A/\!\sim_A)\times(B/\!\sim_B)$.
Here is what I've done:
Let $\pi: A\times B\ \longrightarrow\ (A\times B)/\!\sim$ be the canonical projection, i.e. $\pi(a,b)=[a,b]_\sim$.
Let $\mathbf{Set}^{A\times B}$ -or, if you prefer, $(A\times B\downarrow\mathbf{Set})$- be a coslice category over $\mathbf{Set}$.
The pair $(\pi,(A\times B)/\!\sim)$ is an initial object in the coslice category so given an object $(f,Z)$ we have an unique morphism $\sigma\in \text{Hom}((\pi,(A\times B)/\!\sim),(f,Z))$ such that $f=\sigma\circ\pi$.
If we consider the objects $(\pi_A,A)$ and $(\pi_B,B)$ where $\pi_A$ and $\pi_B$ are the canonical projections to the quotients $A/\!\sim_A$ and $B/\!\sim_B$, this means that there are two unique morphisms $\sigma_A$ and $\sigma_B$ such that $\pi_A=\sigma_A\circ\pi$ and $\pi_B=\sigma_B\circ\pi$.
Consider now the slice category $\mathbf{Set}_{\frac{A}{\sim_A},\frac{B}{\sim_B}}$ -or, if you prefer, $(\mathbf{Set}\downarrow\frac{A}{\sim_A},\frac{B}{\sim_B})$.
Let $p_A:(A/\!\sim_A)\times (B/\!\sim_B)\ \longrightarrow\ A/\!\sim_A$ be the canonical projection from the product to $A/\!\sim_A$, and $p_B$ the projection on $B/\!\sim_B$.
Since $\mathbf{Set}$ has products, we know that the object $(p_A,p_B,(A/\!\sim_A)\times (B/\!\sim_B))$ is final in this slice category.
Now, the problem is showing that also $(\sigma_A, \sigma_B,(A\times B)/\!\sim)$ is final: if I do that the exercise is done because final objects are isomorphic.
Let's take an object $(f,g,Z)$. I want to show that there exists a unique morphism \begin{equation} \omega\in\text{Hom}((f,g,Z),(\sigma_A,\sigma_B,(A\times B)/\!\sim)) \end{equation} such that $f=\sigma_A\circ\omega$ and also $g=\sigma_B\circ\omega$.
Given $z\in Z$, I have $f(z)=[a]_{\sim_A}$ and $f(z)=[b]_{\sim_B}$ for some $a\in A$ and $b\in B$. I could define $\omega(z):=[a,b]_{\sim}$ by choosing two representatives of $[a]_{\sim_A}$ and $[b]_{\sim_B}$ respectively (Zorn lemma creeps in here???) and this would do the job, but I don't know how to prove the uniqueness of this definition. Any help is greatly appreciated!
Recall the universal properties of products and quotients. Using these, it is easy to see that there is a unique morphism $(A \times B)/{\sim} \to A/{\sim} \times B/{\sim}$ such that $$\begin{array}{c} A \times B & = & A \times B \\ \downarrow && \downarrow \\ (A \times B)/{\sim} & \rightarrow & A/{\sim} \times B/{\sim} \end{array}$$ commutes. But I claim that there is no purely formal (in the sense that it holds in any category) proof that this morphism is an isomorphism. In fact, even in the category of topological spaces, it fails (the well-known example is $A=\mathbb{R}$ with the relation which collapses $\mathbb{Z}$ to the point, and $B=\mathbb{Q}$ with the trivial/smallest equivalence relation). So in any proof, you will really have to use what the category of sets really is and you will have to use elements somewhere or some additional structure. The element proof is one line long. If you want to use some additional structure, use that the category of sets is cartesian closed. This implies that the functor $A \times -$ preserves colimits (this is what fails for topological spaces, unless $A$ is locally compact for example). Applying this twice, we see that the morphism above is an isomorphism.
If you prove that $A/{\sim} \times B/{\sim}$ satisfies the defining universal property of $(A \times B)/{\sim}$, or vice versa that $(A \times B)/{\sim}$ satisfies the universal property of $A/{\sim} \times B/{\sim}$ (which seems to be your idea), you will need elements anyway and this will be rather long as compared to the direct proof that our map is an isomorphism. Let me show you this: There are two canonical maps $(A \times B)/{\sim} \to A/{\sim}$ and $(A \times B)/{\sim} \to B/{\sim}$. We want to show that these satisfies the universal property of a product. Thus, given a set $Z$ and two maps $Z \to A/{\sim}$ and $Z \to B/{\sim}$, we want to construct a map $Z \to (A \times B)/{\sim}$. If we start with an element in $Z$, we get an element in $A/{\sim}$ and in $B/{\sim}$. Since $A \to A/{\sim}$ and $B \to B/{\sim}$ are surjective, we may choose lifts to elements in $A$ and $B$. This produces an element in $A \times B$. (Here, we don't need any Zorn's Lemma, unless we want to choose a function $Z \to A \times B$ which does the choice for us, but we don't need this, in fact we just fix some element of $Z$). We consider its image in $(A \times B)/{\sim}$. We claim that this is well-defined. So assume that we choose another lift in $A$ resp. in $B$. This will give us an element in $A \times B$ which is equivalent to the former one (by construction of ${\sim}$ on $A \times B$), so that their images in $(A \times B)/{\sim}$ become equal. This way, we have constructed a map $Z \to (A \times B)/{\sim}$. Also, by construction we get back $Z \to A/{\sim}$ and $Z \to B/{\sim}$ when we compose with the canonical maps. So let us prove uniqueness. This really comes down to the injectivity of the canonical map $(A \times B)/{\sim} \to A/{\sim} \times B/{\sim}$. If we have two elements in $(A \times B)/{\sim}$ with the same image, we lift them to two elements in $A \times B$ with the same image. Then we get two elements in $A$ with the same image in $A/{\sim}$ and likewise with $B$. But then this means (by construction of ${\sim}$ on $A \times B$) that the two elements of $A \times B$ are equivalent and therefore become equal in $(A \times B)/{\sim}$.
As you see, this proof is terribly long as compared to the direct proof that $(A \times B)/{\sim} \to A/{\sim} \times B/{\sim}$ is bijective.