Fork me on GitHub
Math for the people, by the people.

User login

relation on objects

\documentclass{article}
\usepackage{amssymb,amscd}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{mathrsfs}

% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
\usepackage{amsthm}
% making logically defined graphics
%%\usepackage{xypic}
\usepackage{pst-plot}

% define commands here
\newcommand*{\abs}[1]{\left\lvert #1\right\rvert}
\newtheorem{prop}{Proposition}
\newtheorem{thm}{Theorem}
\newtheorem{ex}{Example}
\newcommand{\real}{\mathbb{R}}
\newcommand{\pdiff}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\mpdiff}[3]{\frac{\partial^#1 #2}{\partial #3^#1}}
\begin{document}
In category theory, there are at least two inequivalent ways to define ``relations'' between objects of a category.  Both definitions are direct generalizations of ordinary relations between sets.  In this entry, we fix a category $\mathcal{C}$, and only look at binary relations, as relations of higher arity can be easily formulated.

\subsection*{Definition 1}
The first definition is the generalization of the fact that a relation between sets $A, B$ is just a subset $R$ of the cartesian product $A\times B$.

\textbf{Definition}.  Let $A,B$ be objects in $\mathcal{C}$.  A \emph{relation} from $A$ to $B$ is a subobject $R$ of the categorical direct product $A \times B$.  We often write $R\subseteq A\times B$ to denote that $R$ is a relation from $A$ to $B$.

One potential drawback with this definition is that $R$ itself is not an object in $\mathcal{C}$, as $R$ is an equivalence class of monomorphisms into $A\times B$.  Another, possibly bigger, drawback is that a relation is only defined if the product of $A\times B$ exists.

For example, in \textbf{Set}, the category of sets, a relation between sets $A$ and $B$ is an equivalence class $[S]$ of a subset $S\subseteq A\times B$.  In other words, take a subset $S$ of $A\times B$ and form the class of all sets (in \textbf{Sets}) equipollent to $S$.


\subsection*{Definition 2}

The second definition looks at the functional properties of a binary relation between sets $A$ and $B$.  If $R$ is a relation from sets $A$ to $B$, it is a subset of $A\times B$.  Therefore, it has two projections $p_1\!:\!R\to A$ and $p_2\!:\!R\to B$, projecting $R$ onto the its first and second components respectively.  Furthermore, $p_1$ and $p_2$ has the properties that they form a monomorphic pair.

\textbf{Definition}.  Let $A,B$ be objects in $\mathcal{C}$.  A \emph{relation object} from $A$ to $B$ is an object $R$ and an ordered pair of morphisms $(p_1\!:\!R\to A,p_2\!:\!R\to B)$, such that $p_1,p_2$ form a monomorphic pair.  When $A=B$, we call $R$ a relation object on $A$.

One clear advantage of this definition is that there is no need to introduce the notion of products (on objects) in this definition.  Another big advantage with this definition is that one gets an associated a set-theorectic relation with each relation object:
\begin{quote}
For every relation object $R$ on $A$ and every object $C$, set $$R_C:=\lbrace (p_1\circ f, p_2\circ f) \mid f \in \hom(C,R)\rbrace.$$
\end{quote}
Then $R_C$ is a set relation from $\hom(C,A)$ to $\hom(C,B)$.

Suppose now that $R$ is a relation object on $A$.  Then $R_C$ is a set relation on $\hom(C,A)$.  $R$ is said to be a \emph{reflexive relation object, symmetric relation object, transitive relation object}, or an \emph{equivalence relation object} on $A$ iff the induced relation $R_C$ is reflexive, symmetric, transitive, or equivalence on $\hom(C,A)$ for every object $C$.

For example, a relation object $R$ on an object $A$ in \textbf{Set} is just the oridinary binary relation on the set $A$.  We also have the following: $R$ is reflexive (symmetric, transitive, or equivalence) relation object iff $R$ is reflexive (symmetric, transitive, or equivalence) relation.
\begin{proof}  There are three parts to this proof:
\begin{enumerate}
\item (reflexivity).  $(\Rightarrow)$.  Suppose first that $R$ is a reflexive relation object on $A$.  Let $C$ be the diagonal relation on $A$, and $f:C\to A$ a function given by $f(a,a)=a$.  Since $R_C$ is a reflexive relation on set $\hom(C,A)$, there is a function $g:C\to R$ such that $p_1\circ g= f = p_2 \circ g$.  As $g$ can be written as $(g_1,g_2)$, with each $g_i=p_i\circ g$, we get $g=(f,f)$.  This shows that $(a,a) = (f(a,a),f(a,a)) = g(a,a) \in R$ for all $a\in A$.  Therefore, $R$ is a reflexive relation on $A$.

$(\Leftarrow)$.  Suppose now that $R$ is a reflexive relation on set $A$.  Let $C$ be an arbitrary set and $f:C\to A$ and arbitrary function from $C$ to $A$.  We get a function $f':C\to A\times A$ by setting $f'(c)=(f(c),f(c))$.  Since $R$ is reflexive, $f'$ maps $C$ into $R$.  But $(f,f) = (p_1\circ f', p_2\circ f')\in R_C$, we have that $R_C$ is reflexive.  Since $C$ is arbitrary, $R$ is a reflexive relation object on $A$.
\item (symmetry).  $(\Rightarrow)$.  Suppose $R$ is a symmetric relation object on $A$, and suppose $(a,b)\in R$, where $a,b\in A$.  Let $C=\lbrace (b,a)\rbrace$.  Define $f:C\to R$ by $f(b,a)=(a,b)$.  Since $(p_1\circ f, p_2\circ f)\in R_C$, which is symmetric on $\hom(C,A)$, there is a $g = (g_1,g_2):C\to R$ such that $(g_1,g_2)= (p_1\circ g, p_2\circ g)=(p_2\circ f,p_1\circ f)$.  So $(b,a)=(p_2(a,b),p_1(a,b))=(p_2\circ f(b,a),p_1\circ f(b,a))=(g_1(b,a),g_2(b,a)) = g(b,a)\in R$, which means that $R$ is a symmetric relation on $A$.

$(\Leftarrow)$.  Now suppose that $R$ is a symmetric relation on set $A$.  Let $C$ be an arbitrary set with $(p_1\circ f, p_2\circ f)\in R_C$, where $f:C\to R$ is some function.  Since $R$ is symmetric, $t:R\to R$ given by $t(a,b)=(b,a)$ is well-defined.  We also have the equations $p_1=p_2\circ t$ and $p_2=p_1\circ t$.  As a result, $(p_2\circ f, p_1\circ f) = (p_1\circ t\circ f, p_2\circ t\circ f) \in R_C$ as well, showing that $R_C$ is symmetric on $\hom(C,A)$.  But $C$ is arbitrary, $R$ is a symmetric relation object on $A$.
\item (transitivity).  $(\Rightarrow)$.  Suppose $R$ is a transitive relation object on $A$, with $(a,b),(b,c)\in R$.  Let $C=\lbrace (a,c)\rbrace$, where $a,b,c\in A$..  Define $f,g:C\to R$ by $f(a,c)=(a,b)$ and $g(a,c)=(b,c)$.  Write $f=(f_1,f_2)=(p_1\circ f, p_2\circ f)$ and $g=(g_1,g_2)=(p_1\circ g,p_2\circ g)$.  Since $f_2(a,c)=b=g_1(a,c)$, and $R_C$ is transitive, we must have $(f_1,g_2)\in R_C$, which means that there is $h:C\to R$ with $h=(h_1,h_2)=(p_1\circ h, p_2\circ h) =(f_1,g_2)$.  But this implies that $(a,c)=(f_1(a,c),g_2(a,c))=h(a,c)\in R$.  As a result, $R$ is a transitive relation on set $A$.

$(\Leftarrow)$.  Now suppose that $R$ is a transitive relation on set $A$.  Let $C$ be an arbitrary set with $f=(f_1,f_2)=(p_1\circ f,p_2\circ f), g=(g_1,g_2)=(p_1\circ g,p_2\circ g)\in R_C$.  Suppose $f_2=g_1=x:C\to A$.  Define $h:C\to A\times A$ by $h(c)=(f_1(c),g_2(c))$.  Since $(f_1(c),x(c))=(f_1(c),f_2(c))=f(c) \in R$ and $(x(c),g_2(c))= (g_1(c),g_2(c))=g(c)\in R$, we have $(f_1(c),g_2(c))\in R$ as $R$ is transitive.  This shows that $h$ maps $C$ into $R$, or $(f_1,g_2)=h=(p_1\circ h,p_2\circ h)\in R_C$.  So $R_C$ is transitive.  As $C$ is arbitrary, $R$ is a transitive relation object on $A$.
\end{enumerate}
Finally, collecting all of the above results, we see that $R$ is an equivalence relation object on $A$ iff $R$ is an equivalence relation on $A$.
\end{proof}

\textbf{Remark}.  Dually, one can define a \emph{corelation} on objects.  We invite the reader to formulate the exact notion of a corelation from one object to another.

\begin{thebibliography}{9}
\bibitem{fb} F. Borceux \emph{Categories and Structures, Handbook of Categorical Algebra II}, Cambridge University Press, Cambridge (1994)
\end{thebibliography}
%%%%%
%%%%%
nd{document}