The following question, is taken from Arbib and Manes’ Arrows, structures and functors text:
Definition 1: Given an equivalence relation $E$ on a set $A$, we define the equivalence class of an element $a$ of $A$ with respect to $E$ to be $$ [a]_E = \{a' \mid \text{$a'\in A$ and $(a,a')\in E$}\} $$ (when no ambiguity can arise, we write $[a]$ for $[a]_E$.) The factor set or quotient set of $A$ with respect to $E$ is then the set of equivalence classes $$ A/E = \{[a] \mid a \in A\} \,. $$
Definition 2: Given any function $f \colon A \rightarrow B$, we define the equivalence relation $E(f)$ of $f$ on $A$ by $$ E(f) = \{ (a,a') \in A \times A \mid f(a) = f(a') \}. $$
[…]
Given any relation $R$ on $A$ (i.e., any subset of $A \times A$) we may associate with it the two projection maps $$ p_k \colon R \rightarrow A \,, \quad (a_1, a_2) \mapsto a_k \,, \quad k = 1, 2 \,. $$ On the other hand, given any pair of maps $$ p_1, p_2 \colon R \rightarrow A $$ with common domain, and with codomain $A$, we may define on $A$ the corresponding relation $$ E_R = \{ (p_1(r), p_2(r)) \mid r \in R\} \subset A \times A \tag{$1$} $$ (where we forbear writing $E_{(R, p_1, p_2)}$ for brevity).
Exercise: Given relations $p_1, p_2 \colon R \rightarrow A$, $q_1, q_2 \colon S \rightarrow A$, say that $(p_1, p_2) \sim (q_1, q_2)$ if there exist functions (not necessarily isomorphisms!) as shown below:
Show that $\sim$ is an equivalence relation. Show that $[R,p,q] \mapsto E_R$ is a well defined bijection from the set of $\sim$-equivalence classes of relations to the set of subsets of $A \times A$.
Let $x_1$ be the map that sends $R$ to $S$ and $x_2$ be the map that sends $S$ to $R$. From the above commutative diagram, we also define another exact lookin diagrams but with one pair of mappings renamed to $z_1$ and $z_2$ along with defining the following mapping/identities:
- $p_1=q_1\circ x_1, \quad (1)$
- $p_2=q_2\circ x_1$,
- $q_1=p_1\circ x_2, \quad (2)$
- $q_2=p_2\circ x_2,$
- $q_1=z_1\circ x_3, \quad (3)$
- $q_2=z_2\circ x_3,$
- $z_1=q_1\circ x_4, \quad (4)$
- $z_2=q_2\circ x_4.$
To show that $\sim$ is reflexive, applying $(1)$ to itself twice, we get $p_1 = p_1 \circ x_1 \circ x_2$ and $p_2 = p_2 \circ x_1 \circ x_2$, hence $(p_1, p_2) \sim (p_1, p_2)$.
For symmetry, from $(1)$ and $(2)$, we have $(p_1, p_2) \sim (q_1, q_2)$ and $(q_1, q_2) \sim (p_1, p_2)$, so we get symmetry.
For transitivity from $(1)$ and $(3)$, $(p_1, p_2) \sim (q_1, q_2)$, and $(q_1, q_2) \sim (z_1, z_2)$. Then plugging $(3)$ into $(1)$, we get $p_1 = z_1 \circ x_3 \circ x_1$ and $p_2 = z_2 \circ x_3 \circ x_1$, hence $(p_1, p_2) \sim (z_1, z_2)$.
For showing that the function $[R, p, q] \mapsto E_R$ is well-defined and bijective, can someone tell me what the notations $[R, p, q]$ means? I know there is a misprint there. The notations should read as $[R_i, p_j, p_j]$ and $E_{R_i}$ for $i, j = 1, 2$.
Thank you in advance.