%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[twocolumn,english]{amsbook}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\setlength\parskip{\smallskipamount}
\setlength\parindent{0pt}
\usepackage{graphicx}
\usepackage{amssymb}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \numberwithin{section}{chapter}
 \theoremstyle{plain}    
 \newtheorem{thm}{Theorem}[section]
 \numberwithin{equation}{section} %% Comment out for sequentially-numbered
 \numberwithin{figure}{section} %% Comment out for sequentially-numbered
 \theoremstyle{definition}
  \newtheorem*{example*}{Exemple}
 \theoremstyle{definition}
 \newtheorem*{defn*}{Définition}
 \theoremstyle{definition}
  \newtheorem{xca}{Exercice}
 \theoremstyle{remark}
 \newtheorem*{rem*}{Remarque}
 \theoremstyle{definition}
  \newtheorem{problem}[thm]{Problem}
 \theoremstyle{plain}    
 \newtheorem{algorithm}[thm]{Algorithme} %%Delete [thm] to re-start numbering
 \theoremstyle{plain}    
 \newtheorem*{thm*}{Théorème} 
 \theoremstyle{plain}    
 \newtheorem*{prop*}{Proposition} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}

\usepackage[francais,american]{babel}
\makeatother
\begin{document}

\chapter{Relations (section 4.1, 4.2 and 4.4)}


\section{Introduction}

A mere set of words would not make a good dictionary. 

It would be a pain to find a particular word!

A usable dictionary has some structure: the words are sorted.

In general, the more \emph{structure} a set have, the more useful
it is.

A way to bring structure into this set is to describe the \emph{relations}
between its elements, or between its elements and the elements of
another set. 

In this section we will see how we can formalize and study relations.

\begin{example*}
Imagine you want to build a house. 

Figure \ref{fig.house} shows the tasks that need to be completed.
%
\begin{figure}
\begin{center}\includegraphics[%
  width=0.75\textwidth]{house} \end{center}


\caption{\label{fig.house}Tasks to build a house}
\end{figure}


Let $S:=\{ F,W,E,I,O,R\}$ be the set of all tasks.

Problem: can we do the tasks in any order ?

%

%

%

%

%

%%

For example, it would be better to build the walls AFTER the foundations!

$S$ in itself does not contain enough information to choose a correct
order. %
\begin{figure}
\begin{center}\includegraphics[%
  width=0.75\textwidth]{house-PERT}\end{center}


\caption{\label{fig.house-PERT}Constraints between the tasks to build a house}
\end{figure}


Set of constraints: $\rho:=\{(F,W),(W,O),(W,E),(R,E),(R,I)\}$.

This set of constraints gives some structure to $S$, and makes it
useful.
\end{example*}

\section{Relations}


\subsection{Definitions}

\begin{defn*}
A \emph{binary relation} on a set $S$ is a subset $\rho$ of $S\times S$.

Let $x$ and $y$ be two elements of $S$.

Then $x$ is \emph{in relation} with $y$ (denoted $x\textrm{ }\rho\textrm{ }y$)
iff $(x,y)\in\rho$.
\end{defn*}
\begin{example*}
Let $\rho$ be the relation {}``is a prerequisite for'':

\[
\rho:=\{(F,W),(W,O),(W,E),(R,E),(R,I)\}\]


Then, $(F,W)\in\rho$, but $(I,O)\notin\rho$.

So, $F\textrm{ }\rho\textrm{ }W$ is true, whereas $I\textrm{ }\rho\textrm{ }O$
is false.
\end{example*}
A relation can be defined by a property.

\begin{xca}
Let $S:=\{1,2,3,4,5\}$. Draw the relations defined by:
\begin{enumerate}
\item $x\textrm{ }\rho_{1}\textrm{ }y$ iff $x=y$;
\item $x\textrm{ }\rho_{2}\textrm{ }y$ iff $x\leq y$;
\item $x\textrm{ }\rho_{3}\textrm{ }y$ iff $x$ divides $y$;
\item $x\textrm{ }\rho_{4}\textrm{ }y$ iff $x-y$ is even.
\end{enumerate}
\end{xca}
\begin{defn*}
A \emph{binary relation} between two sets $S$ and $T$ is a subset
$\rho$ of $S\times T$.

A \emph{n-ary relation} between $n$ sets $S_{1},\ldots,S_{n}$ is
a subset $\rho$ of $S_{1}\times\cdots\times S_{n}$.
\end{defn*}
\begin{example*}
Let $M$ be a set of male and $F$ a set of female students.

We can define the relation {}``is married to''.
\end{example*}

\subsection{Basic properties of relations}

Is there anything particular about the relation {}``is married to''
?

%

%

%

%

%

%%

\begin{defn*}
Let $\rho$ be a relation between $S$ and $T$. 
\begin{itemize}
\item $S$ is \emph{one-to-one} if any element of $S$ and $T$ appears
at most once in $\rho$;
\end{itemize}
\vspace{0.3cm}
\begin{center}\includegraphics{one-to-one}\end{center}
\vspace{0.3cm}

\begin{itemize}
\item $S$ is \emph{one-to-many} if any element of $T$ appears at most
once in $\rho$;\vspace{0.3cm}

\end{itemize}
\vspace{0.3cm}
\begin{center}\includegraphics{one-to-many}\end{center}
\vspace{0.3cm}

\begin{itemize}
\item $S$ is \emph{many-to-one} if any element of $S$ appears at most
once in $\rho$;
\end{itemize}
\vspace{0.3cm}
\begin{center}\includegraphics{many-to-one}\end{center}
\vspace{0.3cm}

\begin{itemize}
\item $S$ is \emph{many-to-many} in all other cases.
\end{itemize}
\vspace{0.3cm}
\begin{center}\includegraphics{many-to-many}\end{center}
\vspace{0.3cm}

\end{defn*}
%(pictures needs to be added below).

\begin{example*}
Is $x$ lower or equal to itself ?
\end{example*}
\begin{defn*}
A relation $\rho$ on a set $S$ is \emph{reflexive} iff \[
(\forall x\in S)\textrm{ }x\textrm{ }\rho\textrm{ }x.\]

\end{defn*}
%

%

%%

\begin{example*}
Assume $x$ is equal to $y$. Is $y$ equal to $x$ ?
\end{example*}
\begin{defn*}
A relation $\rho$ on a set $S$ is \emph{symmetric} iff \[
(\forall x\in S)(\forall y\in S)\textrm{ }(x\textrm{ }\rho\textrm{ }y)\leftrightarrow(y\textrm{ }\rho\textrm{ }x).\]

\end{defn*}
%

%

%

%%

\begin{example*}
Assume $x\leq y$ and $y\leq x$. What can you say about $x$ and
$y$?
\end{example*}
\begin{defn*}
A relation $\rho$ on a set $S$ is \emph{antisymmetric} iff \[
(\forall x\in S)(\forall y\in S)[(x\textrm{ }\rho\textrm{ }y)\textrm{ and }(y\textrm{ }\rho\textrm{ }x)]\rightarrow(x=y).\]

\end{defn*}
%

%

%

%%

\begin{example*}
Assume $x<y$ and $y<z$. What can you say about $x$ and $z$?
\end{example*}
\begin{defn*}
A relation $\rho$ on a set $S$ is \emph{transitive} iff \[
(\forall x\in S)(\forall y\in S)(\forall z\in S)[(x\textrm{ }\rho\textrm{ }y)\textrm{ and }(y\textrm{ }\rho\textrm{ }z)]\rightarrow(x\textrm{ }\rho\textrm{ }z).\]

\end{defn*}
%

%

%

%%

\begin{example*}
What are the properties of the following relations
\begin{enumerate}
\item $<$, $\leq$, $=$;
\item {}``is married to'';
\item {}``is a friend of'';
\item {}``has the same color than''.
\end{enumerate}
\end{example*}

\subsection{Operations on relations}

A relation is basically a set. So, we can use all usual set operations
on relations.

\begin{rem*}
Let $S$ and $T$ be two sets.

The powerset $\wp(S\times T)$ is the set of all binary relations
between $S$ and $T$.
\end{rem*}
\begin{defn*}
Let $\rho$ and $\sigma$ be two relations between $S$ and $T$.

We can construct the following new relations:
\begin{itemize}
\item union: $\rho\cup\sigma$,
\item intersection: $\rho\cap\sigma$,
\item complement: $\rho'$,
\item \ldots{}
\end{itemize}
\end{defn*}
\begin{example*}
Let $S:=\N$.
\begin{enumerate}
\item What is the union of $<$and $=$?
\item What is the intersection of $<$ and $>$?
\item What is the union of $<$ and $>$?
\item Is $<$a sub relation of $\leq$ ?
\end{enumerate}
\end{example*}

\subsection{Closure of a relation}

\begin{example*}
Lets come back to the example of the house building.%
\begin{figure}
\begin{center}\includegraphics[%
  width=0.75\textwidth]{house-PERT}\end{center}


\caption{\label{fig.house-PERT2}Constraints between the tasks to build a
house}
\end{figure}


Do you have to do the electricity after the foundations ?

Foundations is not a direct prerequisite for electricity. 

However, it still needs to be done before electricity.

The relation {}``has to be done before'' is transitive, and contains
the relation 

{}``is a prerequisite for''. It's the \emph{transitive closure}
of {}``is a prerequisite for''.
\end{example*}
\begin{defn*}
Let $\rho$ be a relation.

The \emph{transitive closure} of $\rho$ is the smallest transitive
relation $\rho^{*}$containing $\rho$.
\end{defn*}
\begin{xca}
Draw the transitive closure of {}``is a prerequisite for''.
\end{xca}
\begin{problem}
Is there an algorithm for computing the transivite relation of a relation?
\end{problem}
%

%

%

%

%

%

%%

\begin{algorithm}
Construction of the transitive closure $\rho^{*}$. 
\begin{enumerate}
\item $\rho^{*}:=\rho$;
\item Find $x$, $y$, $z$ such that $(x\textrm{ }\rho^{*}y)$, $(y\textrm{ }\rho^{*}z)$,
and $(x\textrm{ }\not\rho^{*}z)$;
\item If no such triple exists, $\rho^{*}$is transitive; Exit;
\item $\rho^{*}:=\rho^{*}\cup\{(x,z)\}$;
\item Repeat at step 2.
\end{enumerate}
\end{algorithm}
\begin{rem*}
The order in which you add the pairs to $\rho$ is irrelevant.
\end{rem*}
\begin{example*}
Draw the relation {}``has to be done before'' (Figure~\ref{fig.house-PERT2}).
\end{example*}
\begin{defn*}
Let $\rho$ be a relation.

The \emph{reflexive closure} of $\rho$ is the smallest reflexive
relation containing $\rho$.

The \emph{symmetric closure} of $\rho$ is the smallest symmetric
relation containing $\rho$.
\end{defn*}
\begin{xca}
Consider the following relation:

\vspace{0.3cm}
\begin{center}\includegraphics{relation}\end{center}
\vspace{0.3cm}

\begin{enumerate}
\item Draw its reflexive closure
\item Draw its symmetric closure
\item Draw its transitive closure
\item Draw its antisymmetric closure
\end{enumerate}
\end{xca}
%

%

%

%

%%

\begin{rem*}
The antisymmetric closure of a relation cannot be uniquely defined!
\end{rem*}

\section{Equivalence relations}

\begin{example*}
Consider a set of cars, and the relation {}``has the same color as''.

What are the properties of this relation?
\end{example*}
\begin{defn*}
An \emph{equivalence relation} is a relation which is
\begin{enumerate}
\item Reflexive
\item Symmetric
\item Transitive
\end{enumerate}
\end{defn*}
%

\begin{defn*}
Let $\rho$ be a relation on a set $S$, and $x$ be an element of
$S$.

The \emph{equivalence class} of $x$ is the set $[x]$of all elements
$y$ such that $x\textrm{ }\rho\textrm{ }y$.
\end{defn*}
\begin{example*}
The equivalence class of a car is the set of all cars having same
color.
\end{example*}
\begin{rem*}
If $x\textrm{ }\rho\textrm{ }y$, then $[x]=[y]$.
\end{rem*}
\begin{example*}
Consider the relation $\equiv_{3}$ on $\N$ defined by $x\equiv_{3}y$
iff $3$ divides $x-y$.

(we also say that $x$ and $y$ are \emph{congruent} modulo $3$:
$x\equiv y\textrm{ }(mod\textrm{ }3)$)

What are the equivalence classes?
\end{example*}
\begin{defn*}
A partition of a set $S$ is a collection of subsets $\{ A_{1},\ldots,A_{k}\}$
of $S$ such that:
\begin{enumerate}
\item $A_{1}\cup\cdots\cup A_{k}=S$ 
\item $A_{i}\cap A_{j}=\emptyset$ for any $i$, $j$.
\end{enumerate}
\end{defn*}
\begin{example*}
Consider a set $S$ of car, whose color are either red, blue, or green.

Define the following subsets of $S$: 

$R$ (red cars), $B$ (blue cars), and $G$ (green cars) .

Then, $\{ R,B,G\}$ is a partition of $S$.
\end{example*}
The equivalence relation {}``has the same color'' and the partition
of the cars by color are closely related.

\begin{thm*}
In general:
\begin{enumerate}
\item An equivalence relation on $S$ defines a unique partition of $S$.
\item A partition of $S$ defines a unique equivalence relation on $S$.
\end{enumerate}
\end{thm*}
\begin{proof}
Left as exercise:
\begin{enumerate}
\item Construct the collection $\{ A_{1},\ldots,A_{k}\}$, and prove it
is indeed a partition of $S$.
\item Construct the relation $\rho$, and prove it's indeed an equivalence
relation.
\end{enumerate}
\end{proof}
\begin{defn*}
Let $S$ be a set, and $\rho$ be a relation on $S$.

The set of all the equivalence classes is called the \emph{quotient}
of $S$ by $\rho$.
\end{defn*}
\begin{rem*}
This method is used a lot in set theory:

Construction of $\Z$ from $\N$.

Construction of $\Z/n\Z$ (integers modulo n) from $\Z$.

Construction of $\Q$ from $\Z$. 
\end{rem*}

\section{Partially Ordered Sets}

\begin{example*}
What are the properties of the relation {}``has to be done before''
on the tasks to build a house ?
\end{example*}
\begin{defn*}
A \emph{partially ordered set} (or \emph{poset}) is a set $S$ with
a relation $\rho$ which is
\begin{enumerate}
\item Reflexive
\item Antisymmetric
\item Transitive
\end{enumerate}
\end{defn*}
\begin{example*}
Which of the following are posets ?
\begin{enumerate}
\item $(\{1,2,3,4\},\leq)$;
\item $(\{1,2,3,4\},<)$;
\item $(\{1,2,3,4\},=)$;
\item $(\{1,2,3,4\},\rho)$, with $x\textrm{ }\rho\textrm{ }y$ iff $x$
divides $y$.
\item $(\wp(\{1,2,3,4\}),\subseteq)$.
\end{enumerate}
\end{example*}

\subsection{Drawing posets; Hasse diagrams}

\begin{defn*}
Some names:
\begin{itemize}
\item \emph{Node} (or \emph{vertex})
\item \emph{Predecessor}
\item \emph{Immediate predecessor}
\item \emph{Maximal element}
\item \emph{Minimal element}
\item \emph{Least element}
\item \emph{Greatest element}
\end{itemize}
\end{defn*}
%

\begin{defn*}
The \emph{Hasse diagram} of a poset is a drawing of this poset such
that:
\begin{itemize}
\item If $x\textrm{ }\rho\textrm{ }y$, then $y$ is higher than $x$;
\item The loops are not drawn;
\item There is a segment linking $x$ and $y$ iff $x$ is an immediate
predecessor of $y$.
\end{itemize}
\end{defn*}
\begin{example*}
Draw all posets on $1$, $2$, $3$, $4$ indistinct nodes.

How many such posets are there on $10$ nodes ?
\end{example*}

\subsection{Scheduling}

Scheduling a set of tasks consist in allocating tasks to resources,
subject to certain constraints.

\begin{example*}
Consider the house building problem, with the following assumptions:
\begin{itemize}
\item All tasks take the one day to complete;
\item One worker can only work on one task every day;
\item It does not save time to have two workers working on the same task.
\end{itemize}
%
\begin{figure}
\begin{center}\includegraphics[%
  width=0.75\textwidth]{house-PERT}\end{center}


\caption{\label{fig.house-PERT2}Constraints between the tasks to build a
house}
\end{figure}


Schedule the tasks between 2 workers to optimize the completion time:

\vspace{0.3cm}
\begin{center}\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline 
&
Day 1&
Day 2&
Day 3&
Day 4&
Day 5&
Day 6&
Day 7\tabularnewline
\hline
\hline 
Worker 1&
&
&
&
&
&
&
\tabularnewline
\hline
Worker 2&
&
&
&
&
&
&
\tabularnewline
\hline
\end{tabular}\end{center}
\vspace{0.3cm}

What if there is one worker ? 

\vspace{0.3cm}
\begin{center}\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline 
&
Day 1&
Day 2&
Day 3&
Day 4&
Day 5&
Day 6&
Day 7\tabularnewline
\hline
\hline 
Worker 1&
&
&
&
&
&
&
\tabularnewline
\hline
\end{tabular}\end{center}
\vspace{0.3cm}

What if there are three workers ?

\vspace{0.3cm}
\begin{center}\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline 
&
Day 1&
Day 2&
Day 3&
Day 4&
Day 5&
Day 6&
Day7\tabularnewline
\hline
\hline 
Worker 1&
&
&
&
&
&
&
\tabularnewline
\hline
Worker 2&
&
&
&
&
&
&
\tabularnewline
\hline
Worker 3&
&
&
&
&
&
&
\tabularnewline
\hline
\end{tabular}\end{center}
\vspace{0.3cm}

\end{example*}
\begin{prop*}
Consider the problem of scheduling n tasks on p processors, subject
to precedence constraints, with the same assumptions and goal as above. 
\end{prop*}
\begin{itemize}
\item $1$ or $2$ processors: algorithms in $O(n^{2})$;
\item $3$ processors: complexity unknown;
\item $p$ processors: NP-complete \\
(basically the only known algorithm is exhaustive search);
\item $\infty$ processors: $O(n)$.
\end{itemize}
This is typical from scheduling problems, where a very small change
in the constraints can make huge differences in the complexity of
the problems.

Also, usually the complexity is as follow:

\begin{itemize}
\item No constraints: low complexity;
\item Some constraints: higher and higher complexity;
\item More constraints: NP-complete. The only known algorithm is exhaustive
search through all plausible cases (\emph{branch-and-cut});
\item Even more constraints: still NP-complete, but easier. Indeed more
and more cases can be thrown away very early.
\end{itemize}
Having very good scheduling algorithms is vital in industry, because
a 1\% difference in completion time (for example) can save thousands
of dollars. Consequently, research in this topic is well financed!


\section{Conclusion}

\begin{itemize}
\item The more structure a set has, the more useful it is.
\item Defining a relation is a way to add structure to a set.
\item Relations, posets, equivalence relations, \ldots{} are just abstract
models of natural notions commonly used in real life.
\end{itemize}

\end{document}
