binary-relations.tex

\documentclass[11pt]{article}

\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\theoremstyle{plain}
\newtheorem{defn}{Definition}
\theoremstyle{definition}
\newtheorem*{example}{Example}

\usepackage{multicol}
\usepackage{enumitem}

\usepackage{color}
\usepackage{graphicx}
\graphicspath{ {./img/} }
\usepackage{epstopdf}

\usepackage{wasysym}

\usepackage{listings}
\lstdefinestyle{go}{
  basicstyle=\footnotesize\ttfamily,
  frame=single,
  numbers=left,
  numberstyle=\tiny,
  tabsize=8,
}

\title{Some important binary relations}
\author{Alberto Cortés \\ {\texttt <alcortesm@gmail.com>}\\
Gorka Guardiola Múzquiz \\ {\texttt <paurea@gmail.com>}}
\date{\today}

\begin{document}

\maketitle

\section{Binary Relations}

In mathematics, a binary relation on a set $A$ is a collection of ordered pairs of elements of $A$.
In other words, it is a subset of the Cartesian product $A^2 = A \times A$.

\begin{example}
  Let us say Alice ($a$) is older than Bob ($b$), who is older than Carol ($c$),
  then $A = \left\{a, b, c\right\}$ and
  there is a realtion $R =$ \textsl{``is older than''} on $A$.
\end{example}

More generally, a binary relation between two sets $A$ and $B$ is a subset of $A \times B$,
this is $R \subseteq A \times B$,
therefore a binary relation $R$ is usually defined as an ordered triple $(A, B, G)$
where $A$ and $B$ are arbitrary sets, and $G \subseteq A \times B$.
The set $A$ is called the \textbf{domain} of the relation,
$B$ is called the \textbf{codomain} and
$G$ is called the \textbf{graph}.

The statement $(a,b) \in G$ is read ``\textsl{a is R-related to b}'',
and is denoted by $aRb$ or $R(a,b)$.

\begin{example}
  Cotinuing the example above,
  $aRb \land bRc$ means that
  $a$ is older than $b$ and
  $b$ is older than $c$,
\end{example}

\begin{example}
  Let us say relation $R = \text{``is smaller than''}$ on the set $\mathbb{N}$,
  then $\forall x \in \mathbb{N}, xR(x+1) \text{ and } \neg xRx$.
\end{example}


\subsection{Common Representations}

\paragraph{Graphs} As binary relations are basically pairs,
they can be represented as directed graphs.
For example,
let $A = \left\{a, b, c, d\right\}$ and $R \subseteq A^2$.
The graph for $aRb \land aRc \land cRd \land dRa \land dRd$ would be
  \begin{figure}[th!]
    \centering
    \includegraphics[width=0.5\textwidth,keepaspectratio]{examp_dot.pdf}
    \caption{Example of binary relation.}
  \end{figure}

\paragraph{Arrays} Binary relations can also be represented as arrays.
For example,
the previous graph can be represented in array form as:
\begin{equation*}
  R = \bordermatrix{~ & a & b & c & d \cr
  a & 0 & 1 & 1 & 0 \cr
  b & 0 & 0 & 0 & 0 \cr
  c & 0 & 0 & 0 & 1 \cr
d & 1 & 0 & 0 & 1 \cr}
\end{equation*}
This matrix is called incidence matrix of the graph.

\section{In Computer Science}

Binary relations are heavily used in computer science.
As each relation is basically a pair,
it can be easily represented as an array of 2 elements in any programming language.

For example, the previous graph can be represented in Go as:

\lstinputlisting[style=go]{src/simple-arrays/simple-arrays.go}

Output: \verb+[a b] [a c] [c d] [d a] [d d]+

Or you can use something a little more fancy by joining relations by source:

\lstinputlisting[style=go]{src/map-slice/map-slice.go}

Output: \verb+map[d:[a d] a:[a b] c:[d]]+

This are just simple examples,
actual implementations will depend on the particular problem you are trying to solve.
Anything which can be interpreted as an arrow in a directed graph can be mapped into the pair of a relation.
A pointer from a data structure identifying the origin and  traversing an array or a map (which goes from index to element) are all examples of this.

\section{Properties}

\subsection{Symmetricity}

\begin{defn}
  A \textbf{symmetric} relation can be defined as
  \[ \forall a, b \in S: aRb \implies bRa .\]
  For example ``is a sibling of'' (if Alice is a sibling of Bob, then Bob must be a sibling of Alice).
  Another example would be the relation depicted by the graph in Figure~\ref{fig:sym}.
  \begin{figure}[th!]
    \centering
    \includegraphics[width=0.3\textwidth,keepaspectratio]{sym_dot.pdf}
    \caption{Symmetric relation.\label{fig:sym}}
  \end{figure}
  Note that there is an opposite arrow for each arrow.
\end{defn}

\begin{defn}
  An \textbf{asymmetric} relation can be defined as
  \[ \forall a, b \in S: aRb \implies \neg bRa .\]
  For example ``is taller than'' (if Alice is taller than Bob, then Bob cannot be taller than Alice).
  Another example would be the relation depicted by the graph in Figure~\ref{fig:asym}.
  Note that there is never an opposite arrow for any given arrow.

  \begin{figure}[th!]
    \centering
    \includegraphics[width=0.3\textwidth,keepaspectratio]{asym_dot.pdf}
    \caption{Asymmetric relation.\label{fig:asym}}
  \end{figure}
\end{defn}

\begin{defn}
  Relation $R$ is \textbf{antisymmetric} $\iff \forall a, b \in S: aRb \land bRa \implies a = b$.
  For example ``is greater or equal to''.
  Another way to express that is relation $R$ is antisymmetric $\iff \forall a, b \in S: aRb \land a \neq b \implies \neg bRa$.
  Another example would be the relation depicted by the graph in Figure~\ref{fig:antisym}.
  Note that the only arrows having and opposite arrow are the ones from a node to itself.

  \begin{figure}[th!]
    \centering
    \includegraphics[width=0.3\textwidth,keepaspectratio]{antisym_dot.pdf}
    \caption{Antisymmetric relation.\label{fig:antisym}}
  \end{figure}
\end{defn}

\begin{defn}
  Relation $R$ is \textbf{nonsymmetric} $\iff$ $R$ is not symmetric, asymetric or antisymmetric.
  For example ``is the brother of'' when you have males and females and brother $\neq$ sister).
\end{defn}

\subsection{Reflexivity}

\begin{defn}
  Relation $R$ is \textbf{reflexive} $\iff \forall a \in S, aRa$.
  For example ``is equal to'', ``is as tall as''.
  Another example would be the relation depicted by the graph in Figure~\ref{fig:refl}.
  Note that the only arrows having and opposite arrow are the ones from a node to itself.
  \begin{figure}[th!]
    \centering
    \includegraphics[width=0.3\textwidth,keepaspectratio]{refl_dot.pdf}
    \caption{Reflexive relation.\label{fig:refl}}
  \end{figure}
\end{defn}

\begin{defn}
  Relation $R$ is \textbf{irreflexive} $\iff \forall a \in S, \neg aRa$.
  For example ``is greater than'', ``is to the left of''.
\end{defn}

\begin{defn}
  Relation $R$ is \textbf{non-reflexive} $\iff R$ is neither reflexive nor irreflexive.
  For example ``is grandfather of'', as you can be your own granfather,
  see Ray Stevens song ``I am my own granpa'' \smiley.
\end{defn}

\subsection{Transitivity}

\begin{defn}
  Relation $R$ is \textbf{transitive} $\iff \forall a, b, c \in S: aRb \land bRc \implies aRc$.
  For example ``is descendant of''.
\end{defn}

\begin{defn}
  Relation $R$ is \textbf{intransitive} $\iff \forall a, b, c \in S: aRa \land bRc \implies \neg aRc$.
  For example ``is complementary color of'' or ``is opposite of''.
\end{defn}

\begin{defn}
  Relation $R$ is \textbf{nontransitive} if it neither transitive nor intransitive.
  For example ``is child of'' (Antigore, Oedipus and Jocarta).
\end{defn}


\subsection{Equivalence}

\begin{defn}
  Relation $R$ is \textbf{equivalent} $\iff$ $R$ is reflexive, symmetric and transitive.
  For example ``is congruent to''\footnote{two numbers are congruent if they have the same remainder when divided by some other number.} or ``is equal to''.
\end{defn}

\subsection{Transitive Closure}

\begin{defn}
 Given a relation $R$ over a set $S$, its transitive closure is the smallest transitive relation containing $R$.
\end{defn}

To obtain the \textbf{transitive closure}, $tr(R)$, take all elements $\alpha_i \in R$ which are on the left side of a tuple in $R$.
For any element $\beta_i$ which is \textbf{reachable} following the relation $R$, the tuple $(\alpha_i, \beta_i) \in tr(R)$.
In the case of an equivalence, taking only one $\alpha_i$ gives back all the tuples in the transitive closure.
This is because $(\alpha_i, \beta_i) \implies (\beta_i, \alpha_i)$ and \emph{all the elements are reachable}.
In other words, for an equivalence \emph{all elements represent the relation equally}.
This permits us to form an \textbf{equivalence class}, where we look at the set $S$ through the lense of $R$.
The \emph{equivalence class}, is a smaller or equal set where each element is a representative of a distinct equivalent subset of $S$.

TODO draw all this with graphs, possibly using graphviz (dot).
\end{document}