\setcounter{page}{64}
\setcounter{chapter}{3}

\captionsetup{labelformat=default,font=footnotesize}


\chapterimage{helene}
\chaptertext{Hélène aime Chri-Chri et Chri-Chri aime Johanna mais est-ce
que Hélène aime Johanna? Chri-Chri  aime Johanna mais est-ce que Johanna
aime  Chri-Chri en  retour?  Est-ce que  Johanna  s'aime elle-même?  Ces
questions  fondamentales  sont liées  à  l'étude  des  propriétés de  la
relation \og ...aime...\fg{}.

Quels liens rajouter entre des pages web pour pouvoir aller de
n'importe quelle page vers n'importe quelle autre?
C'est un problème de fermeture transitive d'une relation...

Le SQL: de la programmation relationnelle...

Les  réseaux sociaux:  mettre en  relation des  sites marchands  avec de
potentiels acheteurs.

Vous l'avez compris: les relations, ça compte en informatique.

Ça compte aussi beaucoup de définitions: il y en a 43 dans ce chapitre...
}



\setlength{\topsep}{1pt}
\setlength{\parskip}{1pt}
\setlength{\partopsep}{1pt}
\setlength{\parsep}{1pt}
\chapter{Relations}

\begin{flushright}
  \begin{quote}
    {\itshape
\textbf{Johanna}: Si votre relation est aussi compliquée, pourquoi ne pas laisser tomber ? C’est peu vraisemblable que ça fonctionne un jour.\\
\textbf{Hélène}: Quand on aime quelqu’un, se battre vaut le coup, peu importe les probabilités.}
  \end{quote}
Hélène et les garçons, épisode 217 (1992)
\end{flushright}


\section{Préliminaires...}

Nous aurons besoin à l'occasion de quelques outils de calculs qui seront
repris plus en détail dans les mois à venir.


\subsection{Un peu de calcul matriciel}


Nous aurons  besoin de  multiplier des matrices  entre elles.  Voici une
disposition pratique pour effectuer les calculs.

$$c_{ij}=\displaystyle\sum_{k=1}^{n}a_{ik}b_{kj}$$


avec $n$  le nombre de  colonnes de  A qui doit  être égal au  nombre de
lignes de B.


\subsubsection{Produit de deux matrices \og carré\fg{}}
\renewcommand\myunit{0.9cm}

\begin{center}
\begin{tikzpicture}[>=latex]
% unit

% the styles
\tikzset{node style sp/.style={draw,circle,minimum size=\myunit}}  
\tikzset{node style ge/.style={circle,minimum size=\myunit}}
\tikzset{arrow style mul/.style={draw,sloped,midway,fill=white}}
\tikzset{arrow style plus/.style={midway,sloped,fill=white}}
% defintion of matrices
\matrix (A) [matrix of math nodes,%
             nodes = {node style ge},%
             left delimiter  = (,%
             right delimiter = )] at (0,0)
{%
  a_{11} & a_{12}  & a_{13}  \\ 
  \node[node style sp] {a_{21}};& \node[node style sp] {a_{22}};& \node[node style sp] {a_{23}}; \\ 
  a_{31}& a_{32}  & a_{33}  \\ 
}; 
\node [draw,below] at (A.south) { $A$ : \textcolor{red}{$3$ lignes} $3$ colonnes};
\matrix (B) [matrix of math nodes,%
             nodes = {node style ge},%
             left delimiter  = (,%
             right delimiter =)] at (5*\myunit,5*\myunit)
{% 
  b_{11} &  \node[node style sp] {b_{12}};& b_{13}  \\ 
  b_{21} & \node[node style sp] {b_{22}}; & b_{23} \\ 
  b_{31} & \node[node style sp] {b_{32}}; & b_{33}  \\ 
};
\node [draw,above] at (B.north) { $B$ : $3$ lignes \textcolor{red}{$3$ colonnes}}; 
% matrice résultat
\matrix (C) [matrix of math nodes,%
             nodes = {node style ge},%
             left delimiter  = (,%
             right delimiter = )] at (5*\myunit,0)
{% 
  c_{11} & c_{12} & c_{13} \\ 
  c_{21}&  \node[node style sp,red] {c_{22}};& c_{23} \\ 
  c_{31}&  c_{32} &  c_{33} \\ 
}; 
\node [draw,below] at (C.south) {$ C=A\times B$ : \textcolor{red}{$3$ lignes}  \textcolor{red}{$3$ colonnes}};
% arrows
\draw[blue] (A-2-1.north) -- (C-2-2.north);
\draw[blue] (A-2-1.south) -- (C-2-2.south);
\draw[blue] (B-1-2.west)  -- (C-2-2.west);
\draw[blue] (B-1-2.east)  -- (C-2-2.east);
 \draw[<->,red](A-2-1) to[in=180,out=90] (B-1-2);%
%       node[arrow style mul] (x) {$a_{21}\times b_{12}$};
 \draw[<->,red](A-2-2) to[in=180,out=90](B-2-2);%
%       node[arrow style mul] (y) {$a_{22}\times b_{22}$};
 \draw[<->,red](A-2-3) to[in=180,out=90](B-3-2);%
%       node[arrow style mul] (z) {$a_{23}\times b_{32}$};
% \draw[red,->] (x) to node[arrow style plus] {${\Large +}$} (y)%
%                   to node[arrow style plus] {${\Large +}$} (z);
%                   %
%                   % to (C-3-3.north west);
% \draw[->,red,decorate,decoration=zigzag] (z) -- (C-2-2.north west);
\end{tikzpicture} 
\end{center}


  \begin{DANGER}[produit de matrice non commutatif]
    Le produit  de deux matrices  n'est pas  commutatif. Cela
    signifie qu'en général $A\times B\neq B\times A$.
    \end{DANGER}





\subsubsection{Produit d'une matrice \og carré\fg{} et d'une matrice \og colonne\fg{}}

\renewcommand\myunit{1.2cm}


\begin{center}
\begin{tikzpicture}[>=latex]
% unit

% the styles
\tikzset{node style sp/.style={draw,circle,minimum size=\myunit}}  
\tikzset{node style ge/.style={circle,minimum size=\myunit}}
\tikzset{arrow style mul/.style={draw,sloped,midway,fill=white}}
\tikzset{arrow style plus/.style={midway,sloped,fill=white}}
% defintion of matrices
\matrix (A) [matrix of math nodes,%
             nodes = {node style ge},%
             left delimiter  = (,%
             right delimiter = )] at (0,0)
{%
  a_{11} & a_{12}  & a_{13}  \\ 
  \node[node style sp] {a_{21}};& \node[node style sp] {a_{22}};& \node[node style sp] {a_{23}}; \\ 
  a_{31}& a_{32}  & a_{33}  \\ 
}; 
\node [draw,below] at (A.south) { $A$ : \textcolor{red}{$3$ lignes} $3$ colonnes};
\matrix (B) [matrix of math nodes,%
             nodes = {node style ge},%
             left delimiter  = (,%
             right delimiter =)] at (5*\myunit,5*\myunit)
{% 
   \node[node style sp] {b_{11}};  \\ 
  \node[node style sp] {b_{21}};  \\ 
  \node[node style sp] {b_{31}};   \\ 
};
\node [draw,above] at (B.north) { $B$ : $3$ lignes \textcolor{red}{$1$ colonne}}; 
% matrice résultat
\matrix (C) [matrix of math nodes,%
             nodes = {node style ge},%
             left delimiter  = (,%
             right delimiter = )] at (5*\myunit,0)
{% 
  c_{11}  \\ 
   \node[node style sp,red] {c_{21}}; \\ 
  c_{31} \\ 
}; 
\node [draw,below] at (C.south) {$ C=A\times B$ : \textcolor{red}{$3$ lignes}  \textcolor{red}{$1$ colonne}};
% arrows
\draw[blue] (A-2-1.north) -- (C-2-1.north);
\draw[blue] (A-2-1.south) -- (C-2-1.south);
\draw[blue] (B-1-1.west)  -- (C-2-1.west);
\draw[blue] (B-1-1.east)  -- (C-2-1.east);
 \draw[<->,red](A-2-1) to[in=180,out=90] (B-1-1);%
%       node[arrow style mul] (x) {$a_{21}\times b_{12}$};
 \draw[<->,red](A-2-2) to[in=180,out=90](B-2-1);
%       node[arrow style mul] (y) {$a_{22}\times b_{22}$};
 \draw[<->,red](A-2-3) to[in=180,out=90](B-3-1);%
%       node[arrow style mul] (z) {$a_{23}\times b_{32}$};
% \draw[red,->] (x) to node[arrow style plus] {${\Large +}$} (y)%
%                   to node[arrow style plus] {${\Large +}$} (z);
%                   %
%                   % to (C-3-3.north west);
% \draw[->,red,decorate,decoration=zigzag] (z) -- (C-2-1.north west);
\end{tikzpicture} 
\end{center}



\subsection{Calcul booléen}


Nous  allons  définir  trois  opérations  déjà évoquées  en  logique  sur
l'ensemble $\bigl\{0,1\bigr\}$:

\smallskip

\begin{center}
             \begin{tabularx}{0.25\textwidth}{IZIZ|ZI}
	     \whline
             $\oplus$&0&1\\
             \whline
             0       &0&1\\
             \hline
             1       &1&0\\
             \whline
             \end{tabularx}
\hfill
             \begin{tabularx}{0.25\textwidth}{IZIZ|ZI}
	     \whline
             $\barwedge$&0&1\\
             \whline
             0       &0&0\\
             \hline
             1       &0&1\\
             \whline
             \end{tabularx}
\hfill
\begin{tabularx}{0.25\textwidth}{IZIZ|ZI}
	     \whline
             $\veebar$&0&1\\
             \whline
             0       &0&1\\
             \hline
             1       &1&1\\
             \whline
             \end{tabularx}

           \end{center}
          
\smallskip
 
On pourra combiner le tout et multiplier et additionner des matrices booléennes avec ces opérations.

On utilisera aussi souvent la  matrice Attila$(n,m)$ qui ne contient que des 1.


\medskip




Soit par exemple $$A=
\begin{pmatrix}
 0&1&1\\
 1&1&0\\
 0&0&1 
\end{pmatrix}
\qquad
\text{ et }
\qquad
B=
\begin{pmatrix}
  1&1&0\\
  1&0&1\\
  0&1&1
\end{pmatrix}
$$


Calculer $A\oplus B$ (somme booléenne terme à terme), $A\oplus \text{Attila}(3,3)$ et  $A\barwedge B$ (produit matriciel en utilisant le produit booléen $\barwedge$  pour le produit des  termes et $\oplus$ pour leur somme).

\section{Relations binaires}

\subsection{Au CE1}

%\begin{figure}
\begin{center}
  \includegraphics[width=0.7\linewidth]{CE1-relations}
\end{center}
%\caption{Comment j'ai étudié les relations en CE1...}
\label{ce1}
%\end{figure}


\subsection{Généalogie}

 Voici mon arbre généalogique:


\begin{center}
\begin{tikzpicture}
\tikzstyle{every node}=[]
%\footnotesize
\node {Marcel \& Gisèle} [edge from parent fork down]
  [sibling distance=2cm]
  child {node {Berthe}}
  child {node {Kurt}
  };
\node at (5,0) {Günter \& Gertrude} [edge from parent fork down] 
  [sibling distance=2cm] 
  child {node {Tatiana}}
  child {node {Georgina}}
  child {node {Barbarella}};
\node at (1.9,-1.5) {\& } [edge from parent fork down] 
  [sibling distance=2cm] 
  child {node {Clovis}}
  child {node {Dagobert}}
  child {node {Mathémator}};
\end{tikzpicture}
\end{center}

Formez les couples $(x,y)$ tels que $x$ soit le grand-père de $y$.



\subsection{À l'IUT}

Une relation a pour but de décrire les \og liens\fg{} entre les éléments
de deux
voire plusieurs ensembles. Leur champ d'application est immense.

\begin{definition}
Une \textit{relation binaire}  entre deux ensemble E et  F est la donnée
de E, F et d'un
sous-ensemble du produit cartésien $E\times F$.

Une    \textit{relation   $n$-aire}    entre   $n$    ensembles   $E_1$,
$E_2$,...,$E_n$ est la donnée de ces ensembles et d'un sous-ensemble du produit cartésien $E_1\times
E_2\times \cdots E_n$.
\end{definition}



\begin{remarques}
  \begin{itemize}
  \item Dans  un premier  temps, nous nous  contenterons de  l'étude des
        relations binaires;
      \item les deux ensembles $E$ et $F$ peuvent être égaux;
\item en  fait, plus rigoureusement, une relation  binaire de l'ensemble
      $E$ vers (ou dans) l'ensemble $F$ est 
un triplet $\left( E,F,G_{\mathcal{R}}\right) $ où $G_{\mathcal{R}}$ est
une partie de $E\times F$ appelé le \textit{graphe} de la relation.
Par abus  et parce que ça  n'entraîne pas de confusions,  on confond une
relation avec son graphe.
  \end{itemize}
\end{remarques}




Il faut bien comprendre que pour définir parfaitement la relation $%
\mathcal{R}$ il nous faut conna\^{\i}tre trois éléments $E,F$ et $G_{%
\mathcal{R}}\subseteq E\times F$ ; si au moins l'un de ces trois élé%
ments manque, la relation $\mathcal{R}$ n'est pas définie. Si $G_{%
\mathcal{R}}=\{\}  ,$ $\mathcal{R}$ est la relation vide de $E$ vers $F$%
, ce sera forcément le cas si $E$ ou $F$ est vide. L'ensemble des
relations binaires de $E$ vers (ou dans) $F$ est noté $%
E\longleftrightarrow F$ ou $E\leftrightarrow F$ et est confondu, si besoin,
avec $\mathcal{P}\left( E\times F\right) ,$ l'ensemble des parties de $%
E\times F.$


Les écritures $\mathcal{R}\in E\longleftrightarrow F$ ou $\mathcal{R}%
:E\longleftrightarrow F$ ou $\mathcal{R}\in \mathcal{P}\left( E\times
F\right) $ doivent se traduire par \og $\mathcal{R}$ est une relation binaire
de $E$ vers $F$\fg{}. Si $E=F$ on dit que $\mathcal{R}$ est une relation
binaire de $E$ vers $E$ ou de $E$ dans $E$ ou encore une relation binaire 
\textbf{sur} $E$.

Si $(x,y)\in G_{\mathcal{R}},$ on dit que l'élément $x$ de
l'ensemble de départ $E$ est en relation par $\mathcal{R}$ avec l'él%
ément $y$ de l'ensemble d'arrivée $F$. L'écriture $x\mathcal{R}y$
ou $\mathcal{R}\left( x,y\right) $ est équivalente à $(x,y)\in G_{\mathcal{R}%
}$ ou $(x,y)\in \mathcal{R}$ puisque l'on se permet de confondre $\mathcal{R}
$ et $G_{\mathcal{R}}$ :%

$$
x\mathcal{R}y\Leftrightarrow \mathcal{R}\left( x,y\right) \Leftrightarrow
(x,y)\in G_{\mathcal{R}}\Leftrightarrow \left( x,y\right) \in \mathcal{R}
$$

et on dit que $y$ est \textbf{une} image de $x$ par la relation $\mathcal{R}$
et que $x$ est \textbf{un} antécédent de $y$. Si $(x,y)\notin G_{%
\mathcal{R}}$, $x$ n'est pas en relation avec $y$.

\begin{remarque}
Le couple $\left( x,y\right) $ de $G_{\mathcal{R}}$ est aussi noté $%
x\mapsto y,$ c'est une notation de la méthode B.
\end{remarque}



\subsection {Retour au CE1}


Reprenons la figure de mon vieux livre de CE1\vpageref{ce1}.



La relation $\RR$ est définie par \og est sur le (la)\fg{}
avec un ensemble de départ qui est en fait l'ensemble des élèves:
$E=\bigl\{a,b,c,d,e,f,g\bigr\}$
 et un ensemble d'arrivée qui est en fait l'ensemble des
jeux:
$J=\bigl\{T,M,B\bigr\}$


Son graphe est:

$$G_\RR=\bigl\{(a,T),(b,T),(c,M),(d,M),(e,M),(f,B),(g,B)\bigr\}$$

Les écritures suivantes sont équivalentes:

$$(a,T)\in  G_\RR   \Longleftrightarrow  a\  \RR\   T  \Longleftrightarrow
(a,T)\in \RR $$


\begin{idee}
Posons-nous la question \og combien existe-t-il de relations (binaires) de $E$
vers $F$\fg{}? Nous venons de dire que, les ensembles $E$ et $F$ étant pr%
écisés, la relation est déterminée par son graphe qui est
une partie de $E\times F$. Il y a donc autant de relations de $E$ vers $F$
que de parties dans $E\times F$, c'est à dire $2^{|E\times F| }$. 

Si, par exemple $E$ a 106 éléments et $F$ a 8 
éléments, alors il existe $2^{848}$ relations de $E$ vers $F$ or
$%
2^{848}\simeq 2.10^{255}$ et le nombre d'atomes estimé dans tout
l'univers  est $10^{80}$: il  y a  donc pas  mal de  relations possibles
entre les 106 garçons et les 8 filles d'INFO 1...
\end{idee}


\subsection{Domaine, codomaine}

\begin{definition}
  
L'ensemble des éléments de $E$ qui ont au moins une image par $%
\mathcal{R}$ est l'ensemble de définition ou \textbf{domaine} de dé%
finition de la relation $\mathcal{R}$ que l'on note le plus souvent par $%
\mathcal{D}_{\mathcal{R}}$ ou $\limfunc{dom}(\mathcal{R})$. Remarquons que l'on
a forcément $\limfunc{dom}\left( \mathcal{R}\right) \subseteq E.$%
$$
\limfunc{dom}\left( \mathcal{R}\right) =\left\{ x\in E\mid \text{il existe
au moins }y\in F\text{ avec }x\mathcal{R}y\right\}
$$
Si on est s\^{u}r que $\limfunc{dom}\left( \mathcal{R}\right) =E,$ c'est-%
à-dire que tout élément de l'ensemble de départ a au moins
une image, on dit que la relation $\mathcal{R}$ est \textbf{totale}
\end{definition}


\begin{definition}
  
L'ensemble des éléments de $F$ qui ont au moins un antécé%
dent dans $E$ est appelé l'image de $\mathcal{R}$ ou l'image de $E$ par $%
\mathcal{R}$ ou le \textbf{codomaine} de $\mathcal{R}$. On utilise indiff%
éremment les notations suivantes pour désigner le codomaine de $%
\mathcal{R}$%

$$
\limfunc{Im}\mathcal{R}\text{ ou }\limfunc{Im}(\mathcal{R})\text{ ou }\limfunc{Ran}(%
\mathcal{R})\text{ ou }\limfunc{codom}\left( \mathcal{R}\right)
$$
\end{definition}



$\limfunc{Im}\left( \mathcal{R}\right) $ se lit \og im de $\mathcal{R}$\fg{} ou
\og image de $\mathcal{R}$\fg{}, la notation $\limfunc{Ran}\left( \mathcal{R}\right) 
$ venant de l'anglais \og range\fg{} (cible en fran\c{c}ais). Il faut tout de
suite remarquer que $\limfunc{Im}(\mathcal{R})$ n'est autre que l'ensemble de
toutes les images des éléments de $E$ par la relation $\mathcal{R}$ 
$$
\limfunc{Im}(\mathcal{R})=\left\{ y\in F\mid \text{il exite au moins }x\in E%
\text{ avec }x\mathcal{R}y\right\}
$$
et que l'on a forcément $\limfunc{Im}(\mathcal{R})\subseteq F$.





\subsection{Représentation d'une relation}


Lorsque $E$ et $F$ sont finis on a forcément $G_{\mathcal{R}}\subseteq
E\times F$ qui est fini et on peut représenter la relation $\mathcal{R}$
ou  son  graphe  $G_{\mathcal{R}}$  de différentes  manières.  En  voici
quelques exemples.


\subsubsection{Représentation linéaire ensembliste}



Prenons pour $E=\left\{ a,b,c,d,e\right\} ,$ $F=\left\{ \alpha ,\beta
,\gamma ,\delta \right\} $ et pour graphe:
$$
G_{\mathcal{R}}=\left\{ \left( a,\gamma \right) ,\left( b,\beta \right)
,\left( b,\delta \right) ,\left( d,\gamma \right) ,\left( e,\delta \right)
\right\}
$$


$G_{\mathcal{R}}$ est aussi noté 
$
G_{\mathcal{R}}=\left\{ a\mapsto \gamma ,b\mapsto \beta ,b\mapsto \delta
,d\mapsto \gamma ,e\mapsto \delta \right\}
$.





Le domaine de $\mathcal{R}$ est $\limfunc{dom}\left( \mathcal{R}\right)
=\left\{ a,b,d,e\right\} ,$ c'est l'ensemble constitué des élé%
ments de $E$ qui ont au moins une image dans $F.$ Le codomaine de $\mathcal{R%
}$ est $\limfunc{codom}\left( \mathcal{R}\right) =\left\{ \beta ,\gamma
,\delta \right\} ,$ c'est l'ensemble constitué des éléments de $%
F $ qui ont au moins un antécédent ou encore l'ensemble des images
des éléments de $E$ par $\mathcal{R}$.%






\subsubsection{Représentation sagittale}

Les ensembles $E$ et $F$
sont représentés par des \og patates\fg{} et un élément $x$ de $E$
(un point de la patate $E)$ est relié à un élément $y$ de $F$
par une flèche orientée de $E$ vers $F$ si, et seulemnt si, $x%
\mathcal{R}y.$


\pgfdeclarelayer{background}
\pgfsetlayers{background,main}

\begin{figure}
\begin{center}
\begin{tikzpicture}[ every fit/.style={ellipse,draw,thick},] 
\SetGraphUnit{0.75cm} 
\SetGraphUnit{0.75cm}
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] 

\tikzset{VertexStyle/.style= {shape= circle,
                             shading= ball,
                             ball color= gray!10,
                             minimum size= 15pt,
                             draw}}
\tikzstyle{EdgeStyle}=[->]
\Vertices[dir=\SO]{line}{a,b,d,e}
{\SetVertexNoLabel
\Vertices[empty,x=3,y=0,dir=\SO]{line}{be,ga,de} }
\foreach \v/\n in {be/\beta,ga/\gamma,de/\delta}{%
\Vertex[Node,L=$\n$]{\v}}   
\Edge(a)(ga)
\Edge(b)(be)
\Edge(b)(de)
\Edge(d)(ga)
\Edge(e)(de) 


\SetGraphUnit{1.5cm} 
\SO(e){c}
\SO[L=$\alpha$](de){al}


\begin{pgfonlayer}{background} 
\node[draw=blue,fill=blue!20,inner sep=1.5pt,fit=(a) (b) (d) (e) ] {};
\node[color=red,fill=red!20,inner  sep=2pt,fit=(be) (ga) (de)]{};
\node[inner sep=6pt,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\node[inner sep=6pt,fit=(al) (be) (ga) (de),pin={[pin edge={thick}]F}] {};
\end{pgfonlayer}

\end{tikzpicture}
\end{center}
\caption{Relation non totale}
\end{figure}

Cette relation n'est pas totale car il y a au moins un élément de
l'ensemble de départ $E$ qui n'a pas d'image, en l'occurence $c$ n'a pas
d'image. 

On visualise immédiatement $\limfunc{dom}\left( \mathcal{R}%
\right) =\left\{ a,b,d,e\right\} $ et $\limfunc{Im}\left( \mathcal{R}\right) =%
\limfunc{codom}\left( \mathcal{R}\right) =\limfunc{Ran}\left( \mathcal{R}%
\right) =\left\{ \beta ,\gamma ,\delta \right\} .$

\subsubsection{Table relationnelle}


C'est la même chose sous forme de tableau:

\begin{center}
             \begin{tabularx}{0.15\linewidth}{Y{0}}
	     \whline
             De&Vers\\
             \whline
             a & $\gamma$\\
\hline
b & $\beta$\\
\hline
b & $\delta$\\
\hline
d & $\gamma$\\
\hline
e& $\delta$\\
             \whline
             \end{tabularx}
             \end{center}


\subsubsection{Dictionnaire}


La même chose en plus ramassé:

\begin{center}
             \begin{tabularx}{0.15\textwidth}{Y{0}}
	     \whline
             De & Vers\\
\whline
 a & $\gamma$\\
\hline
b & $\beta$,$\delta$\\
\hline
d & $\gamma$\\
\hline
e& $\delta$\\

             \whline
             \end{tabularx}
             \end{center}


\subsubsection{Représentation matricielle}



 Si les ensembles $E$ et $%
F $ sont définis par:

$$
E =\left\{ x_{1},x_{2},\cdots ,x_{n}\right\} \qquad F =\left\{ y_{1},y_{2},\cdots ,y_{p}\right\}
$$


alors la relation $\mathcal{R}$ est définie par la matrice\footnote{%
Ceux qui ne savent pas encore ce qu'est une matrice (ce doit être le cas
de la majorité d'entre vous) le découvriront avec le module Algè%
bre et Analyse 1, il suffit de savoir ici qu'une matrice est tout simplement
un tableau de \og nombres\fg{}.} $R=(r_{i,j})\in \mathfrak{M}_{n,p}$ définie par:
$$
R=\left( 
\begin{array}{cccccc}
r_{1,1} & \cdots & r_{1,j} & \cdots & \cdots & r_{1,p} \\ 
\vdots &  & \vdots &  &  & \vdots \\ 
r_{i,1} &  & r_{i,j} &  &  & r_{i,p} \\ 
\vdots &  & \vdots &  &  & \vdots \\ 
r_{n,1} & \cdots & r_{n,j} & \cdots & \cdots & r_{n,p}%
\end{array}%
\right) \text{ avec }r_{i,j}=\left\{ 
\begin{array}{l}
1\text{ si }x_{i}\mathcal{R}y_{j} \\ 
0\text{ sinon}%
\end{array}%
\right.
$$

$r_{i,j}$ étant l'élément se trouvant sur la $i^{\grave{e}me}$
ligne et $j^{\grave{e}me}$ colonne$,$ les lignes étant numéroté%
es du haut vers le bas et les colonnes de la gauche vers la droite. La
matrice $R$ est appelée la matrice d'adjacence ou d'incidence de la
relation $\mathcal{R}.$

Si l'on reprend l'exemple précédent, il nous faut décider d'ordonner les éléments de $E$ et de $F$
et, pour s'assurer que celui qui va nous lire ne fera pas de confusions, il
faut s'obliger à faire figurer les éléments à c\^{o}té
de la matrice d'autant plus que certains utilisateurs peuvent très bien d%
écider d'un autre placement pour les éléments de $E$ et de $F$
puisque les éléments de $E$ et de $F$ ne sont pas indicés :%

\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
$\curvearrowright $ & $\alpha $ & $\beta $ & $\gamma $ & $\delta $ \\ \hline
$a$ & \textbf{0} & \textbf{0} & \textbf{1} & \textbf{0} \\ \hline
$b$ & \textbf{0} & \textbf{1} & \textbf{0} & \textbf{1} \\ \hline
$c$ & \textbf{0} & \textbf{0} & \textbf{0} & \textbf{0} \\ \hline
$d$ & \textbf{0} & \textbf{0} & \textbf{1} & \textbf{0} \\ \hline
$e$ & \textbf{0} & \textbf{0} & \textbf{0} & \textbf{1} \\ \hline
\end{tabular}%
\end{center}

Mais bon,  généralement, on place en  ligne les élément de  départ et en
colonne les élément d'arrivée donc on peut se contenter de la matrice:

$$
R=
\begin{pmatrix}
0&0&1&0\\
0&1&0&1\\
0&0&0&0\\
0&0&1&0\\
0&0&0&1\\
\end{pmatrix}
$$

mais il faut être sûr de ce que l'on fait.


\subsubsection{Un exemple de représentation sur \textsc{Caml}}



On crée une relation par listes d'images: une relation binaire est une
liste de paires 

\begin{center}
\texttt{sommets,[liste des images]} 
\end{center}

implémentée à l'aide de notre type \texttt{ens} précédemment étudié.
Les  ensembles d'arrivée  et de  départ  peuvent être  distincts et  les
variables de types \texttt{'a} et \texttt{'b} distincts ou non:
\caml

\begin{lstlisting}[caption={}]
type ('a,'b) relation =
  Rel of ('a * 'b ens)  ens ;;
\end{lstlisting}



Par exemple:

\begin{lstlisting}[caption={}]
let r = Rel( 
  Ens((1, Ens ('a', Ens ('b', Vide))),
     Ens((2, Ens ('c', Vide)),
        Ens((3, Ens ('b', Vide)),
           Ens((4, Vide),
              Ens((5, Ens ('b', Vide)),
                 Vide)))))
);;
\end{lstlisting}

Voyons son type:

\begin{lstlisting}[caption={}]
# r;;

- : (int, char) relation
\end{lstlisting}


\subsection{Relation transposée}

\begin{definition}
La \textbf{relation transposée} de la relation $\mathcal{R}=(E,F,G_{%
\mathcal{R}})$ est la relation notée $\mathcal{R}^{\sim}$ définie par $%
\mathcal{R}^{\sim}=(F,E,G_{\mathcal{R}^{\sim}})$ avec 
$
G_{\mathcal{R}^{\sim}}=\left\{ (y,x)\in F\times E\mid (x,y)\in G_{\mathcal{R}%
}\right\}
$,
c'est-à-dire $y\mathcal{R}^{\sim}x\Leftrightarrow x\mathcal{R}y$.
\end{definition}


 Pour
obtenir la représentation sagittale de $\mathcal{R}^{\sim},$ il suffit de
modifier le sens des flèches de la représentation sagittale de $%
\mathcal{R}$. 

\begin{remarque}

Si $R$ est la matrice de $\mathcal{R}$ alors $^{t}R,$ la
transposée   de   $R,$  est   la   matrice  de   $\mathcal{R}^{\sim}$,
c'est-à-dire  la  matrice  obtenue   en  inversant  les  lignes  et  les
colonnes, ce  qui est assez logique  compte tenu de  notre définition de
la représentation matricielle.%


En reprenant l'exemple précédent:

$$
R=
\begin{pmatrix}
0&0&1&0\\
0&1&0&1\\
0&0&0&0\\
0&0&1&0\\
0&0&0&1\\
\end{pmatrix}
\qquad
\tr R=
\begin{pmatrix}
0&0&0&0&0\\
0&1&0&0&0\\
1&0&0&1&0\\
0&1&0&0&1
\end{pmatrix}
$$
\end{remarque}


Les résultats suivants découlent immédiatement de la dé%
finition : 
\begin{itemize}
\item $\limfunc{dom}\left( \mathcal{R}\right) =\limfunc{Im}(\mathcal{R}^{\sim})$

\item $\limfunc{dom}\left( \mathcal{R}^{\sim}\right) =\limfunc{Im}(\mathcal{R})$

\item $\left( \mathcal{R}^{\sim}\right) ^{\sim} =\mathcal{R}$
\end{itemize}




 Un  petit exemple alors...Considérons les ensembles  et la relation
suivants:
\begin{itemize}
\item Étudiants$=\bigl\{$Roger, Berthe, Jean-Pierre, Gudrun$\bigr\}$;
\item Chaînes$=\bigl\{$ TF1, Gulli, Zen TV$\bigr\}$;
\item  TV$=\bigl\{$Roger   $\mapsto$  Gulli,  Berthe   $\mapsto$  Gulli,
  Jean-Pierre $\mapsto$ Zen TV, Gudrun $\mapsto$ Gulli$\bigr\}$.
\end{itemize}

Ainsi       la       relation       $TV       \in       \text{Étudiants}
\longleftrightarrow\text{Chaîne}$       peut       s'interpréter      en
\og ... regarde ...\fg{}.

Que pensez-vous de la relation réciproque?

\subsection{Image, contre image}

\begin{definition}
  Si $U$ est une partie de $E,$ $\mathcal{R}\left( U\right) $  désigne l'ensemble des images des él%
éments de $U$ par $\mathcal{R}$.
\end{definition}




\begin{remarque}
Si $U$ n'est pas une partie de $E,$ $\mathcal{R}\left( U\right) $ n'a pas de
sens !
\end{remarque}

\begin{definition}
Si $V$ est une partie de $F$, la contre image (ou l'image transposée) de 
$V$ par $\mathcal{R}$ est l'image de $V$ par $\mathcal{R}^{\sim}.$ Elle est
donc notée $\mathcal{R}^{\sim}\left( V\right) $.
\end{definition}


On pourra remarquer que $\mathcal{R%
}^{\sim}\left( F\right) =\limfunc{dom}\mathcal{R}.$

La relation $\mathcal{R}$ définie par son diagramme
sagittal:%

\begin{figure}
\begin{center}
\begin{tikzpicture}[ every fit/.style={ellipse,draw,thick},] 
\SetGraphUnit{0.75cm}  
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] 

\tikzset{VertexStyle/.style= {shape= circle,
                             shading= ball,
                             ball color= gray!10,
                             minimum size= 15pt,
                             draw}}
\tikzstyle{EdgeStyle}=[->]
\Vertices[dir=\SO]{line}{a,b,d,e}
{\SetVertexNoLabel
\Vertices[empty,x=3,y=0,dir=\SO]{line}{be,ga,de} }
\foreach \v/\n in {be/\beta,ga/\gamma,de/\delta}{%
\Vertex[Node,L=$\n$]{\v}}   
\Edge(a)(ga)
\Edge(b)(be)
\Edge(b)(de)
\Edge(d)(ga)
\Edge(e)(de) 


\SetGraphUnit{1.5cm} 
\SO(e){c}
\SO[L=$\alpha$](de){al}


\begin{pgfonlayer}{background} 
\node[draw=blue,fill=blue!20,inner sep=1.5pt,fit=(a) (b) (d) (e) ] {};
\node[color=red,fill=red!20,inner  sep=2pt,fit=(be) (ga) (de)]{};
\node[inner sep=6pt,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\node[inner sep=6pt,fit=(al) (be) (ga) (de),pin={[pin edge={thick}]F}] {};
\end{pgfonlayer}

\end{tikzpicture}
\end{center}
\caption{Image et contre-image}
\end{figure}

Nous avons $\mathcal{R}\left( \left\{ a,b\right\} \right)
=\left\{ \beta ,\gamma \right\} ,\mathcal{R}\left( \bigl\{ c\bigr\} \right)
=\left\{ \gamma \right\} ,\mathcal{R}^{\sim}\left( \bigl\{ \alpha \bigr\}
\right) =\{\}  ,\mathcal{R}^{\sim}\left( \left\{ \gamma \right\} \right)
=\left\{ a,c,d\right\} $ mais aussi $\mathcal{R}\left( \{\}  \right)
=\{\}  $ et $\mathcal{R}\left( \left\{ a,\beta \right\} \right) $ n'a
pas de sens car $\left\{ a,\beta \right\} $ n'est pas une partie de
l'ensemble de départ de $\mathcal{R}.$


 Allez, vous voulez reprendre un exemple...

Qui      regarde      Gulli?      Il     faut      définir      $TV^{\sim}
\left(\bigl\{\text{Gulli}\bigr\}\right)$.




\subsection{égalité de deux relations}


\begin{definition}
Les relations $\mathcal{R}_{1}=(E_{1},F_{1},G_{\mathcal{R}_{1}})$ et $%
\mathcal{R}_{2}=(E_{2},F_{2},G_{\mathcal{R}_{2}})$ sont égales si, et
seulement si, $E_{1}=E_{2}$ \textbf{et} $F_{1}=F_{2}$ \textbf{et} $G_{%
\mathcal{R}_{1}}=G_{\mathcal{R}_{2}}.$
\end{definition}


 Vous êtes priés de ne pas
modifier cette définition en fonction des circonstances. Il faut
comprendre que les relations: 
$$
\mathcal{R}=(E,F,G_{\mathcal{R}})\text{ et }\mathcal{R}_{1}=(\limfunc{dom}%
\left( \mathcal{R}\right) ,\limfunc{Im}(\mathcal{R}),G_{\mathcal{R}})
$$


ne sont pas forcément égales même si on a l'impression que
\og c'est pareil\fg{}. Tout ce que l'on peut dire c'est qu'elles ont le même
graphe et c'est déjà beaucoup. Imaginons que $E$ et $F$ soient deux
fichiers \textit{informatiques } et que $G_{\mathcal{R}}$ nous donne les
couples de fiches correspondant à une certaine requête (relation).
Ce n'est pas parce que certaines fiches (éléments des fichiers) ne
seront pas utilisées que vous devez les ignorer ou les faire dispara%
\^{\i}tre des fichiers !







\subsection{Principales opérations sur les relations}





Une relation $\mathcal{R}$ de $E$ vers $F$ étant assimilée à un
ensemble, une partie de $E\times F,$ on est naturellement amené à
utiliser les opérations ensemblistes élémentaires.

Dans ce qui suit $\mathcal{R}_{1}=\left( E,F,G_{\mathcal{R}_{1}}\right) $ et 
$\mathcal{R}_{2}=\left( E,F,G_{\mathcal{R}_{2}}\right) $ sont deux relations
de  $E$ vers  $F$  et  $R_{1}$ et  $R_{2}$  sont, respectivement,  leurs
matrices.



\subsubsection{Négation}

\begin{definition}
La \textbf{négation} de $\mathcal{R}_{1}$ (on dit aussi le compl%
émentaire de $\mathcal{R}_{1}$) est la relation: 
$$
\overline{\mathcal{R}_{1}}=\left( E,F,\complement_{E\times F}G_{%
\mathcal{R}_{1}}\right)
$$
\end{definition}

Cela signifie tout simplement que $x\overline{\mathcal{R}_{1}}y$ si, et
seulement si, $\left( x,y\right) \notin G_{\mathcal{R}_{1}}$ ou encore que $%
x $ n'est pas en relation avec $y$ par $\mathcal{R}_{1}$. 

La relation $%
\overline{\mathcal{R}_{1}}$ est aussi notée $\lnot \mathcal{R}_{1}.$ 

 Par exemple en reprenant la relation TV, Berthe $\overline{TV}$ TF1: Berthe ne regarde pas TF1.


 La
matrice booléenne de $\overline{\mathcal{R}_{1}}$ s'obtient en rempla%
\c{c}ant dans la matrice booléenne de $\mathcal{R}_{1}$ les \og 0\fg{} par des
\og 1\fg{} et les \og 1\fg{} par des \og 0\fg{}. Cela revient à calculer $R_1\oplus \text{Attila}(|E|,|F|)$.




\subsubsection{Inclusion}


\begin{definition}
On dit que la relation $\mathcal{R}_{1}$ est incluse dans la relation $%
\mathcal{R}_{2}$ ou que la relation $\mathcal{R}_{1}$ est une \textbf{sous
relation} de la relation $\mathcal{R}_{2}$ si, et seulement si, $G_{\mathcal{%
R}_{1}}\subseteq G_{\mathcal{R}_{2}}.$ Cela signifie que 
$$
x\mathcal{R}_{1}y\Rightarrow x\mathcal{R}_{2}y
$$
et on écrit alors $\mathcal{R}_{1}\subseteq \mathcal{R}_{2}$.
\end{definition}


Visuellement, une sous relation est obtenue en \og supprimant\fg{} des fl%
èches :%





\begin{minipage}[t]{0.5\linewidth}
\begin{figure}
\begin{center}
\begin{tikzpicture}[ every fit/.style={ellipse,draw,thick},] 
\SetGraphUnit{0.75cm}  
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] 

\tikzset{VertexStyle/.style= {shape= circle,
                             shading= ball,
                             ball color= gray!10,
                             minimum size= 15pt,
                             draw}}
\tikzstyle{EdgeStyle}=[->]
\Vertices[dir=\SO]{line}{a,b,c,d,e}
{\SetVertexNoLabel
\Vertices[empty,x=3,y=0,dir=\SO]{line}{al,be,ga,de} }
\foreach \v/\n in {al/\alpha,be/\beta,ga/\gamma,de/\delta}{%
\Vertex[Node,L=$\n$]{\v}}   
\Edge(a)(be)
\Edge(a)(ga)
\Edge(c)(ga)
\Edge(d)(ga)
\Edge(d)(de)
\Edge(e)(de)
\begin{pgfonlayer}{background}
% \node[draw=blue,fill=blue!20,inner sep=1.5pt,thick,ellipse,fit=(a) (b) (d) (e)] {};
% \node[draw=red,fill=red!20,inner  sep=2pt,thick,ellipse,fit=(be) (ga) (de)]{};
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(al) (be) (ga) (de),pin={[pin edge={thick}]F}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{$\RR_1$}
\end{figure}
\end{minipage}\hspace{0.5cm}
\begin{minipage}[t]{0.5\linewidth}%\vspace{-0.5cm}
\hspace{5.5cm} 
\begin{flushright}
\begin{figure}
\begin{center}
\begin{tikzpicture}[ every fit/.style={ellipse,draw,thick},] 
\SetGraphUnit{0.75cm}  
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] 

\tikzset{VertexStyle/.style= {shape= circle,
                             shading= ball,
                             ball color= gray!10,
                             minimum size= 15pt,
                             draw}}
\tikzstyle{EdgeStyle}=[->]
\Vertices[dir=\SO]{line}{a,b,c,d,e}
{\SetVertexNoLabel
\Vertices[empty,x=3,y=0,dir=\SO]{line}{al,be,ga,de} }
\foreach \v/\n in {al/\alpha,be/\beta,ga/\gamma,de/\delta}{%
\Vertex[Node,L=$\n$]{\v}}   
\Edge(a)(be)
%\Edge(a)(ga)
\Edge(c)(ga)
%\Edge(d)(ga)
%\Edge(d)(de)
\Edge(e)(de)
\begin{pgfonlayer}{background}
% \node[draw=blue,fill=blue!20,inner sep=1.5pt,thick,ellipse,fit=(a) (b) (d) (e)] {};
% \node[draw=red,fill=red!20,inner  sep=2pt,thick,ellipse,fit=(be) (ga) (de)]{};
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(al) (be) (ga) (de),pin={[pin edge={thick}]F}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{$\RR_2$ est une sous-relation de $\RR_1$}
\end{figure}
\end{flushright}
\end{minipage}


 Pour être plus concret, modifions un peu notre exemple télévisuel en supposant
qu'on peut maintenant regarder plusieurs chaînes de télévision. 

Par exemple, posons à présent TV2$=\bigl\{$Roger $\mapsto$ Gulli, Berthe $\mapsto$ Gulli,
Berthe $\mapsto$ Zen TV,
  Jean-Pierre $\mapsto$ Zen TV, Gudrun $\mapsto$ Gulli, Gudrun $\mapsto$
  TF1, Gudrun $\mapsto$ Zen TV$\bigr\}$.

Alors $TV\subseteq TV2$. 




Matriciellement cela se traduit par le fait que tous les \og $1$\fg{} de la matrice 
$R_{1}$ sont aussi des \og 1\fg{} de la matrice $R_{2}$ ce qui donne, en utilisant
le calcul booléen $\left( 1\veebar1=1\right) $ :%
$$
\mathcal{R}_{1}\subseteq \mathcal{R}_{2}\Leftrightarrow R_{1}\veebar R_{2}=R_{2}
$$


\begin{notation}[Méthode B]
Voici les notations utilisées en méthode B, $\mathcal{R}$ dé%
signant une relation de $E$ vers $F$. 

\textbf{Obligatoirement }$A\subseteq E$ \textbf{et} $B\subseteq F$.

\begin{itemize}
\item \textit{La relation }$\left( E,F,G_{\mathcal{R}}\cap \left( A\times
F\right) \right) $\textit{\ est notée }$A\vartriangleleft \mathcal{R},$%
\textit{\ c'est une sous relation de }$\mathcal{R}$\textit{\ et les
informaticiens parlent de \og restriction de domaine\fg{}.}

\item \textit{La relation }$(E,F,G_{\mathcal{R}}\cap (E\times B))$\textit{\
est notée }$\mathcal{R}\vartriangleright B,$\textit{\ c'est une sous
relation de }$\mathcal{R}$\textit{et les informaticiens parlent de
\og restriction de codomaine\fg{}.}

\item \textit{La relation }$\left( E,F,G_{\mathcal{R}}\cap \left( A\times
B\right) \right) $\textit{\ est notée }$A\vartriangleleft \mathcal{R}%
\vartriangleright B$\textit{, c'est une sous relation de }$\mathcal{R}\ $%
\textit{et les informaticiens parlent de \og restriction de domaine et de
codomaine\fg{}.}
\end{itemize}
\end{notation}


\subsubsection{Réunion et intersection}


\begin{definition}
 La \textbf{réunion} de $\mathcal{R}_{1}$ et de $\mathcal{R}%
_{2}$ est la relation $\mathcal{R}_{1}\cup \mathcal{R}_{2}=\left( E,F,G_{%
\mathcal{R}_{1}}\cup G_{\mathcal{R}_{2}}\right) .$

 L'\textbf{intersection} de $\mathcal{R}_{1}$ et de $\mathcal{R}%
_{2}$ est la relation $\mathcal{R}_{1}\cap \mathcal{R}_{2}=\left( E,F,G_{%
\mathcal{R}_{1}}\cap G_{\mathcal{R}_{2}}\right) .$
\end{definition}

Cela revient en fait à ajouter ou à enlever des flèches.

\begin{DANGER}
On notera bien que l'on ne peut comparer ou faire l'union ou l'intersection
de deux relations qu'à la condition qu'elles aient le même ensemble
de départ et le même ensemble d'arrivée.
\end{DANGER}



La matrice booléenne
de $\mathcal{R}_{1}\cup \mathcal{R}_{2}$ est $R_{1}\veebar R_{2}.$

 La matrice booléeen
de $\mathcal{R}_{1}\cap \mathcal{R}_{2}$ s'obtient \og en ne gardant que les 1
qui ont la même place\fg{} dans $R_{1}$ et $R_{2}$. On va donc effectuer $E_1\barwedge E_2$.




Rien  ne vaut  un bon  exemple...Considérons deux  relations  $\RR_1$ et
$\RR_2$:





\begin{minipage}[t]{0.5\linewidth}
\begin{figure}
\begin{center}
\begin{tikzpicture}[ every fit/.style={ellipse,draw,thick},] 
\SetGraphUnit{0.75cm}  
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] 

\tikzset{VertexStyle/.style= {shape= circle,
                             shading= ball,
                             ball color= gray!10,
                             minimum size= 15pt,
                             draw}}
\tikzstyle{EdgeStyle}=[->]
\Vertices[dir=\SO]{line}{a,b,c,d,e}
{\SetVertexNoLabel
\Vertices[empty,x=3,y=0,dir=\SO]{line}{al,be,ga,de} }
\foreach \v/\n in {al/\alpha,be/\beta,ga/\gamma,de/\delta}{%
\Vertex[Node,L=$\n$]{\v}}   
\Edge(a)(be)
\Edge(a)(ga)
%\Edge(c)(ga)
\Edge(d)(ga)
%\Edge(d)(de)
\Edge(e)(de)
\begin{pgfonlayer}{background}
% \node[draw=blue,fill=blue!20,inner sep=1.5pt,thick,ellipse,fit=(a) (b) (d) (e)] {};
% \node[draw=red,fill=red!20,inner  sep=2pt,thick,ellipse,fit=(be) (ga) (de)]{};
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(al) (be) (ga) (de),pin={[pin edge={thick}]F}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{$\RR_1$}
\end{figure}
\end{minipage}\hspace{0.5cm}
\begin{minipage}[t]{0.5\linewidth}%\vspace{-0.5cm}
\hspace{5.5cm} 
\begin{flushright}
\begin{figure}
\begin{center}
\begin{tikzpicture}[ every fit/.style={ellipse,draw,thick},] 
\SetGraphUnit{0.75cm}  
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] 

\tikzset{VertexStyle/.style= {shape= circle,
                             shading= ball,
                             ball color= gray!10,
                             minimum size= 15pt,
                             draw}}
\tikzstyle{EdgeStyle}=[->]
\Vertices[dir=\SO]{line}{a,b,c,d,e}
{\SetVertexNoLabel
\Vertices[empty,x=3,y=0,dir=\SO]{line}{al,be,ga,de} }
\foreach \v/\n in {al/\alpha,be/\beta,ga/\gamma,de/\delta}{%
\Vertex[Node,L=$\n$]{\v}}   
\Edge(a)(be)
\Edge(a)(de)
\Edge(c)(de)
%\Edge(d)(ga)
%\Edge(d)(de)
\Edge(d)(ga)
\begin{pgfonlayer}{background}
% \node[draw=blue,fill=blue!20,inner sep=1.5pt,thick,ellipse,fit=(a) (b) (d) (e)] {};
% \node[draw=red,fill=red!20,inner  sep=2pt,thick,ellipse,fit=(be) (ga) (de)]{};
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(al) (be) (ga) (de),pin={[pin edge={thick}]F}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{$\RR_2$}
\end{figure}
\end{flushright}
\end{minipage}

On remarque qu'aucune n'est incluse dans l'autre et on obtient:%




















\begin{minipage}[t]{0.3\linewidth}
\begin{figure}
\begin{center}
\begin{tikzpicture}[ every fit/.style={ellipse,draw,thick},] 
\SetGraphUnit{0.75cm}  
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] 

\tikzset{VertexStyle/.style= {shape= circle,
                             shading= ball,
                             ball color= gray!10,
                             minimum size= 15pt,
                             draw}}
\tikzstyle{EdgeStyle}=[->]
\Vertices[dir=\SO]{line}{a,b,c,d,e}
{\SetVertexNoLabel
\Vertices[empty,x=3,y=0,dir=\SO]{line}{al,be,ga,de} }
\foreach \v/\n in {al/\alpha,be/\beta,ga/\gamma,de/\delta}{%
\Vertex[Node,L=$\n$]{\v}}   
\Edge(a)(al)
\Edge(a)(de)
\Edge(b)(al)
\Edge(b)(be)
\Edge(b)(ga)
\Edge(b)(de)
\Edge(c)(al)
\Edge(c)(be)
\Edge(c)(ga)
\Edge(c)(de)
\Edge(d)(al)
\Edge(d)(be)
\Edge(d)(de)
\Edge(e)(al)
\Edge(e)(be)
\Edge(e)(ga)
\begin{pgfonlayer}{background}
% \node[draw=blue,fill=blue!20,inner sep=1.5pt,thick,ellipse,fit=(a) (b) (d) (e)] {};
% \node[draw=red,fill=red!20,inner  sep=2pt,thick,ellipse,fit=(be) (ga) (de)]{};
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(al) (be) (ga) (de),pin={[pin edge={thick}]F}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{$\overline{\RR_1}$}
\end{figure}
\end{minipage}\hspace{0.5cm}
\begin{minipage}[t]{0.3\linewidth}%\vspace{-0.5cm}
\hspace{5.5cm} 
\begin{flushright}
\begin{figure}
\begin{center}
\begin{tikzpicture}[ every fit/.style={ellipse,draw,thick},] 
\SetGraphUnit{0.75cm}  
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] 

\tikzset{VertexStyle/.style= {shape= circle,
                             shading= ball,
                             ball color= gray!10,
                             minimum size= 15pt,
                             draw}}
\tikzstyle{EdgeStyle}=[->]
\Vertices[dir=\SO]{line}{a,b,c,d,e}
{\SetVertexNoLabel
\Vertices[empty,x=3,y=0,dir=\SO]{line}{al,be,ga,de} }
\foreach \v/\n in {al/\alpha,be/\beta,ga/\gamma,de/\delta}{%
\Vertex[Node,L=$\n$]{\v}}   
\Edge(a)(be)
\Edge(a)(ga)
%\Edge(c)(ga)
\Edge(d)(ga)
%\Edge(d)(de)
\Edge(e)(de)
%\Edge(a)(be)
\Edge(a)(de)
\Edge(c)(de)
%\Edge(d)(ga)
%\Edge(d)(de)
%\Edge(d)(ga)
\begin{pgfonlayer}{background}
% \node[draw=blue,fill=blue!20,inner sep=1.5pt,thick,ellipse,fit=(a) (b) (d) (e)] {};
% \node[draw=red,fill=red!20,inner  sep=2pt,thick,ellipse,fit=(be) (ga) (de)]{};
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(al) (be) (ga) (de),pin={[pin edge={thick}]F}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{$\RR_{1}\cup\RR_2$}
\end{figure}
\end{flushright}
\end{minipage}\hspace{0.5cm}
\begin{minipage}[t]{0.3\linewidth}%\vspace{-0.5cm}
\hspace{5.5cm} 
\begin{flushright}
\begin{figure}
\begin{center}
\begin{tikzpicture}[ every fit/.style={ellipse,draw,thick},] 
\SetGraphUnit{0.75cm}  
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] 

\tikzset{VertexStyle/.style= {shape= circle,
                             shading= ball,
                             ball color= gray!10,
                             minimum size= 15pt,
                             draw}}
\tikzstyle{EdgeStyle}=[->]
\Vertices[dir=\SO]{line}{a,b,c,d,e}
{\SetVertexNoLabel
\Vertices[empty,x=3,y=0,dir=\SO]{line}{al,be,ga,de} }
\foreach \v/\n in {al/\alpha,be/\beta,ga/\gamma,de/\delta}{%
\Vertex[Node,L=$\n$]{\v}}   
\Edge(a)(be)
%\Edge(a)(ga)
%\Edge(c)(ga)
\Edge(d)(ga)
%\Edge(d)(de)
%\Edge(e)(de)
\begin{pgfonlayer}{background}
% \node[draw=blue,fill=blue!20,inner sep=1.5pt,thick,ellipse,fit=(a) (b) (d) (e)] {};
% \node[draw=red,fill=red!20,inner  sep=2pt,thick,ellipse,fit=(be) (ga) (de)]{};
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(al) (be) (ga) (de),pin={[pin edge={thick}]F}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{$\RR_1\cap\RR_2$}
\end{figure}
\end{flushright}
\end{minipage}



  Rallumons la  télé  mais  cette fois  en  distinguant les  chaînes
regardées le midi de celles regardées le soir:

TVmidi$=\bigl\{$Roger $\mapsto$ Gulli, Berthe $\mapsto$ Gulli,
Berthe $\mapsto$ Zen TV, Jean-Pierre $\mapsto$ Zen TV, Gudrun $\mapsto$ Gulli, Gudrun $\mapsto$
  TF1, Gudrun $\mapsto$ Zen TV$\bigr\}$.

TVsoir=$=\bigl\{$Roger $\mapsto$ TF1, Berthe $\mapsto$ Gulli,
Berthe $\mapsto$ TF1,
  Jean-Pierre $\mapsto$ TF1, Gudrun $\mapsto$ Gulli, Gudrun $\mapsto$
  TF1$\bigr\}$.


Comment  décririez-vous les  relations  TVmidi $\cap$  TVsoir et  TVmidi
$\cup$ TVsoir?

\subsection{Composition de relations}






\begin{definition}
$\mathcal{R}=(E,F,G_{\mathcal{R}})$ et $\mathcal{S}=(U,V,G_{\mathcal{S}})$
sont deux relations. 

La \textbf{composition} (ou la composée) de $%
\mathcal{R}$ par $\mathcal{S}$ (attention à l'ordre) \textbf{ne peut se
faire que si} $F=U$ ou, si l'on préfère, que si l'ensemble d'arriv%
ée de $\mathcal{R}$ est égal à l'ensemble de départ de $%
\mathcal{S}$. 


Dans ce cas la composée de $\mathcal{R}$ par $\mathcal{S}$
est la relation notée $\mathcal{S}\circ \mathcal{R}$ qui a pour ensemble
de départ $E$ (l'ensemble de départ de $\mathcal{R}$), pour ensemble
d'arrivée $V$ (l'ensemble d'arrivée de $\mathcal{S}$) et pour graphe 

$$G_{\mathcal{S}\circ \mathcal{R}}=\left\{\left(
x,z\right)  \in  E\times V\mid\exists  y\in  F,\  \left( x,y\right)  \in
G_{\mathcal{R}} \land \left(
y,z\right) \in G_{\mathcal{S}}\right\}$$
\end{definition}


Pour simplifier les choses, $\mathcal{S}\circ \mathcal{R}$ est aussi notée $\mathcal{R}\mathbf{.}%
\mathcal{S}$ ou bien encore $\mathcal{R};\mathcal{S}$ (attention à
l'ordre!). En effet, si $x\mathcal{R}y$ et $y\mathcal{S}z$ il est plus
\og naturel\fg{}  d'écrire $x\mathcal{R}.\mathcal{S}z$.


Le mieux est encore d'analyser un exemple:





\begin{minipage}[t]{0.3\linewidth}
\begin{figure}
\begin{center}
\begin{tikzpicture}[ every fit/.style={ellipse,draw,thick}] 
\SetGraphUnit{.75cm}  
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] 

\tikzset{VertexStyle/.style= {shape= circle,
                             shading= ball,
                             ball color= gray!10,
                             minimum size= 15pt,
                             draw}}
\tikzstyle{EdgeStyle}=[->]
{\SetVertexNoLabel
\Vertices[empty,x=0,y=0,dir=\SO]{line}{a,b,c,d,e} }
\foreach \v in {a,b,c,d,e}{%
\Vertex[Node]{\v}}   
{\SetVertexNoLabel
\Vertices[empty,x=3,y=0,dir=\SO]{line}{al,be,ga,de} }
\foreach \v/\n in {al/\alpha,be/\beta,ga/\gamma,de/\delta}{%
\Vertex[Node,L=$\n$]{\v}}   
\Edge(a)(be)
\Edge(a)(ga)
\Edge(c)(ga)
\Edge(d)(ga)
\Edge(d)(de)
\Edge(e)(de)
\begin{pgfonlayer}{background}
\node[draw=blue,fill=blue!20,inner sep=4pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\node[draw=black,fill=green!10,inner sep=4pt,thick,ellipse,fit=(al) (be) (ga) (de),pin={[pin edge={thick}]F=U}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{$\RR$}
\end{figure}
\end{minipage}\hspace{0.5cm}
\begin{minipage}[t]{0.3\linewidth}%\vspace{-0.5cm}
\hspace{5.5cm} 
\begin{flushright}
\begin{figure}
\begin{center}
\begin{tikzpicture}[ every fit/.style={ellipse,draw,thick}] 
\SetGraphUnit{.75cm}  
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] 

\tikzset{VertexStyle/.style= {shape= circle,
                             shading= ball,
                             ball color= gray!10,
                             minimum size= 15pt,
                             draw}}
\tikzstyle{EdgeStyle}=[->]
{\SetVertexNoLabel
\Vertices[empty,x=3,y=0,dir=\SO]{line}{1,2,3,4,5} }
\foreach \v in {1,2,3,4,5}{%
\Vertex[Node]{\v}}   
{\SetVertexNoLabel
\Vertices[empty,x=0,y=0,dir=\SO]{line}{al,be,ga,de} }
\foreach \v/\n in {al/\alpha,be/\beta,ga/\gamma,de/\delta}{%
\Vertex[Node,L=$\n$]{\v}}   
\Edge(be)(2)
\Edge(be)(4)
\Edge(ga)(5)
\begin{pgfonlayer}{background}
\node[draw=red,fill=red!20,,inner sep=4pt,thick,ellipse,fit=(1) (2) (3) (4) (5),pin={[pin edge={thick}]V}] {};
\node[draw=black,fill=green!10,inner sep=4pt,thick,ellipse,fit=(al) (be) (ga) (de),pin={[pin edge={thick}]U=F}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{$\SR$}
\end{figure}
\end{flushright}
\end{minipage}\hspace{0.5cm}
\begin{minipage}[t]{0.3\linewidth}%\vspace{-0.5cm}
\hspace{5.5cm} 
\begin{flushright}
\begin{figure}
\begin{center}
\begin{tikzpicture}[ every fit/.style={ellipse,draw,thick}] 
\SetGraphUnit{.75cm}  
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] 

\tikzset{VertexStyle/.style= {shape= circle,
                             shading= ball,
                             ball color= gray!10,
                             minimum size= 15pt,
                             draw}}
\tikzstyle{EdgeStyle}=[->]
{\SetVertexNoLabel
\Vertices[empty,x=0,y=0,dir=\SO]{line}{a,b,c,d,e} }
\foreach \v in {a,b,c,d,e}{%
\Vertex[Node]{\v}}   
{\SetVertexNoLabel
\Vertices[empty,x=3,y=0,dir=\SO]{line}{al,be,ga,de,ep} }
\foreach \v/\n in {al/1,be/2,ga/3,de/4,ep/5}{%
\Vertex[Node,L=$\n$]{\v}}   
\Edge(a)(be)
\Edge(a)(de)
\Edge(a)(ep)
\Edge(c)(ep)
\Edge(d)(ep)
\begin{pgfonlayer}{background}
\node[draw=blue,fill=blue!20,inner sep=4pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\node[draw=red,fill=red!20,inner sep=4pt,thick,ellipse,fit=(al) (be) (ga) (de) (ep),pin={[pin edge={thick}]V}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{$\SR \circ \RR$}
\end{figure}
\end{flushright}
\end{minipage}


\begin{recherche}
  Si  $R$  est  la  matrice  de  $\mathcal{R}$  et  $S$  la  matrice  de
  $\mathcal{S}$ alors quelle sera la matrice de $R\ ;\ S$?
\end{recherche}


\begin{recherche}
  Que pensez de  $\RR^{\sim}\circ \RR$ ou de $\RR  \circ \RR^{\sim}$? Regardez
ce que cela donne avec la relation $\RR$ introduite précédemment.

Quelle est la relation transposée de $\mathcal{S\circ R}$
\end{recherche}


Un exemple? Allez,  on va changer un  peu. Cette fois  considérons des animaux,
leurs petits noms et leurs cris:


\begin{itemize}
\item   Baptême=$\bigl\{$            alouette$\mapsto$Josette,
  alouette$\mapsto$Pépette,                     albatros$\mapsto$Bernard,
  bécasse$\mapsto$Germaine$\bigr\}$;
\item   Cri=$\bigl\{$Josette$\mapsto$turlute,   Josette$\mapsto$grisole,
  Pépette$\mapsto$turlute, Bernard$\mapsto$piaule, Germaine$\mapsto$croule$\bigr\}$
\end{itemize}

Quelle est la tête de Baptême $\ ; \ $ Cri et comment l'interpréter?

\section{Fonctions}

\subsection{Définitions}

\begin{definition}
On dit que \textbf{la relation} $f=(E,F,G_{f})$ est une \textbf{fonction}
(ou une dépendance fonctionnelle) de $E$ vers (ou dans) $F$ si, et
seulement si, tout élément de $E$ a \textbf{au plus} (cela veut dire
: soit zéro ou une) une image dans $F$. 
\end{definition}


 Cela signifie aussi que si $x$
est un élément quelconque de $E,$ $f\left( \left\{ x\right\} \right) 
$ est soit l'ensemble vide soit un singleton. Si $x$ a au moins une image,
c'est-à-dire s'il existe $y\in F$ tel que $\left( x,y\right) \in G_{f},$ 
$y$ est forcément unique et est noté $f(x).$ Lorsque la relation $%
f=(E,F,G_{f})$ est une fonction on préfère le plus souvent utiliser
la notation:
$$
 f\colon \begin{array}{rll} E & \to & F\\
   x & \mapsto & f(x)=y
 \end{array}
 $$

qui se lit \og $f$ est une fonction de $E$ dans $F$ qui à $x$ associe $%
f(x)$ \fg{}. On note $\mathcal{F}(E,F)$ ou $F^{E}$ l'ensemble des fonctions de $%
E $ dans $F$.

Lorsque $E$ est de la forme $U^{n}=U\times U\times \ldots \times U,$ on dit
que la fonction de $U^{n}$ dans $F$ est une fonction de $n$ variables%

$$
 f\colon \begin{array}{rll} U^n & \to & F\\
   (u_1,u_2,...,u_n) & \mapsto & f(u_1,u_2,...,u_n)
 \end{array}
 $$

et $u_{i}$ est appelée la $i^{\grave{e}me}$ variable de $f.$






\begin{definition}
Si la fonction $f=(E,F,G)$ vérifie $\limfunc{dom}\left( f\right) =E$ on
dit que $f$ est une  
\textbf{fonction} \textbf{totale} de $E$ dans $F.$
\end{definition}




\begin{recherche}


\begin{minipage}[t]{0.5\linewidth}
\begin{figure}
\begin{center}
\begin{tikzpicture}[ every fit/.style={ellipse,draw,thick},] 
\SetGraphUnit{0.75cm}  
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] 

\tikzset{VertexStyle/.style= {shape= circle,
                             shading= ball,
                             ball color= gray!10,
                             minimum size= 15pt,
                             draw}}
\tikzstyle{EdgeStyle}=[->]
\Vertices[dir=\SO]{line}{a,b,c,d,e}
{\SetVertexNoLabel
\Vertices[empty,x=3,y=0,dir=\SO]{line}{al,be,ga,de} }
\foreach \v/\n in {al/\alpha,be/\beta,ga/\gamma,de/\delta}{%
\Vertex[Node,L=$\n$]{\v}}   
\Edge(a)(be)
\Edge(a)(ga)
\Edge(c)(ga)
\Edge(d)(ga)
\Edge(d)(de)
\Edge(e)(de)
\begin{pgfonlayer}{background}
% \node[draw=blue,fill=blue!20,inner sep=1.5pt,thick,ellipse,fit=(a) (b) (d) (e)] {};
% \node[draw=red,fill=red!20,inner  sep=2pt,thick,ellipse,fit=(be) (ga) (de)]{};
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(al) (be) (ga) (de),pin={[pin edge={thick}]F}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{$f$}
\end{figure}
\end{minipage}\hspace{0.5cm}
\begin{minipage}[t]{0.5\linewidth}%\vspace{-0.5cm}
\hspace{5.5cm} 
\begin{flushright}
\begin{figure}
\begin{center}
\begin{tikzpicture}[ every fit/.style={ellipse,draw,thick},] 
\SetGraphUnit{0.75cm}  
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] 

\tikzset{VertexStyle/.style= {shape= circle,
                             shading= ball,
                             ball color= gray!10,
                             minimum size= 15pt,
                             draw}}
\tikzstyle{EdgeStyle}=[->]
\Vertices[dir=\SO]{line}{a,b,c,d,e}
{\SetVertexNoLabel
\Vertices[empty,x=3,y=0,dir=\SO]{line}{al,be,ga,de} }
\foreach \v/\n in {al/\alpha,be/\beta,ga/\gamma,de/\delta}{%
\Vertex[Node,L=$\n$]{\v}}   
\Edge(a)(be)
%\Edge(a)(ga)
\Edge(c)(ga)
\Edge(d)(ga)
%\Edge(d)(de)
\Edge(e)(de)
\begin{pgfonlayer}{background}
% \node[draw=blue,fill=blue!20,inner sep=1.5pt,thick,ellipse,fit=(a) (b) (d) (e)] {};
% \node[draw=red,fill=red!20,inner  sep=2pt,thick,ellipse,fit=(be) (ga) (de)]{};
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(al) (be) (ga) (de),pin={[pin edge={thick}]F}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{$g$}
\end{figure}
\end{flushright}
\end{minipage}



Parmi les deux relations représentées, y a-t-il une fonction? une fonction totale?
\end{recherche}




\subsection{Fonctions particulières}

On est très souvent amené à utiliser des mêmes \og types\fg{} de
fonctions, il est alors naturel de fixer un certain vocabulaire pour é%
viter à chaque fois de redéfinir ces fonctions.

\begin{definition}[Projection canonique]
  
La fonction totale 
$$
\pi_{i}\colon\begin{array}{rll} E_{1}\times E_{2}\times \ldots \times E_{n} &\to &  E_{i} \\ (x_{1},x_{2},\ldots ,x_{n})  & \mapsto &  x_i\end{array}$$

 est appelée
projection canonique de 
$E_{1}\times E_{2}\times \ldots \times E_{n}$ sur $E_{i}$.

Si tous les $E_{i}$ sont égaux au même ensemble $E$, $\pi_{i}$ est
appelée la $i$\eme projection.

\end{definition}





\begin{definition}[Fonction identité]
  C'est la fonction totale  définie sur $E$ par 
$$
 \limfunc{Id}_E\colon \begin{array}{rll} E & \to & E\\
   x & \mapsto & x
 \end{array}
$$%
\end{definition}


\begin{definition}[Composition réitérée]
  
Si $f$ est une fonction totale de $E$ dans $E,$ on note $f^{k}$ la
composition 
$$
\underset{k\text{ fois}}{\underbrace{f\circ f\circ \cdots \circ f}}
$$%
si $k$ est un entier naturel non nul et, par convention, $f^{0}=id_{E}$. 

\end{definition}



\begin{definition}[Fonction caractéristique]
  $$
 \indi{A}\colon \begin{array}{rll} E & \to & \bigl\{0,1\bigr\}\\
   x &  \mapsto & \begin{cases}  1 \text{  si } x\in  A\\ 0 \text{  si }
     x\not \in A \end{cases}
 \end{array}
$$
\end{definition}




\begin{definition}[Loi de composition]
  On appelle loi de composition (ou opération) dans $E$ toute fonction de $%
A\times E$ dans $E$.

 Si $A=E$, on dit que la loi est une loi de composition
interne, sinon on parle de loi de composition externe ou loi mixte. 
\end{definition}


 Si $f$ est
une  telle loi  de  composition  et $(a,x)\in  A\times  E,$ on  remplace
souvent la \textbf{notation préfixée} $f\left(
(a,x)\right) $ par une \textbf{notation infixée} du style $a\circledcirc x$ ou $a\ast x$ ou $a\boxplus x$ ou $%
a\boxdot x$ ou $a+x$  ou...

Sur Caml, on peut définir de nouveaux opérateurs infixes:


\begin{lstlisting}[caption={}]
# let biplus(a,b) = a + b + b ;;
val biplus : int * int -> int = <fun>

# let (++) a b = biplus(a,b);;
val ( ++ ) : int -> int -> int = <fun>

# 1 ++ 2 ;;
- : int = 5

# biplus(1,2);;
- : int = 5
\end{lstlisting}






\subsection{Fonction injective}



\begin{definition}
  
La fonction $f:E\longrightarrow F$ est \textbf{injective} (ou est une
injection) si, et seulement si, tout élément de $F$ a au plus un antécédent. 
\end{definition}




\begin{figure}
\begin{center}
\begin{tikzpicture}[ every fit/.style={ellipse,draw,thick}] 
\SetGraphUnit{.75cm}  
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] 

\tikzset{VertexStyle/.style= {shape= circle,
                             shading= ball,
                             ball color= gray!10,
                             minimum size= 15pt,
                             draw}}
\tikzstyle{EdgeStyle}=[->]
{\SetVertexNoLabel
\Vertices[empty,x=0,y=0,dir=\SO]{line}{a,b,c,d,e} }
\foreach \v in {a,b,c}{%
\Vertex[Node]{\v}}   
{\SetVertexNoLabel
\Vertices[empty,x=3,y=0,dir=\SO]{line}{al,be,ga,de} }
\foreach \v/\n in {al/\alpha,be/\beta,ga/\gamma,de/\delta}{%
\Vertex[Node,L=$\n$]{\v}}   
\Edge(a)(be)
\Edge(b)(de)
\Edge(c)(al)
\begin{pgfonlayer}{background}
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(a) (b) (c) ,pin={[pin edge={thick}]E}] {};
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(al) (be) (ga) (de),pin={[pin edge={thick}]F}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{Injection}
\end{figure}


 Cette définition équivaut à dire que :

\begin{itemize}
\item $f^{-1}$ est une fonction.

\item il n'existe pas deux éléments différents de $E$ qui ont la
même image dans $F.$ En d'autres termes deux éléments diffé%
rents ont toujours des images différentes.

\item il n'existe pas d'élément de $F$ ayant plus d'un antécé%
dent.
\end{itemize}

Mathématiquement cela s'écrit : 
\begin{eqnarray*}
f\text{ injective} &\Leftrightarrow &\forall (x,x^{\prime })\in E^{2},\left(
x\neq x^{\prime }\Rightarrow f(x)\neq f(x^{\prime })\right) \\
f\text{ injective} &\Leftrightarrow &\forall (x,x^{\prime })\in E^{2},\left(
f(x)=f(x^{\prime })\Rightarrow x=x^{\prime }\right)
\end{eqnarray*}



\subsection{Fonction surjective}


\begin{definition}

La fonction  $f:E\longrightarrow F$  est \textbf{surjective} (ou est une
surjection de $E$) sur $F$ si, et seulement si, tout élément de $F$ a au moins
un antécédent. 
\end{definition}




\begin{figure}
\begin{center}
\begin{tikzpicture}[ every fit/.style={ellipse,draw,thick}] 
\SetGraphUnit{.75cm}  
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] 

\tikzset{VertexStyle/.style= {shape= circle,
                             shading= ball,
                             ball color= gray!10,
                             minimum size= 15pt,
                             draw}}
\tikzstyle{EdgeStyle}=[->]
{\SetVertexNoLabel
\Vertices[empty,x=0,y=0,dir=\SO]{line}{a,b,c,d,e} }
\foreach \v in {a,b,c,d}{%
\Vertex[Node]{\v}}   
{\SetVertexNoLabel
\Vertices[empty,x=3,y=0,dir=\SO]{line}{al,be,ga,de} }
\foreach \v/\n in {al/\alpha,be/\beta,ga/\gamma}{%
\Vertex[Node,L=$\n$]{\v}}   
\Edge(a)(be)
\Edge(b)(be)
\Edge(c)(al)
\Edge(d)(ga)
\begin{pgfonlayer}{background}
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(a) (b) (c) (d),pin={[pin edge={thick}]E}] {};
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(al) (be) (ga) ,pin={[pin edge={thick}]F}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{Surjection}
\end{figure}


Cela équivaut à écrire que $\func{Im}%
(f)=F $ ou que $f\left( E\right) =F$ ou encore que la relation ré%
ciproque de $f $ est une relation totale.



\subsection{Fonction bijective}


\begin{definition}
  
La fonction  $f:E\longrightarrow F$  est \textbf{bijective} ou \textbf{biunivoque} ou est une
bijection si, et seulement si, elle est à la fois injective et
surjective.
\end{definition}



%\begin{figure}
\begin{center}
\begin{tikzpicture}[ every fit/.style={ellipse,draw,thick}] 
\SetGraphUnit{.75cm}  
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] 

\tikzset{VertexStyle/.style= {shape= circle,
                             shading= ball,
                             ball color= gray!10,
                             minimum size= 15pt,
                             draw}}
\tikzstyle{EdgeStyle}=[->]
{\SetVertexNoLabel
\Vertices[empty,x=0,y=0,dir=\SO]{line}{a,b,c,d,e} }
\foreach \v in {a,b,c}{%
\Vertex[Node]{\v}}   
{\SetVertexNoLabel
\Vertices[empty,x=3,y=0,dir=\SO]{line}{al,be,ga,de} }
\foreach \v/\n in {al/\alpha,be/\beta,ga/\gamma}{%
\Vertex[Node,L=$\n$]{\v}}   
\Edge(a)(be)
\Edge(b)(ga)
\Edge(c)(al)
\begin{pgfonlayer}{background}
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(a) (b) (c) ,pin={[pin edge={thick}]E}] {};
\node[draw=black,inner sep=4pt,thick,ellipse,fit=(al) (be) (ga),pin={[pin edge={thick}]F}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
%\caption{Bijection}
%\end{figure}


\begin{notation}[Méthode B]
En méthode B on note:
\begin{itemize}
\item ${D\foncpart\ \ C}$: fonctions partielles de D vers C;
\item ${D\fonctot C}$: fonctions totales de D vers C;
\item ${D\injpart\ \ C}$: injections partielles de D vers C;
\item ${D\injtot C}$: injections totales de D vers C;
\item ${D\surjpart\ \ C}$: surjections partielles de D vers C;
\item ${D\surjtot C}$: surjections totales de D vers C;
\item ${D\bijpart C}$: bijections partielles de D sur C;
\item ${D\bijtot C}$: bijections totales de D sur C.
\end{itemize}

\end{notation}





\section{Relations binaires sur un ensemble}

\subsection{Au CE1}



%\begin{figure}
\begin{center}
  \includegraphics[scale=0.6]{CE1-rel-ens}
\end{center}
%\end{figure}




\subsection{Définition}


\begin{definition}
On appelle \textbf{relation binaire sur l'ensemble} $E$ tout triplet du type 
$$
\mathcal{R}=\left( E,E,G_{\mathcal{R}}\right)
$$

où $G_{\mathcal{R}}$ est une partie de $E\times E.$ 
\end{definition}




Une relation binaire
sur l'ensemble $E$ est donc tout simplement une relation \og classique\fg{} qui a
son ensemble de départ égal à son ensemble d'arrivée.





\subsection{Représentations}


On aurait envie d'utiliser le diagramme sagittal habituel mais il est cependant plus \og économique\fg{} de n'utiliser qu'une \og
patate\fg{} car nous restons dans E. On symbolise alors les relations du
type $a\ \RR\ a$ à l'aide de \textit{boucles}:



\begin{figure}
\begin{center}
\begin{tikzpicture}
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] \SetGraphUnit{1cm}
\tikzset{VertexStyle/.style= {shape= circle,shading= ball,
   ball color= gray!10,minimum size= 5pt,draw}}
\tikzstyle{EdgeStyle}=[->]
\Vertex{a}
\EA(a){b}
\SO(a){e}
\SO[empty](b){f}
\SO(f){d}
\EA(f){c}
\Edge(c)(d)
\Edge(c)(e)
\Edge(d)(b)
\tikzstyle{EdgeStyle}=[->,bend left]
\Edge(a)(b)
\Edge(b)(a)
\Loop[dist=1.5cm,dir=SOEA,color= black!70,style={ultra thick}](a)
\begin{pgfonlayer}{background}
% \node[draw=blue,fill=blue!20,inner sep=1.5pt,thick,ellipse,fit=(a) (b) (d) (e)] {};
% \node[draw=red,fill=red!20,inner  sep=2pt,thick,ellipse,fit=(be) (ga) (de)]{};
\node[draw=black,inner sep=8pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{Diagramme sagittal d'une relation sur un ensemble (version 2)}
\end{figure}

On peut bien sûr utiliser une matrice carrée d'ordre $n$. 

Si $E=\left\{ x_{1},x_{2},\cdots
,x_{n}\right\} ,$ la matrice: 
\begin{equation*}
M=(m_{i,j})\text{ avec }\left\{ 
\begin{array}{l}
m_{i,j}=1\text{ si }x_{i}\ \mathcal{R}\ x_{j} \\ 
m_{i,j}=0\text{ si (}x_{i},x_{j})\notin G_{\mathcal{R}}%
\end{array}%
\right.
\end{equation*}%
est appelée la \textit{matrice d'adjacence} de $\mathcal{R}$ ou du graphe $%
\mathcal{R}.$ On dit aussi que $M$ est la\textit{ matrice booléenne} de la
relation $\mathcal{R},$ dans ce cas, les calculs matriciels utilisent le
fait que \og $1+1=1$\fg{}.







\subsection{Composition}

\begin{theoreme}

\begin{itemize}
\item La composition ou le produit de relations binaires sur l'ensemble $E$
est une loi de composition interne dans l'ensemble des relations binaires
sur $E.$

\item Ce produit est associatif et il a pour élément neutre $Id_{E}$
:%
$$
\mathcal{R}\ ; \  Id_{E}=Id_{E}\ ; \ \mathcal{R}=\mathcal{R}
$$

\item Si la relation $\mathcal{R}$ n'est pas la relation vide, on pose $%
\mathcal{R}^{0}=Id_{E}$ sinon c'est la relation vide (de $E$ dans $E$).

\item $k$ désignant un entier naturel, une définition récursive
de $\mathcal{R}^{k}$ est la sui\-vante :%
$$
i\in \mathbb{N},\mathcal{R}^{i+1}=\mathcal{R}^{i}\ ; \  \mathcal{R=R}\circ 
\mathcal{R}^{i}
$$%
\end{itemize}
\end{theoreme}


\begin{remarque}
Il faut bien comprendre que si $x\mathcal{R}^{k}y$ alors il existe%
$$
u_{1},u_{2},\ldots ,u_{k-1}\text{ éléments de }E
$$%
vérifiant 
$$
x\mathcal{R}u_{1}\text{ et }u_{1}\mathcal{R}u_{2}\text{ et }u_{21}\mathcal{R}%
u_{3}\text{ et }\ldots \text{ et }u_{k-1}\mathcal{R}y
$$%
et l'on dit que $y$ est un descendant de $x$ ou que $x$ est un ascendant de $%
y.$
\end{remarque}






\subsection{Chemin}


Nous parlerons l'an prochain de  graphes directionnels et de chemine sur
ces graphes.  Grosso modo, un graphe directionnel, c'est des sommets reliés par des
flèches et un chemin c'est un parcours en suivant ces flèches.

Nous pouvons reprendre l'idée pour une relation:

\begin{definition}
Soit $\RR$  une relation. Il existe  un \textbf{chemin} de  $a$ vers $b$
dans $\RR$ s'il  existe une suite d'éléments $x_1,x_2,x_3,...,x_{n-1}$
telle que  $(a,x_1), (x_1,x_2), (x_2,x_3),...,(x_{n-1},b)$ appartiennent
à $\RR$. Ce chemin est de \textbf{longueur} $n$.
\end{definition}

En      reprenant      la      relation     représentée      sur      la
figure\vref{fig::fermeture1}, il  existe un chemin  (et même plusieurs!)
de $a$ vers $c$, passant par exemple par $a,a,a,e,d,b,d,c$.


Le théorème suivant nous sera très utile:

\begin{theoreme}
Soit $\RR$  une relation sur  un ensemble et  $n$ un entier  naturel. Il
existe un chemin de longueur $n$ de $a$ vers $b$ si, et seulement si, $(a,b)\in\RR^n$.
\end{theoreme}


La démonstration s'effectue par récurrence...et est laissée au lecteur attentif.









\subsection{Relations particulières}

\begin{definition}[Relation réflexive]
   $\mathcal{R}$ est \textbf{réflexive} si, et seulement si, pour
tout $x$ de $E$ on a $x\mathcal{R}x.$ En d'autres termes $\mathcal{R}$ est r%
éflexive si, et seulement si, $G_{\mathcal{R}}$ contient $\Delta $ la
diagonale de $E\times E,$ $\Delta =\left\{ \left( x,x\right) \mid x\in
E\right\} .$%
\end{definition}



\begin{figure}
\begin{center}
\begin{tikzpicture}
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] \SetGraphUnit{1cm}
\tikzset{VertexStyle/.style= {shape= circle,shading= ball,
   ball color= gray!10,minimum size= 5pt,draw}}
\tikzstyle{EdgeStyle}=[->]
\Vertex{a}
\EA(a){b}
\SO(a){e}
\SO[empty](b){f}
\SO(f){d}
\EA(f){c}
\Edge(a)(e)
\Edge(d)(c)
\Edge(b)(d)
\Edge(e)(b)
\Loop[dist=1.25cm,dir=NOEA,color= black!70,style={ultra thick}](a)
\Loop[dist=1.25cm,dir=NOEA,color= black!70,style={ultra thick}](b)
\Loop[dist=1.25cm,dir=SOEA,color= black!70,style={ultra thick}](c)
\Loop[dist=1.25cm,dir=SOEA,color= black!70,style={ultra thick}](d)
\Loop[dist=1.25cm,dir=SOEA,color= black!70,style={ultra thick}](e)
\begin{pgfonlayer}{background}
% \node[draw=blue,fill=blue!20,inner sep=1.5pt,thick,ellipse,fit=(a) (b) (d) (e)] {};
% \node[draw=red,fill=red!20,inner  sep=2pt,thick,ellipse,fit=(be) (ga) (de)]{};
\node[draw=black,inner sep=8pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{Relation réflexive}
\end{figure}


\begin{theoreme}
$\RR$ est réflexive si, et seulement si, $\mathcal{R}\cup Id_{E}=\mathcal{R}$.
\end{theoreme}


\begin{definition}[Fermeture réflexive]
La \textbf{fermeture réflexive} d'une relation quelconque $\mathcal{R}$
sur $E$ est  la relation dont le graphe  est $G_{\mathcal{R}}\cup \Delta
$.

C'est la plus petite relation binaire sur $E$ (au sens de l'inclusion) qui
contient $\mathcal{R}.$
\end{definition}




\begin{minipage}[t]{0.5\linewidth}
\begin{figure}
\begin{center}
\begin{tikzpicture}
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] \SetGraphUnit{1cm}
\tikzset{VertexStyle/.style= {shape= circle,shading= ball,
   ball color= gray!10,minimum size= 5pt,draw}}
\tikzstyle{EdgeStyle}=[->]
\Vertex{a}
\EA(a){b}
\SO(a){e}
\SO[empty](b){f}
\SO(f){d}
\EA(f){c}
\Edge(c)(b)
\Edge(c)(e)
\Edge(d)(e)
\tikzstyle{EdgeStyle}=[->,bend left]
\Edge(a)(b)
\Edge(b)(a)
\Loop[dist=1.5cm,dir=SOEA,color= black!70,style={ultra thick}](a)
\begin{pgfonlayer}{background}
% \node[draw=blue,fill=blue!20,inner sep=1.5pt,thick,ellipse,fit=(a) (b) (d) (e)] {};
% \node[draw=red,fill=red!20,inner  sep=2pt,thick,ellipse,fit=(be) (ga) (de)]{};
\node[draw=black,inner sep=8pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{La relation $\RR$}
\end{figure}
\end{minipage}\hspace{0.5cm}
\begin{minipage}[t]{0.5\linewidth}%\vspace{-0.5cm}
\hspace{5.5cm} 
\begin{flushright}
\begin{figure}
\begin{center}
\begin{tikzpicture}
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] \SetGraphUnit{1cm}
\tikzset{VertexStyle/.style= {shape= circle,shading= ball,
   ball color= gray!10,minimum size= 5pt,draw}}
\tikzstyle{EdgeStyle}=[->]
\Vertex{a}
\EA(a){b}
\SO(a){e}
\SO[empty](b){f}
\SO(f){d}
\EA(f){c}
\Edge(c)(b)
\Edge(c)(e)
\Edge(d)(e)
\tikzstyle{EdgeStyle}=[->,bend left]
\Edge(a)(b)
\Edge(b)(a)
\Loop[dist=1.5cm,dir=SOEA,color= black!70,style={ultra thick}](a)
\Loop[dist=1.5cm,dir=SOEA,color= black!70,style={ultra thick}](b)
\Loop[dist=1.5cm,dir=SOEA,color= black!70,style={ultra thick}](c)
\Loop[dist=1.5cm,dir=SOEA,color= black!70,style={ultra thick}](d)
\Loop[dist=1.5cm,dir=SOEA,color= black!70,style={ultra thick}](e)
\begin{pgfonlayer}{background}
% \node[draw=blue,fill=blue!20,inner sep=1.5pt,thick,ellipse,fit=(a) (b) (d) (e)] {};
% \node[draw=red,fill=red!20,inner  sep=2pt,thick,ellipse,fit=(be) (ga) (de)]{};
\node[draw=black,inner sep=8pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{La fermeture réflexive de $\RR$}
\end{figure}
\end{flushright}
\end{minipage}





\begin{definition}[Relation irréflexive]
 $\mathcal{R}$ est irréflexive (
on utilise aussi le mot \og antiréflexif\fg{}) si, et seulement si, il
n'existe pas $x\in E$ vérifiant $x\mathcal{R}x.$
\end{definition}

 Ne pas confondre une relation irréflexive
avec une relation non réflexive!


Par  exemple,  la  relation  \og   ...  est  l'enfant  de  ...\fg{}  est
irréflexive...



\begin{definition}[Relation symétrique]
  $\mathcal{R}$ est \textbf{symétrique} si, et seulement si, 
à chaque fois que l'on a $x\mathcal{R}y$ on a aussi $y\mathcal{R}x.$
\end{definition}



\begin{figure}
\begin{center}
\begin{tikzpicture}
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] \SetGraphUnit{1cm}
\tikzset{VertexStyle/.style= {shape= circle,shading= ball,
   ball color= gray!10,minimum size= 5pt,draw}}
\tikzstyle{EdgeStyle}=[->]
\Vertex{a}
\EA(a){b}
\SO(a){e}
\SO[empty](b){f}
\SO(f){d}
\EA(f){c}
\tikzstyle{EdgeStyle}=[->,bend left=10]
\Edge(a)(e)
\Edge(d)(c)
\Edge(b)(d)
\Edge(e)(b)
\Edge(e)(a)
\Edge(c)(d)
\Edge(d)(b)
\Edge(b)(e)
\Loop[dist=1.25cm,dir=NOEA,color= black!70,style={ultra thick}](b)
\begin{pgfonlayer}{background}
% \node[draw=blue,fill=blue!20,inner sep=1.5pt,thick,ellipse,fit=(a) (b) (d) (e)] {};
% \node[draw=red,fill=red!20,inner  sep=2pt,thick,ellipse,fit=(be) (ga) (de)]{};
\node[draw=black,inner sep=8pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{Relation symétrique}
\end{figure}


\begin{recherche}

 Considérons par exemple la relation:

$\text{Train}=\bigl\{\text{(Nantes,Paris),(Paris,Nantes),(Nantes,Vertou),(Vertou,Nantes),}\bigr.$

\hspace{2cm}$\bigl.\text{(Paris,Vertou),(Vertou,Paris),(Paris,Sucé),(Sucé,Paris)}\bigr\}$

Est-elle symétrique?


\end{recherche}


\begin{theoreme}
  Matriciellement, $\mathcal{R}$ est symétrique si, et seulement si, sa
matrice $R$ est symétrique, c'est-à-dire $^{t}R=R.$
\end{theoreme}




\begin{definition}[Fermeture symétrique]

La {fermeture symétrique} de la relation $\mathcal{R=}\left( E,G_{%
\mathcal{R}}\right) $ est la plus petite relation symétrique dont le
graphe  contient $G_{\mathcal{R}}$.

\end{definition}




\begin{minipage}[t]{0.5\linewidth}
\begin{figure}
\begin{center}
\begin{tikzpicture}
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] \SetGraphUnit{1cm}
\tikzset{VertexStyle/.style= {shape= circle,shading= ball,
   ball color= gray!10,minimum size= 5pt,draw}}
\tikzstyle{EdgeStyle}=[->]
\Vertex{a}
\EA(a){b}
\SO(a){e}
\SO[empty](b){f}
\SO(f){d}
\EA(f){c}
\Edge(c)(b)
\Edge(c)(e)
\Edge(d)(e)
\tikzstyle{EdgeStyle}=[->,bend left]
\Edge(a)(b)
\Edge(b)(a)
\Loop[dist=1.5cm,dir=SOEA,color= black!70,style={ultra thick}](a)
\begin{pgfonlayer}{background}
% \node[draw=blue,fill=blue!20,inner sep=1.5pt,thick,ellipse,fit=(a) (b) (d) (e)] {};
% \node[draw=red,fill=red!20,inner  sep=2pt,thick,ellipse,fit=(be) (ga) (de)]{};
\node[draw=black,inner sep=8pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{La relation $\RR$}
\end{figure}
\end{minipage}\hspace{0.5cm}
\begin{minipage}[t]{0.5\linewidth}%\vspace{-0.5cm}
\hspace{5.5cm} 
\begin{flushright}
\begin{figure}
\begin{center}
\begin{tikzpicture}
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] \SetGraphUnit{1cm}
\tikzset{VertexStyle/.style= {shape= circle,shading= ball,
   ball color= gray!10,minimum size= 5pt,draw}}
\tikzstyle{EdgeStyle}=[->]
\tikzstyle{EdgeStyle}=[->,bend left=20]
\Vertex{a}
\EA(a){b}
\SO(a){e}
\SO[empty](b){f}
\SO(f){d}
\EA(f){c}
\Edge(c)(b)
\Edge(b)(c)
\Edge(c)(e)
\Edge(e)(c)
\Edge(d)(e)
\Edge(e)(d)
\Edge(a)(b)
\Edge(b)(a)
\Loop[dist=1.5cm,dir=SOEA,color= black!70,style={ultra thick}](a)
\begin{pgfonlayer}{background}
% \node[draw=blue,fill=blue!20,inner sep=1.5pt,thick,ellipse,fit=(a) (b) (d) (e)] {};
% \node[draw=red,fill=red!20,inner  sep=2pt,thick,ellipse,fit=(be) (ga) (de)]{};
\node[draw=black,inner sep=8pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{La fermeture symétrique de $\RR$}
\end{figure}
\end{flushright}
\end{minipage}


\begin{theoreme}
La fermeture symétrique de $\mathcal{R}$ est $\mathcal{R}\cup \mathcal{R}^{-1}$.
\end{theoreme}



\begin{definition}[Relation antisymétrique]
  $\mathcal{R}$ est {antisymétrique} si, et seulement si, 
à chaque fois que l'on a $x\mathcal{R}y,$ avec $x$ différent de $y,$
on n'a pas $y\mathcal{R}x.$ Cela équivaut à écrire que si on a
simultanément $x\mathcal{R}y\ $et $y\mathcal{R}x,$ on a forcément $%
x=y.$
\end{definition}

Le diagramme sagittal ne possède aucun \og aller et retour\fg{}.



\begin{definition}[Relation transitive]
 $\mathcal{R}$ est {transitive} si, et seulement si, à
chaque fois que l'on a $x\mathcal{R}y$ et $y\mathcal{R}z,$ on a aussi $x%
\mathcal{R}z.$

\end{definition}


 Si \og on peut aller de $x$ à $z$ en passant par $y,$ on
doit pouvoir aller directement de $x$ à $z$\fg{}.




\begin{minipage}[t]{0.5\linewidth}
\begin{figure}
\begin{center}
\begin{tikzpicture}
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] \SetGraphUnit{1cm}
\tikzset{VertexStyle/.style= {shape= circle,shading= ball,
   ball color= gray!10,minimum size= 5pt,draw}}
\tikzstyle{EdgeStyle}=[->]
\Vertex{a}
\EA(a){b}
\SO(a){e}
\SO[empty](b){f}
\SO(f){d}
\EA(f){c}
\Edge(e)(c)
\Edge(c)(d)
\Edge(e)(d)
\tikzstyle{EdgeStyle}=[->,bend left]
\Edge(a)(b)
\Edge(b)(a)
\Loop[dist=1.5cm,dir=SOEA,color= black!70,style={ultra thick}](a)
\Loop[dist=1.5cm,dir=SOEA,color= black!70,style={ultra thick}](b)
\begin{pgfonlayer}{background}
% \node[draw=blue,fill=blue!20,inner sep=1.5pt,thick,ellipse,fit=(a) (b) (d) (e)] {};
% \node[draw=red,fill=red!20,inner  sep=2pt,thick,ellipse,fit=(be) (ga) (de)]{};
\node[draw=black,inner sep=8pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{Relation transitive}
\end{figure}
\end{minipage}\hspace{0.5cm}
\begin{minipage}[t]{0.5\linewidth}%\vspace{-0.5cm}
\hspace{5.5cm} 
\begin{flushright}
\begin{figure}
\begin{center}
\begin{tikzpicture}
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] \SetGraphUnit{1cm}
\tikzset{VertexStyle/.style= {shape= circle,shading= ball,
   ball color= gray!10,minimum size= 5pt,draw}}
\tikzstyle{EdgeStyle}=[->]
\Vertex{a}
\EA(a){b}
\SO(a){e}
\SO[empty](b){f}
\SO(f){d}
\EA(f){c}
\Edge(e)(c)
\Edge(c)(d)
\Edge(e)(d)
\tikzstyle{EdgeStyle}=[->,bend left]
\Edge(a)(b)
\Edge(b)(a)
\Loop[dist=1.5cm,dir=SOEA,color= black!70,style={ultra thick}](a)
\begin{pgfonlayer}{background}
\node[draw=black,inner sep=8pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{Relation non transitive}
\end{figure}
\end{flushright}
\end{minipage}






\begin{recherche}

 Considérons à nouveau la relation:


$\text{Train}=\bigl\{\text{(Nantes,Paris),(Paris,Nantes),(Nantes,Vertou),(Vertou,Nantes)},\bigr.$

\hspace{2cm}$\bigl.\text{(Paris,Vertou),(Vertou,Paris),(Paris,Sucé),(Sucé,Paris)}\bigr\}$

Est-elle transitive?


\end{recherche}









\begin{theoreme}
  \begin{itemize}
  \item $\mathcal{R}$ transitive $\Leftrightarrow \mathcal{R}^{2}\subseteq \mathcal{R}%
.$
\item $\mathcal{R}$ réflexive et transitive $\Rightarrow \mathcal{R}^{2}=%
\mathcal{R}.$
\item  $\RR$ est transitive  si, et  seulement si,  $\RR^n\subseteq \RR$
  pour tout entier naturel non nul $n$.
  \end{itemize}
\end{theoreme}



\begin{definition}[Fermeture transitive]


La {fermeture transitive} de la relation $\mathcal{R}=\left( E,G_{%
\mathcal{R}}\right) ,$ est la plus petite (au sens de l'inclusion) relation
transitive sur $E$ dont le graphe contient $G_{\mathcal{R}}.$

\end{definition}




\begin{minipage}[t]{0.5\linewidth}
\begin{figure}
\begin{center}
\begin{tikzpicture}
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] \SetGraphUnit{1cm}
\tikzset{VertexStyle/.style= {shape= circle,shading= ball,
   ball color= gray!10,minimum size= 5pt,draw}}
\tikzstyle{EdgeStyle}=[->]
\Vertex{a}
\EA[empty](a){g}
\EA(g){b}
\SO(a){e}
\SO[empty](b){f}
\SO(f){d}
\EA(f){c}
\Edge(c)(e)
\Edge(c)(d)
\Edge(d)(b)
\tikzstyle{EdgeStyle}=[->,bend left=10]
\Edge(a)(b)
\Edge(b)(a)
\Loop[dist=1.5cm,dir=SOEA,color= black!70,style={ultra thick}](a)
\begin{pgfonlayer}{background}
% \node[draw=blue,fill=blue!20,inner sep=1.5pt,thick,ellipse,fit=(a) (b) (d) (e)] {};
% \node[draw=red,fill=red!20,inner  sep=2pt,thick,ellipse,fit=(be) (ga) (de)]{};
\node[draw=black,inner sep=8pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{Relation}\label{fig::ferm_trans}
\end{figure}
\end{minipage}\hspace{0.5cm}
\begin{minipage}[t]{0.5\linewidth}%\vspace{-0.5cm}
\hspace{5.5cm} 
\begin{flushright}
\begin{figure}
\begin{center}
\begin{tikzpicture}
\SetUpEdge[lw= 1.5pt,color= black!70]
\GraphInit[vstyle=Normal] \SetGraphUnit{1cm}
\tikzset{VertexStyle/.style= {shape= circle,shading= ball,
   ball color= gray!10,minimum size= 5pt,draw}}
\tikzstyle{EdgeStyle}=[->]
\Vertex{a}
\EA[empty](a){g}
\EA(g){b}
\SO(a){e}
\SO[empty](b){f}
\SO(f){d}
\EA(f){c}
\Edge(c)(b)
\Edge(c)(a)
\Edge(c)(d)
\Edge(c)(e)
\Edge(d)(b)
\Edge(d)(a)
\tikzstyle{EdgeStyle}=[->,bend left=10]
\Edge(a)(b)
\Edge(b)(a)
\Loop[dist=1.5cm,dir=SOEA,color= black!70,style={ultra thick}](a)
\Loop[dist=1.5cm,dir=SOEA,color= black!70,style={ultra thick}](b)
\begin{pgfonlayer}{background}
\node[draw=black,inner sep=8pt,thick,ellipse,fit=(a) (b) (c) (d) (e),pin={[pin edge={thick}]E}] {};
\end{pgfonlayer}
\end{tikzpicture}
\end{center}
\caption{Fermeture transitive de la relation}\label{fig::ferm_trans2}
\end{figure}
\end{flushright}
\end{minipage}



\subsection{Fermeture transitive et chemin}

En  fait,   trouver  la  fermeture  transitive   d'une  relation,  c'est
déterminer les couples reliés par un chemin.


\begin{definition}
Soit  $\RR$ une  relation  sur  un ensemble.  La  relation de  connexion
$\RR^+$ contient  tous les couples  $(a,b)$ tels qu'il existe  un chemin
sur $\RR$ de longueur non nulle allant de $a$ vers $b$.
\end{definition}

Maintenant,  souvenons-nous que  $\RR^n$ est  formé des  couples $(a,b)$
tels  qu'il existe un  chemin de  longueur $n$  de $a$  vers $b$.  Il en
découle que $\RR^+$ est en fait la réunion de tous les $\RR^n$:


\begin{theoreme}
 $$\mathcal{R}^{+}=\displaystyle\bigcup \limits_{n\in \mathbb{N}^{\ast  }}\mathcal{R}^{n}$$
\end{theoreme}


\begin{recherche}
Par exemple,  si $\RR$  est la relation  sur l'ensemble  des département
français qui  contient $(a,b)$  si les départements  $a$ et $b$  ont une
frontière commune, quelle est $\RR^n$? $\RR^+$?
\end{recherche}


Nous en arrivons au théorème important suivant:


\begin{theoreme}
La fermeture transitive d'une relation $\RR$ est égale à $\RR^+$.
\end{theoreme}



Pour les curieux, on peut survoler une petite démonstration de ce résultat.


Il   est  assez   simple   de  montrer   que   $\RR^+$  est   transitive
(faites-le...) et que $\RR^+$ contient $\RR$.

Maintenant,  il faudrait  montrer  que n'importe  quelle relation  $\SR$
transitive qui contient $\RR$ contient aussi $\RR^+$.



Comme $\SR$ est  transitive, alors $\SR^n$ aussi et  $\SR^n \subseteq \SR$.

Or          $\mathcal{S}^{+}=\displaystyle\bigcup          \limits_{n\in
  \mathbb{N}^{\ast }}\mathcal{S}^{n}$ donc $\SR^+\subseteq \SR$. Or $\RR
\subseteq \SR$ donc $\RR^+\subseteq \SR^+$. 

Finalement  $\RR^+\subseteq  \SR^+\subseteq  \SR$  ce qui  achève  notre
démonstration.

Bon, on sait ce que c'est que la fermeture transitive: il reste à savoir
comment la déterminer concrètement...







\subsubsection*{Fermeture d'une relation: du concret}


Disons que vous  gérer un réseau informatique avec  des centres situés à
Vertou, Saint Mars du Désert,  Chavagne en Paillé, Guéméné Penfao et des
lignes de câbles unidirectionnelles de Vertou vers Saint Mars, de Vertou vers Chavagne, de
Chavagne  vers Guéméné,  de Guéméné  vers Saint  Mars. Si  $\RR$  est la
relation qui contient le couple $(a,b)$  s'il y a une ligne entre $a$ et
$b$, on  voudrait savoir  si on peut  connecter deux centres  donnés. Le
chemin de Vertou vers Guéméné existe  mais est indirect car il passe par
Chavagne:  la relation  $\RR$  n'est  donc pas  transitive  car elle  ne
contient  pas  tous  les  couples  pouvant se  connecter.  La  fermeture
transitive est en fait la plus petite relation transitive contenant 
$\RR$.  C'est concrètement la relation qui comprend tous les couples de centres
pouvant être connectés. 

On  peut  dans  le  même  esprit s'occuper  des  fermetures  symétrique,
réflexive, réflexive-transitive,  etc. Pour les  fermetures réflexive et
symétrique,  c'est assez immédiat.  Notre problème  sera de  trouver des
algorithmes pour la fermeture transitive car c'est moins simple.

\begin{recherche}
  Essayez     de    déterminer     la     fermeture    transitive     de
  $\RR=\bigl\{(1,3),(1,4),(2,1),(3,2)\bigr\}$       sur       l'ensemble
  $\ER=\bigl\{1,2,3,4\bigr\}$.


\end{recherche}




\section{Relations d'équivalence}





Tous les étudiants d'Info s'inscrivent pour un camp d'été de maths auprès de
leur professeur adoré.

Comme il  y a beaucoup  d'étudiants, on décide d'inscrire  les étudiants
dont le nom de famille commence par  une lettre comprise entre A et G le
lundi, ceux dont le nom commence par une lettre entre H et N le mardi et
les autres le mercredi.

Soit $\RR$  la relation  définie sur l'ensemble  $\ER$ des  étudiants de
l'IUT qui contient $(x,y)$ si $x$ et $y$ se sont inscrits le même jour.

 On  vérifie aisément que  cette relation  est réflexive,  symétrique et
 transitive. 

On remarque surtout  que $\RR$ divise l'ensemble $\ER$  des étudiants en
trois classes distinctes. Il suffit de savoir dans quel classe se trouve
l'étudiant pour  savoir quel  jour il s'inscrira,  sans avoir  besoin de
connaître son identité: gain de temps...

Ce genre  de relation réflexive, symétrique et  transitive s'appelle une
\textbf{relation d'équivalence}.




\begin{definition}

$\mathcal{R}=\left( E,G_{\mathcal{R}}\right) ,$ où $E$ est un ensemble
non vide, est une \textbf{relation d'équivalence} si, et seulement si, $%
\mathcal{R}$ est 
\begin{center}
\text{\textbf{Réflexive et Symétrique et Transitive (R.S.T.)}}
\end{center}%


$x$ désignant un élément de $E,$ la \textbf{classe d'é%
quivalence} de $x$ est l'ensemble 
$$
cl\left( x\right) =\overline{x}=\left\{ y\in E\mid x\mathcal{R}y\right\}
=\left\{ y\in E\mid y\mathcal{R}x\right\}
$$
\end{definition}


Beaucoup d'autres notations sont utilisées : $\overline{x}=cl(x)=%
\widehat{x}=\widetilde{x}=\left[ x\right] _{\mathcal{R}}$ ou encore $%
\mathring{x}=\breve{x}=\cdots $.




\begin{propriete}
 La classe de $x,$ $\overline{x},$ ne peut être un ensemble vide.
\end{propriete}


En effet, $\mathcal{R}$ étant réflexive, on a pour tout $x$ de $E,$ $%
x\mathcal{R}x$ et, par conséquent, $\overline{x}$ contient au moins un 
élément qui est $x.$



\begin{propriete}
$$x\mathcal{R}y\Leftrightarrow \overline{x}=\overline{y}.$$
\end{propriete}


\begin{enumerate}
\item Supposons tout d'abord que $x\mathcal{R}y$ et choisissons un él%
ément $z\in \overline{y}$ ; nous avons alors $y\mathcal{R}z$ et comme $x%
\mathcal{R}y$ nous obtenons $x\mathcal{R}z$ qui prouve que $z\in \overline{x}%
.$ Nous venons de démontrer que $\overline{y}\subseteq \overline{x}.$ En
permutant les r\^{o}les de $x$ et $y$ (ne pas oublier que $\mathcal{R}$ est
symétrique) on obtient $\overline{x}\subseteq \overline{y}$ et, par cons%
équent, $\overline{x}=\overline{y}.$

\item Supposons maintenant que $\overline{x}=\overline{y},$ nous savons que $%
y\in \overline{y}$ et donc que $y\in \overline{x}$ ; on en déduit que $x%
\mathcal{R}y.$
\end{enumerate}


\begin{propriete}
 $\overline{x}\cap \overline{y}=\{\}  \Leftrightarrow x$ n'est pas
en relation avec $y.$
\end{propriete}

 Nous venons d'établir que $x\mathcal{R}y\Leftrightarrow 
\overline{x}=\overline{y}$. En conséquence, si $x\mathcal{R}y,$ il est
impossible que $\overline{x}\cap \overline{y}=\{\}  $ puisque $\overline{%
x}=\overline{y}$ et qu'aucune classe n'est vide. Nous venons de prouver que $%
\overline{x}\cap \overline{y}=\{\}  \Rightarrow x\overline{\mathcal{R}}%
y. $ transposéement, supposons que $\overline{x}\cap \overline{y}\neq
\{\}  .$ La classe de $x$ et la classe de $y$ ont donc au moins un él%
ément en commun $z$ qui vérifie $x\mathcal{R}z$ et $z\mathcal{R}y$
et, du coup, on a forcément $x\mathcal{R}y.$ Nous venons de dé%
montrer que $\overline{x}\cap \overline{y}\neq \{\}  \Rightarrow x%
\mathcal{R}y$ donc aussi $x\overline{\mathcal{R}}y\Rightarrow \overline{x}%
\cap \overline{y}=\{\}  .$



\begin{propriete}
 L'ensemble des classes d'équivalences, noté $E\diagup \mathcal{%
R}$, est une partition de $E.$
\end{propriete}


 Nous n'allons détailler ce résultat
que lorsque le nombre de classes est fini : notons $C_{1},C_{2},\ldots
,C_{k} $ les différentes classes d'équivalence. Nous venons de
prouver que $C_{i}\cap C_{j}=\{\}  $ si $i\neq j$. Maintenant
choisissons un élément quelconque $e\in E,$ nous savons que $e\in 
\overline{e}$ et la classe de $e$ est forcément l'une des classes $%
C_{i}. $ Ceci prouve que 
$\displaystyle\bigcup\limits_{i=1}^{k}C_{i}=E$



\begin{propriete}
Toute partition de $E$ définit une relation d'équivalence sur $E.$
\end{propriete}


À vous de  trouver une démonstration si vous avez un  peu compris ce qui
se passe...



% %%%%%%%%%%%





\vfill

\eject




\section{Structures d'ordre}


\subsection{Relation d'ordre}



%Tout d'abord, quelques définitions:

\begin{definition}
La relation $\mathcal{R}=\left( E,G\right) $ est une \textbf{relation d'ordre%
} (ordre large) si, et seulement si, $\mathcal{R}$ est

\begin{center}
\text{\textbf{Réflexive et Antisymétrique et Transitive (R.A.T.)}}
\end{center}%
et on vérifie immédiatement que 
$$
\mathcal{R}\text{ relation d'ordre}\Leftrightarrow \mathcal{R}^{-1}\text{
relation d'ordre}
$$

Une relation d'ordre est dite \textbf{totale} si, et seulement si, pour tout couple $%
(x,y)$ de $E$ on a soit $x\mathcal{R}y,$ soit $y\mathcal{R}x.$ Cela signifie
que deux éléments quelconques sont toujours \og comparables\fg{}. Si la
relation d'ordre n'est pas totale on dit qu'elle est \textbf{partielle} et, dans ce
cas, il existe au moins deux éléments distincts de $E$ qui ne sont
pas comparables.

La relation $\mathcal{R}=\left( E,G\right) $ est une relation d'\textbf{%
ordre strict} si, et seulement si, $\mathcal{R}$ est

\begin{center}
\text{\textbf{Irréflexive et Antisymétrique et Transitive}}
\end{center}%
\end{definition}



En général une relation d'ordre (large) est notée par $\leq $ 
ou par $\preceq $ ou par $\leqslant$ et une
relation d'ordre strict est notée par $<$ ou par $\prec$.

La relation transposée de la relation d'ordre $\leqslant $ est notée $%
\geqslant $ : 
$
x\leqslant y\Leftrightarrow y\geqslant x
$
et il est bien entendu que l'on peut utiliser à loisir, l'une ou l'autre.






\begin{theoreme}
$\mathcal{R}$ est une relation d'ordre $\Leftrightarrow \left\{ 
\begin{tabular}{l}
$\mathcal{R}\cap \mathcal{R}^{-1}=Id_{E}$ \\ 
$\mathcal{R}=\mathcal{R}^{2}=\mathcal{R}^{\ast }$%
\end{tabular}%
\right. $
\end{theoreme}

Pourquoi?...


\subsection{Ensembles ordonnés}


\begin{definition}
  Un ensemble $E$ est dit ordonné par la relation $\mathcal{R}$ si $%
\mathcal{R}$ est une relation binaire sur $E$ et si $\mathcal{R}$ est une
relation d'ordre. Un \textbf{ensemble ordonné} se présente comme le
couple $\left( E,\mathcal{R}\right) $ où $\mathcal{R}$ est une relation
d'ordre sur $E.$ On dit que l'ensemble ordonné $\left( E,\mathcal{R}%
\right) $ est totalement ordonné si $\mathcal{R}$ est une relation
d'ordre total.
\end{definition}



Attention! Un même ensemble peut être muni de plusieurs relations
d'ordre différentes, si $\leqslant _{1}$ et $\leqslant _{2}$ sont deux relations
d'ordre différentes alors les ensembles ordonnés $\left( E,\leqslant
_{1}\right) $ et $\left( E,\leqslant _{2}\right) $ sont des ensembles ordonné%
s différents.



\begin{exemple}
Montrer  par exemple  que la  relation d'inclusion  $\subseteq$  est une
relation  d'ordre (de quelle  nature?) sur  l'ensemble des  parties d'un
ensemble donné E.


Que pensez-vous de l'ensemble $\bbz^+$ muni de la relation \og divise\fg{}?
\end{exemple}



\begin{NB}
En fait,  on peut montrer que  le principe de  récurrence s'applique sur
tout ensemble bien ordonné.
\end{NB}


\subsection{Ordre lexicographique}


Comment sont rangés les mots dans un dictionnaire? C'est une des manière
de ranger des  éléments d'un produit cartésien (comment  le définir?). Y
en a-t-il d'autres possibles?


\subsection{Diagramme de \textsc{Hasse}}


Dresser un diagramme sagittal peut s'avérer parfois pénible: il y a trop
de flèches dans tous les  sens...Nous allons voir un moyen de visualiser
plus nettement la situation d'ensembles ordonnés.
Nous aurons besoin tout d'abord  de préciser les notions de prédécesseur
et de successeur.


\begin{definition}
On appelle éléments consécutifs de l'ensemble ordonné $%
\left( E,\leq \right) $ deux éléments $a$ et $b$ qui vérifient 
$$
\left\{ 
\begin{array}{l}
a< b \\ 
a\leqslant c\leqslant b\Rightarrow a=c\text{ ou }b=c%
\end{array}%
\right.
$$

% On note alors $a$ $\text{pred}$ $b$ ;
$a$ est un prédécesseur (imm%
édiat) de $b$ ou $b$ est un successeur (immédiat) de $a.$
\end{definition}

Tout ça pour dire que si $a$  et $b$ sont consécutifs, il n'y a personne
entre eux, ils sont différents et l'un est plus grand que l'autre.


Revenons à nos ensembles ordonnés: pour ne pas avoir trop de flèches, on
convient de ne relier $x$ à $y$ que si $x$ est un prédécesseur de $y$ et
on  place  $x$  sous  $y$.  On obtient  alors  un  \textbf{diagramme  de
  \textsc{Hasse}}.

En fait,  il s'agit  d'un diagramme sagittal  où on élimine  les boucles
puisqu'on sait que  la relation est réflexive. On  élimine aussi les \og
raccourcis\fg{}: s'il y a  une flèche de $a$ vers $b$ ,  de $b$ vers $c$
et  de $a$  vers  $c$, on  élimine  la dernière  puisqu'on  sait que  la
relation  est transitive. Enfin,  on n'a  pas besoin  de flèches  car on
\og pointe vers le haut\fg{}.

Considérons par exemple l'ensemble $\ER=\bigl\{2,3,6,7,8,9,12,18\bigr\}$
et l'ordre partiel $\bigl\{(a,b)\mid a \text{ divise }b\bigr\}$.


Le diagramme de \textsc{Hasse} correspondant est:


\begin{figure}
\begin{center}
\begin{tikzpicture}
\SetGraphUnit{1}
\Vertex{7}
\EA(7){2} \NOEA(2){6} \SOEA(6){3}
\NOEA(6){9} \NOWE(6){12} \NOEA(12){18} \WE(12){8}

\Edge(2)(8)
\Edge(2)(6)
\Edge(3)(6)
\Edge(6)(18)
\Edge(6)(12)
\Edge(3)(9)
\Edge(9)(18)
;
\end{tikzpicture}
\caption{Diagramme            de            \textsc{Hasse}            de
  $\bigl\{\{2,3,6,7,8,9,12,18\},\mid\bigr\}$}\label{fig::hasse_divise}
\end{center}
\end{figure}


Voici        un       autre        exemple        pour       $\bigl\{\PR
\left(\bigl\{a,b,c\bigr\}\right),\subseteq\bigr\}$:


\begin{figure}
\begin{center}
\begin{tikzpicture}
\SetGraphUnit{1.15}
\SetUpVertex[LabelOut]
\GraphInit[vstyle=Classic]
\Vertex[Lpos=-90,L=$\{\} $]{O}
\NO[Lpos=-60,L=$\{c\}$](O){C}
\NOWE[Lpos=180,L=$\{a\}$](O){A}
\NOEA[Lpos=0,L=$\{b\}$](O){B}
\NO[Lpos=180,L=$\{ac\}$](A){D}
\NO[Lpos=-90,L=$\{ab\}$](C){E}
\NO[Lpos=0,L=$\{bc\}$](B){F}
\NO[Lpos=90,L=$\{abc\}$](E){G}
\Edge(O)(A)
\Edge(O)(B)
\Edge(O)(C)
\Edge(B)(F)
\Edge(A)(D)
\Edge(E)(G)
\Edge(A)(E)
\Edge(B)(E)
\Edge(D)(G)
\Edge(F)(G)
\Edge(C)(F)
\Edge(C)(D)
;
\end{tikzpicture}
\caption{Diagramme            de            \textsc{Hasse}            de
  $\bigl\{\PR
\left(\bigl\{a,b,c\bigr\}\right),\subseteq\bigr\}$
}\label{fig::hasse_inclus}
\end{center}
\end{figure}



\subsection{Éléments remarquables}

Dans tout ce qui suit $\left( E,\leq \right) $ est un ensemble ordonné
et $A$ est une partie de $E.$



\begin{definition}
  
\begin{itemize}
\item On dit que la partie $A$ est \textbf{majorée} par $u\in E$ si, et
seulement si, on a : 
$$
\text{pour tout }x\text{ de }A,x\leq u
$$

\item On dit que la partie $A$ est \textbf{minorée} par $v\in E$ si, et
seulement si, on a : 
$$
\text{pour tout }x\text{ de }A,v\leq x
$$
\end{itemize}
\end{definition}



\begin{definition}
  On dit que $g$ est un\textbf{\ plus} \textbf{grand élément}
(ou élément maximum) de $A$ si, et seulement si, 
$$
g\in A\text{ et }\forall x\in A,x\leq g
$$

Si $g$ existe, il est unique et on ne doit pas parler d'un plus grand él
ément de $A$ mais du plus grand élément de $A$.
\end{definition}

Démontrons
ce résultat : pour cela supposons que $g$ et $g^{\prime }$ sont deux
plus grands éléments de $A,$ nous avons alors%
\begin{eqnarray*}
\forall x &\in &A,x\leq g\text{ donc }g^{\prime }\leq g \\
\forall y &\in &A,y\leq g^{\prime }\text{ donc }g\leq g^{\prime }
\end{eqnarray*}%
L'antisymétrie de $\leq $ permet alors de conclure $g=g^{\prime }.$



 Le
plus grand élément de $A$ (s'il existe) est noté $\operatorname{Max}(A)$
et c'est aussi évidemment le plus petit majorant de $A.$

\begin{definition}
On dit que $p$ est un \textbf{plus petit élément} (ou él%
ément minimum) de $A$ si, et seulement si, 
\begin{equation*}
p\in A\text{ et }\forall x\in A,p\leq x
\end{equation*}%
Si $p$ existe, il est unique et on ne doit pas parler d'un plus petit él%
ément de $A$ mais du plus petit élément de $A.$ 
\end{definition}

Le plus petit 
élément de $A$ (s'il existe) est noté $\operatorname{Min}(A)$ et c'est
alors le plus grand minorant de $A.$








\begin{definition}
  Considérons $\mathcal{G}$ l'ensemble des majorants de $A.$ Si $%
\mathcal{G}$ admet un plus petit élément $s$ c'est la \textbf{borne supérieure} de $A.$
\end{definition}


Bien remarquer que $s$ n'existe pas toujours et que s'il
existe, ce n'est pas forcément un élément de $A$ ; par contre si 
$A$ admet un plus grand élément c'est sa \textbf{borne supérieure%
}. La borne supérieure de $A$ dans $E$ est notée $\Sup_{E}(A)$ ou $%
\Sup(A).$


\begin{definition}
 Considérons $\mathcal{P}$ l'ensemble des minorants de $A.$ Si $%
\mathcal{P}$ admet un plus grand élément $i$ c'est la \textbf{borne inférieure} de $A.$
\end{definition}



Bien remarquer que $i$ n'existe pas toujours et que s'il
existe, ce n'est pas forcément un élément de $A$ ; par contre si 
$A$ admet un plus petit élément c'est sa \textbf{borne inférieure%
}. La borne inférieure de $A$ dans $E$ est notée $\Inf_{E}(A)$ ou $%
\Inf(A).$

\begin{definition}
$a\in A,$ $a$ est \textbf{maximal} dans $A$ s'il n'existe pas d'él%
ément $x\in A$ vérifiant $x\neq a$ et $a\leq x.$

$\alpha \in A,$ $\alpha $ est \textbf{minimal} dans $A$ s'il n'existe
pas d'élément $x\in A$ vérifiant $x\neq \alpha $ et $x\leq
\alpha .$
\end{definition}

Si $A$ admet un plus grand élément, ce plus grand élé%
ment est maximal et c'est le seul.


Si $A$ admet un plus petit élément, ce plus petit élé%
ment est minimal et c'est le seul.



\begin{NB}
Lorsque l'on peut représenter l'ensemble ordonné $(E,\leq )$ à
l'aide  d'un diagramme  de \textsc{Hasse},  on voit  appara\^{\i}tre les
éléments minimaux ou maximaux éventuels de $E$ ainsi que les
bornes ou é léments extrémaux éventuels de toute partie de $E.$
\end{NB}


Observons     par    exemple     le    diagramme     de     la    figure
\vref{fig::hasse_divise}. L'ensemble $\ER$ ne  possède pas de plus grand
élément ni de plus petit élément.

Cependant, 8, 12, 18  et 7 sont les éléments maximaux et  2, 3 et 7 sont
les éléments minimaux.

 La partie $W=\left\{
8,12\right\} $ de $E$ n'admet pas de majorant, il n'y a pas dans $E$ d'él%
ément simultanément \og plus grand ou égal\fg{} à 8 et 12. Il faut,
ici, entendre \og plus grand ou égal que\fg{} comme \og être un multiple de\fg{} ! 
$W$ admet un unique minorant dans $E,$ c'est 2, qui divise simultanément
8 et 12; 2 étant le \og plus grand\fg{} des minorants, c'est la borne infé%
rieure de $W$. 

La partie $V=\left\{ 2,3,6\right\} $ admet 3 majorants dans $%
E,$: ce sont 6, 12 et 18; 6 est la borne supérieure de $V,$ c'est aussi
le plus grand élément de $V.$%


\medskip


Observons  maintenant  le  diagramme  de  \textsc{Hasse}  de  la  figure
\vref{fig::hasse_inclus}.

Le plus  petit élément est  l'ensemble vide car $\{\}   \subseteq A$
pour tout partie A de $\ER=\bigl\{a,b,c\bigr\}$.

Le plus grand élément est $\ER$ car toute partie A de $ \ER$ est incluse
dans $ \ER$.


\subsection{Ensemble bien ordonné}




\begin{definition}
$(E,\leqslant )$ est un \textbf{ensemble BIEN ordonné} si $\leqslant $
est un  ordre total et si tout  sous-ensemble non vide de  E contient un
plus petit élément.
\end{definition}

Est-ce que $(\bbz,\leqslant )$ est bien ordonné?





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\modeexercice % entre en mode exercice






\section{EXERCICES}


\small
\begin{listeexercices}



\subsection{Relations binaires}

\begin{exercice}
  Donnez des relations telles que $\RR\circ\SR\neq\SR\circ\RR$.
\end{exercice}


\begin{exercice}
Déterminez  parmi les  relations suivantes  celles qui  sont réflexives,
transitives,  symétriques, antisymétriques,  irréflexives  (on précisera
les ensembles):

\begin{enumerate}
\item ...a les mêmes parents que...
\item ...est le frère de...
\item ...n'a pas le même âge que...
\item est au moins aussi grand que...
\item $x+y$ est impair
\item $x+y$ est pair
\item $xy$ est impair
\item $x+xy$ est pair
\end{enumerate}

\end{exercice}

\begin{exercice}
  Décrivez les fermetures transitives de:
  \begin{enumerate}
  \item ...a un an de plus que...
\item ...est le double de...
\item ...est le fils de...
\item ...a un lien dynamique vers la page web...
\item ...est relié par le train à...
  \end{enumerate}
\end{exercice}


\begin{exercice}
$E_{1}=\left\{ a,b,c,d\right\} ,E_{2}=\left\{ 0,1,2\right\} ,E_{3}=\left\{
\alpha ,\beta ,\gamma ,\delta ,\epsilon \right\} .$ On considére les
relations $\mathcal{R}=\left( E_{1},E_{2},G_{\mathcal{R}}\right) $ et $%
\mathcal{S}=\left( E_{2},E_{3},G_{\mathcal{S}}\right) $ avec 
\begin{eqnarray*}
G_{\mathcal{R}} &=&\left\{ (a,0),(a,1),(c,1),(d,0)\right\} \\
G_{\mathcal{S}} &=&\left\{ (1,\beta ),(2,\delta ),(2,\varepsilon )\right\}
\end{eqnarray*}


\begin{enumerate}
\item P{réciser }$\limfunc{dom}\mathcal{R}${\ et }$\limfunc{Im}%
\mathcal{R}.$

\item $\mathcal{R}${\ est-elle totale ?}

\item {Reprendre les questions précédentes avec }$\mathcal{S}%
. $

\item {Déterminer }$\mathcal{S}\circ \mathcal{R}.${\ Pr%
éciser }$\limfunc{dom}\left( \mathcal{S}\circ \mathcal{R}\right) ${\
et }$\limfunc{Im}\left( \mathcal{S}\circ \mathcal{R}\right) .$

\item {Déterminer les relations }$\mathcal{R}^{\sim}${\ et }$%
\mathcal{S}^{\sim}.$

\item {Vrai ou faux ?}

\begin{enumerate}
\item $a\mathcal{R}1$

\item $\mathcal{R}\left( b,0\right) $

\item $\left( 1,c\right) \in \mathcal{R}^{\sim}$

\item $\left( a,\beta \right) \in \mathcal{S}\circ \mathcal{R}$

\item $\left( a,\beta \right) \in \mathcal{R}.\mathcal{S}$
\end{enumerate}

\item $\mathcal{R}^{\sim}${\ est-elle une fonction ?}

\item {Déterminer la relation }$\mathcal{S}^{\sim}.\mathcal{R}%
^{\sim}. $

\item {Déterminer }$\mathcal{R}\circ \mathcal{S}.$

\item {Déterminer les relations suivantes :} $\mathcal{R}_{\mid
\left\{ a\right\} },$ $\mathcal{R}_{\mid \left\{ b\right\} },$ $\mathcal{R}%
_{\mid \left\{ a,b\right\} },$ $\mathcal{R}_{\mid \left\{ 1\right\} }^{\sim},%
\mathcal{R}_{\mid \left\{ 1\right\} }.$
\end{enumerate}


\end{exercice}



















\begin{exercice}
$\mathcal{R}=\left( E,F,G_{\mathcal{R}}\right) ${\ et }$\mathcal{R}%
^{\prime }=\left( E^{\prime },F^{\prime },G_{\mathcal{R}^{\prime }}\right) $%
{\ sont deux relations.}


\begin{enumerate}
\item {Dans quel(s) cas }$\mathcal{R}^{\sim}${\ n'existe pas ?}

\item {Dans quel(s) cas }$\mathcal{R}\circ \mathcal{R}^{\prime }$%
{\ n'existe pas ?}

\item {Dans quel(s) cas }$\mathcal{R}\circ \mathcal{R}^{\prime }$%
{\ et }$\mathcal{R}^{\prime }\circ \mathcal{R}${\ existent
simultanément ?}
\end{enumerate}

\end{exercice}








\begin{exercice}
$\mathcal{R}$ est une relation de $E$ vers $F$ dont le graphe est $G_{%
\mathcal{R}}$. Cette relation est notée%
$$
\mathcal{R}=\left( E,F,G_{\mathcal{R}}\right) \text{ avec évidemment }G_{%
\mathcal{R}}\subseteq E\times F
$$%
Si $U$ est une partie de $E$, la relation $\left( U,F,G_{\mathcal{R}}\cap
\left( U\times F\right) \right) $ est notée $\mathcal{R}_{\mid U},$
c'est la restriction de la relation $\mathcal{R}$ à la partie $U$ de $E.$
La relation $\left( E,F,G_{\mathcal{R}}\cap \left( U\times F\right) \right) $
est une sous relation de $\mathcal{R}$ qui est notée $U\vartriangleleft 
\mathcal{R},$ c'est une restriction de domaine de $\mathcal{R}$ à $U.$
Sachant que $U$ est une partie de $E$ et $V$ une partie de $F,$ définir
les relations suivantes en précisant leur ensemble de départ, leur
ensemble d'arrivée et leur graphe


\begin{enumerate}
\item $\mathcal{R}_{1}=\left( \mathcal{R}_{\mid V}^{\sim}\right) ^{\sim}.$

\item $\mathcal{R}_{2}=\left( \mathcal{R}_{\mid V}^{\sim}\right) _{\mid
U}^{\sim}.$

\item $\mathcal{R}3=\left( \left( \mathcal{R}_{\mid U}\right) _{\mid
V}^{\sim}\right) ^{\sim}.$

\item $\mathcal{R}_{4}=\left( V\vartriangleleft \mathcal{R}^{\sim}\right)
^{\sim} $ {que l'on note} $\mathcal{R}\vartriangleright V.$

\item $\mathcal{R}_{5}=U\vartriangleleft \left( V\vartriangleleft \mathcal{R}%
^{\sim}\right) ^{\sim}$ {que l'on note} $U\vartriangleleft \mathcal{R}%
\vartriangleright V.$

\item $\mathcal{R}_{6}=\left( \left( \left( U\vartriangleleft \mathcal{R}%
\vartriangleright V\right) _{\mid U}\right) _{\mid V}^{\sim}\right)
^{\sim}.\medskip $
\end{enumerate}

\end{exercice}









\begin{exercice}
$E=\left\{ a,b,c,d\right\} ,$ $F=\left\{ 1,2,3,4,5\right\} ,$ 

$G_{\mathcal{R}%
}=\left\{ \left( a,1\right) ,\left( a,2\right) ,\left( c,4\right) ,\left(
d,2\right) ,\left( d,5\right) \right\} $ et $\mathcal{R}$ est la relation de 
$E$ vers $F$ qui a pour graphe $G_{\mathcal{R}}.$

\begin{enumerate}
\item C{ombien existe-t-il de relations de }$E${\ vers }$F$%
{\ ?}

\item {Vrai ou faux ? Vous expliquerez votre réponse.}

\begin{enumerate}
\item $\mathcal{R}\in E\longleftrightarrow F$

\item $\mathcal{R}\in \mathcal{P}\left( E\times F\right) $

\item $\mathcal{R}=\left( E,F,G_{\mathcal{R}}\right) $

\item $a\mathcal{R}1${\ ; }$\left( a,1\right) \in \mathcal{R}${%
\ ; }$\mathcal{R}\left( a,1\right) $

\item $\mathcal{R}${\ est une relation totale.}

\item $\mathcal{R}${\ est une fonction.}
\end{enumerate}

\item {Déterminer un ensemble }$B${\ ayant un maximum d'%
éléments pour que }$\left( \mathcal{R}_{\mid B}^{\sim}\right) ^{\sim}$%
{\ soit une fonction.}

\item {Déterminer deux ensembles }$A${\ et }$B${\
ayant chacun un maximum d'éléments pour que }$\left( \left( \mathcal{%
R}_{\mid A}\right) _{\mid B}^{\sim}\right) ^{\sim}${\ soit une fonction
totale.}

\item {Déterminer deux ensembles }$A${\ et }$B${\
ayant chacun un maximum d'éléments pour que }$\left( \left( \mathcal{%
R}_{\mid A}\right) _{\mid B}^{\sim}\right) ^{\sim}${\ soit une fonction
totale surjective et non injective.}

\item {Déterminer deux ensembles }$A${\ et }$B${\
ayant chacun un maximum d'éléments pour que }$\left( \left( \mathcal{%
R}_{\mid A}\right) _{\mid B}^{\sim}\right) ^{\sim}${\ soit une fonction
totale injective et non surjective.}

\item {Déterminer deux ensembles }$A${\ et }$B${\
ayant chacun un maximum d'éléments pour que }$\left( \left( \mathcal{%
R}_{\mid A}\right) _{\mid B}^{\sim}\right) ^{\sim}${\ soit une fonction
totale bijective.}

\item {Déterminer un ensemble }$B${\ ayant un maximum d'%
éléments pour que }$\left( \mathcal{R}\rhd B\right) ^{\sim}${\
soit une fonction.}

\item {Déterminer un ensemble }$A${\ ayant un maximum d'%
éléments pour que }$\left( A\lhd \mathcal{R}\right) ^{\sim}${\
soit une fonction.}

\item {Déterminer un ensemble }$A${\ et un ensemble }$B$%
{\ ayant chacun un maximum d'éléments pour que }$\left(
\left( \left( \mathcal{R}_{\mid A}\right) _{\mid B}^{\sim}\right) ^{\sim}\right)
^{\sim}${\ soit une fonction totale.}

\item {Donner le résultat ou dire que l'écriture n'a pas de
sens en expliquant pourquoi :}

\begin{enumerate}
\item $\mathcal{R}\left( c\right) ,${\ }$\mathcal{R}\left( \left\{
b\right\} \right) $

\item $\mathcal{R}^{\sim}\left( 5\right) ,${\ }$\mathcal{R}^{\sim}\left(
\left\{ d\right\} \right) $

\item $\mathcal{R}^{2}=\mathcal{R}\circ \mathcal{R},${\ }$\mathcal{R}%
^{\sim}\circ \mathcal{R}$

\item $\mathcal{R}^{\sim}\left( \left\{ 6\right\} \right) $
\end{enumerate}

\item {Déterminer une relation }$\mathcal{R}^{\prime }${\
de }$E${\ vers }$F${\ de sorte que }$\mathcal{R}\cup \mathcal{R%
}^{\prime }${\ soit une relation totale.}

\item {Déterminer une relation }$\mathcal{R}^{\prime }${\
de }$E${\ vers }$F${\ de sorte que }$\mathcal{R}\cap \mathcal{R%
}^{\prime }${\ soit une fonction.}
\end{enumerate}


\end{exercice}












\begin{exercice}
$\mathcal{R}_{1}=\left( E,F,G_{\mathcal{R}_{1}}\right) $ et $\mathcal{R}%
_{2}=\left( E,F,G_{\mathcal{R}_{2}}\right) $ sont deux relations de
l'ensemble $E$ vers (ou dans) l'ensemble $F,$ $G_{\mathcal{R}_{i}}$ est le
graphe de la relation $\mathcal{R}_{i}.$ On considère la relation $%
\mathcal{R}=\left( E,F,G_{\mathcal{R}}\right) $ dont les éléments $%
\left( x,y\right) $ du graphe vérifient :%
$$
\begin{tabular}{c}
si $\left( x,y\right) \in G_{\mathcal{R}_{2}}\ $alors $\left( x,y\right) \in
G_{\mathcal{R}}$ \\ 
si $\left( x,y\right) \in G_{\mathcal{R}_{1}}\ $et pour tout $z\in F,\left(
x,\,z\right) \notin G_{\mathcal{R}_{2}}$ alors $\left( x,y\right) \in G_{%
\mathcal{R}}$%
\end{tabular}%
$$%
Il vous est demandé d'exprimer le graphe de la relation $\mathcal{R}$ en
utilisant les opérations ensemblistes usuelles et des ensembles choisis
parmi les ensembles suivants : le domaine de $\mathcal{R}_{1}$ noté $%
\limfunc{dom}\mathcal{R}_{1},$ le domaine de $\mathcal{R}_{2}$ noté $\limfunc{%
dom}\mathcal{R}_{2},$ $G_{\mathcal{R}_{1}},$ $G_{\mathcal{R}_{2}},$ $E$ et $%
F $.
\end{exercice}













\begin{exercice}
On considère les ensembles $E=\left\{ a,b,c,d\right\} $ et $F=\left\{
1,2,3\right\} $.


\begin{enumerate}
\item {Combien existe-t-il de relations de }$E${\ vers }$F$%
{\ ?}

\item {On considère les relations }$r${\ et }$s${\
suivantes :}%
\begin{eqnarray*}
r &=&\left( E,E,G_{r}\right) \\
\text{avec }G_{r} &=&\left\{ \left( a,a\right) ,\left( a,b\right) ,\left(
c\,,a\right) ,\left( b,c\right) ,\left( d,a\right) \right\} \\
s &=&\left( E,F,G_{s}\right) \\
\text{avec }G_{s} &=&\left\{ \left( b,1\right) ,\left( c,1\right) ,\left(
d,3\right) \right\}
\end{eqnarray*}%
{Pour les diagrammes qui suivent, il est exigé que l'ensemble de d%
épart soit à gauche et l'ensemble d'arrivée à droite, si la
question n'a pas de sens, d\^{\i}tes-le en expliquant pourquoi.}

\begin{enumerate}
\item {Donner un diagramme sagittal de la relation }$r\circ r=r^{2}$

\item {Donner un diagramme sagittal de la relation }$r.r^{\sim}$

\item {Donner un diagramme sagittal de la relation }$rs=r.s=s\circ r$

\item {Donner un diagramme sagittal de la relation }$\left( \left\{
1\right\} \vartriangleleft s^{\sim}\right) .\left( r^{\sim}\vartriangleright
\left\{ a,c,d\right\} \right) $

\item {Donner un diagramme sagittal de la relation }$\left( r_{\mid
\left\{ a,c\right\} }^{\sim}\right) _{\mid \left\{ a,c\right\} }^{\sim}$
\end{enumerate}

\item {Donner le résultat ou dire que l'écriture n'a pas de
sens en expliquant pourquoi :}

\begin{enumerate}
\item $r\left( d\right) =$

\item $\left( r\vartriangleright \left\{ a\right\} \right) \left( c\right) =$

\item $\left( r\vartriangleright \left\{ a\right\} \right) \left( b\right) =$

\item $r_{\mid \left\{ a\right\} }\left( \left\{ d\right\} \right) =$

\item $\left( r_{\mid \left\{ d\right\} }\right) \left( d\right) =$

\item $\left( s_{\mid \left\{ a\right\} }\right) \left( \left\{ a\right\}
\right) =$

\item $s^{\sim}\left( \left\{ 2\right\} \right) =$

\item $\left( \left\{ d\right\} \vartriangleleft r\right) \left( \left\{
a\right\} \right) =$

\item $sr\left( \left\{ 1\right\} \right) =$

\item $s^{\sim}r^{\sim}\left( \left\{ 1\right\} \right) =$

\item $r^{\sim}\left( \left\{ 2\right\} \right) =$

\item $\left( \left\{ a,b\right\} \vartriangleleft s\right) ^{\sim}\left(
1\right) =$
\end{enumerate}
\end{enumerate}

\end{exercice}



























\begin{exercice}
$E=\left\{ 12,13,33,51,111,128\right\} ,$ $F=\left\{ 2,3,4,5,6,7\right\} .$
On considére la relation $\mathcal{R}$ de $E$ vers (ou dans) $F$ dé%
finie par : $x\in E,y\in F,x\mathcal{R}y$ si, et seulement si,  la somme des chiffres utilis%
és dans l'écriture de $x$ (on travaille en base 10) est égale 
à $y.$


\begin{enumerate}
\item {Déterminer le domaine et le codomaine de }$\mathcal{R},$ 
{son graphe et donner un diagramme sagittal..}

\item $\mathcal{R}${\ est-elle une fonction ? L'écriture }$%
\mathcal{R}(33)${\ est-elle licite ?}

\item $\mathcal{R}${\ est-elle une application ?}

\item {Donner le graphe de }$\mathcal{R}^{\sim},${\ }$\mathcal{R}%
^{\sim}${\ est-elle une fonction? L'écriture }$\mathcal{R}^{\sim}(6)$%
{\ est-elle licite?}

\item {Calculer, si cela a un sens,}

\begin{enumerate}
\item $\mathcal{R}\left( 6\right) ,${\ }$\mathcal{R}\left( 12\right)
, ${\ }$\mathcal{R}\left( \left\{ 12\right\} \right) ,${\ }$%
\mathcal{R}(E)$

\item $\mathcal{R}^{\sim}\left( \left\{ 6\right\} \right) ,${\ }$%
\mathcal{R}^{\sim}(F),${\ }$\mathcal{R}^{\sim}(2),${\ }$\mathcal{R}%
^{\sim}\left( \left\{ 2\right\} \right) $
\end{enumerate}

\item {Déterminer le graphe de la restriction de }$\mathcal{R}$%
{\ à }$\left\{ 33;51\right\} $

\item $\mathcal{R}_{\mid E-\left\{ 128\right\} }${\ est-elle une
application ? Est-elle injective ? surjective ? bijective ?}
\end{enumerate}

\end{exercice}









\begin{exercice}
Donner la représentation sagittale d'une application de l'ensemble fini $%
E$ dans l'ensemble fini $F$

\begin{enumerate}
\item {non injective et non surjective ;}

\item {non injective mais surjective ;}

\item {injective mais pas surjective ;}

\item {bijective.}
\end{enumerate}
\end{exercice}







\begin{exercice}
Déterminez  si  les  fonctions  de  $\bbz$ dans  $\bbz$  suivantes  sont
injectives ou surjectives ou...?
\begin{multicols}{2}
\begin{enumerate}
\item $f(n)=n-1$;
\item $f(n)=n^2+12$;
\item $f(n)=n^3+37$;
\item $f(n)=\lfloor n/2 \rfloor$.
\end{enumerate}
\end{multicols}
\end{exercice}


\begin{exercice}
  Mêmes  questions  avec  les  fonctions de  $\bbz\times  \bbz\to  \bbz$
  suivantes:
\begin{multicols}{2}
  \begin{enumerate}
  \item $f(m,n)=2m-n$;
\item $f(m,n)=m^2-n^2$;
\item $f(m,n)=m^2+n^2$;
\item $f(m,n)=|m|-|n|$;
\item $f(m,n)=m-n$;
\item $f(m,n)=|n|$;
\item $f(m,n)=m$;
\item $f(m,n)=m^2-4$.
  \end{enumerate}
\end{multicols}
\end{exercice}












\begin{exercice}
$f$ est une application de $E$ dans $F,$ $A$ et $B$ sont deux parties de $E$
et $A^{\prime }$ et $B^{\prime }$ sont deux parties de $F.$ Démontrer :


\begin{enumerate}
\item $A\subseteq B\Rightarrow f(A)\subseteq f(B)$

\item $f(A\cup B)=f(A)\cup f(B)$

\item $f(A\cap B)\subseteq f(A)\cap f(B),$ donner un exemple où il n'y a
pas égalité.

\item $A\subseteq f^{\sim}\left( f(A)\right) $

\item $f^{\sim}(A^{\prime }\cap B^{\prime })=f^{\sim}(A^{\prime })\cap
f^{\sim}(B^{\prime })$

\item $f\left( f^{\sim}(B^{\prime })\right) \subseteq B^{\prime }$

\item $A^{\prime }\subseteq B^{\prime }\Rightarrow f^{\sim}(A^{\prime
})\subseteq f^{\sim}(B^{\prime })$

\item $f^{\sim}(A^{\prime }\cap B^{\prime })=f^{\sim}(A^{\prime })\cap
f^{\sim}(B^{\prime })$
\end{enumerate}
\end{exercice}






















\begin{exercice}
$E$, $F$ et $G$ sont 3 ensembles (tous les trois $\neq \{\}  ).$ $f\in 
\mathcal{A(}E,F),$ $g\in \mathcal{A(}F,G).$


\begin{enumerate}
\item $g\circ f${\ injective }$\Rightarrow ${\ }$f${\
injective.} ?

\item $g\circ f${\ surjective }$\Rightarrow ${\ }$g${\
surjective.} ?

\item Si $f$ et $f\circ  g$ son injectives (surjectives), est-ce que $g$
  est injective (surjective)?
\end{enumerate}


\end{exercice}














\begin{exercice}
$A$ est une partie non vide de l'ensemble $E.$ Qu'appelle-t-on l'injection
canonique de $A$ dans $E$ ?
\end{exercice}






\begin{exercice}
Démontrer que la relation transposée de la fonction totale $f=\left(
E,F,G_{f}\right) $ est une fonction si, et seulement si,  f est injective.
\end{exercice}







\begin{exercice}
$E=\left\{ a,b,c,d\right\} $ et $F=\left\{ 1,2,3,4,5,6\right\} .$ Dé%
montrer qu'il est impossible de construire une surjection et, a fortiori une
bijection, de $E$ sur $F.$
\end{exercice}








\begin{exercice}
Donner une bijection de $\mathbb{N}$ sur $\mathbb{Z}.$
\end{exercice}









\begin{exercice}
Lorsqu'on est en présence d'ensembles finis, il est facile de savoir
s'il existe des injections ou surjections entre ces ensembles puisque si
elles existent on est capable de les construire. Pour des ensembles infinis
c'est plus difficile mais on est s\^{u}r qu'il n'existe pas de surjection
entre un ensemble $E$ et l'ensemble de ses parties $\mathcal{P}\left(
E\right) ,$ c'est le théorème de Cantor\footnote{%
Ne pas confondre avec le fameux théorème de Cantor-Bernstein (qui
n'est pas à votre programme) qui dit que s'il existe une injection de $E$
vers $F$ et une injection de $F$ vers $E$ alors il existe une bijection de $%
E $ sur $F.$}, on va le démontrer :

\begin{enumerate}
\item $E=\left\{ a,b,c,d\right\} ${\ et }$f${\ est la fonction
totale de }$E${\ dans }$\mathcal{P}\left( E\right) ${\ dé%
finie par }$f\left( x\right) =\left\{ x\right\} ${, déterminer }%
$$
A=\left\{ x\in E\mid x\notin f\left( x\right) \right\}
$$

\item $E=\left\{ a,b,c,d\right\} ${\ et }$f${\ est la fonction
totale de }$E${\ dans }$\mathcal{P}\left( E\right) ${\ dé%
finie par }$f\left( x\right) =\complement _{E}\left\{ x\right\} ${, d%
éterminer }%
$$
A=\left\{ x\in E\mid x\notin f\left( x\right) \right\}
$$

\item $E=\left\{ a,b,c,d\right\} ${\ et }$f${\ est la fonction
totale de }$E${\ dans }$\mathcal{P}\left( E\right) ${\ dé%
finie par }$f\left( a\right) =\left\{ b,c\right\} ${\ et }$f\left(
x\right) =E${\ pour }$x\neq a,${\ déterminer }%
$$
A=\left\{ x\in E\mid x\notin f\left( x\right) \right\}
$$

\item $E${\ est un ensemble non vide quelconque, fini ou infini, et }$%
f${\ est une fonction totale de }$E${\ dans }$\mathcal{P}%
\left( E\right) ${\ ; }$A${\ est la partie de }$E${\ d%
éfinie par }$A=\left\{ x\in E\mid x\notin f\left( x\right) \right\} $%
{\ et pour prouver que }$f${\ n'est pas surjective nous allons
prouver que }$A${\ ne peut avoir le moindre antécédent ! Pour
cela on suppose que }$A${\ possède au moins un antécédent 
}$u,${\ }$f\left( u\right) =A.${\ De deux choses l'une, ou
bien }$u\in A${\ ou bien }$u\notin A${\ ; démontrer
l'impossibilité de chaque cas et conclure.}
\end{enumerate}

\end{exercice}


\subsection{ Relations binaires sur un ensemble}











\begin{exercice}
Commentez cet énoncé de CM1 (on progresse...)
%\begin{figure}
\begin{center}
  \includegraphics[width=\linewidth]{CM1-rel}
\end{center}
%\end{figure}

\end{exercice}














\begin{exercice}
\begin{enumerate}
\item   Donner la représentation  matricielle des relations suivantes définies
  sur $\bigl\{1,2,3,4\bigr\}$:
  \begin{enumerate}
  \item $\bigl\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\bigr\}$;
  \item $ \bigl\{(1,1),(1,4),(2,2),(3,3),(4,1)\bigr\}$;
  \item                                                                 $
    \bigl\{(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),$

        $(3,4),(4,1),(4,2),(4,3)\bigr\}$;
   \item $ \bigl\{(2,4),(3,1),(3,2),(3,4)\bigr\}$
  \end{enumerate}
\item  Quelles sont, parmi  ces relations,  celles qui  sont réflexives?
  irrefléxives? symétriques? antisymétriques? transitives?
\end{enumerate}
\end{exercice}


\begin{exercice}
  \begin{enumerate}
  \item Énumérer les couples  des relations sur $ \bigl\{1,2,3,4\bigr\}$
    définies par les matrices suivantes:
    \begin{multicols}{2}
 \begin{enumerate}
    \item
      $\begin{pmatrix}
        1&1&0&1\\
        1&0&1&0\\
        0&1&1&1\\
        1&0&1&1
      \end{pmatrix}$
\item $
  \begin{pmatrix}
    1&1&1&0\\
    0&1&0&0\\
    0&0&1&1\\
    1&0&0&1
  \end{pmatrix}
$
\item $
  \begin{pmatrix}
    0&1&0&1\\
    1&0&1&0\\
    0&1&0&1\\
    1&0&1&0
  \end{pmatrix}
$
    \end{enumerate}

  \end{multicols}
\item Quelles sont, parmi  ces relations,  celles qui  sont réflexives?
  irrefléxives? symétriques? antisymétriques? transitives?
  \end{enumerate}
\end{exercice}

\begin{exercice}
  Combien  d'éléments  non  nuls  contient la  matrice  représentant  la
  relation $  \RR$ sur l'ensemble  $ \ER=\bigl\{1,2,3,...,100\bigr\}$ si
  $\RR$ est:
  \begin{multicols}{2}
    \begin{enumerate}
    \item $ \bigl\{(a,b)\mid a>b\bigr\}$; \item $ \bigl\{(a,b)\mid a\neq
      b\bigr\}$;
\item  $   \bigl\{(a,b)\mid  a=b+1\bigr\}$;  \item   $  \bigl\{(a,b)\mid
  a=0\bigr\}$;
\item $ \bigl\{(a,b)\mid ab=0\bigr\}$;
\item $ \bigl\{(a,b)\mid a+b=100\bigr\}$
    \end{enumerate}
    
  \end{multicols}
\end{exercice}

\begin{exercice}
Soit  $\RR=\bigl\{(a,b)\in  \bbz^2  \mid  a\neq  b\bigr\}$  Quelle  est  la
fermeture réflexive de $\RR$?
\end{exercice}

\begin{exercice}
Soit $\RR=\bigl\{(a,b)\in \bbn^2 \mid a \text{ divise }b\bigr\}$ Quelle est la
fermeture symétrique de $\RR$?
\end{exercice}



\begin{exercice}
  Soit $\ER=\bigl\{1,2,3,4,5\bigr\}$ et $\RR$ une relation sur $\ER$ qui
  contient  les  couples $(1,3)$,  $(2,4)$,  $(3,1)$, $(3,5)$,  $(4,3)$,
  $(5,1)$, $(5,2)$ et $(5,4)$. Déterminer:

  \begin{multicols}{3}
    \begin{enumerate}
    \item $\RR^2$ \item $\RR^3$ \item $\RR^4$
    \item $\RR^5$ \item $\RR^6$ \item $\RR^+$
    \end{enumerate}
  \end{multicols}


\end{exercice}










\begin{exercice}
On considère les relations binaires $\mathcal{R}$ et $\mathcal{S}$ sur $%
E=\left\{ a;b;c;d;e\right\} $ qui ont pour graphe : 
\begin{eqnarray*}
G_{\mathcal{R}} &=&\left\{ (a,a),(a,b),(b,c),(c,b),(e,b)\right\} \\
G_{\mathcal{S}} &=&\left\{ (a,a),(b,a),(b,b),(c,b),(e,b),(e,d)\right\}
\end{eqnarray*}

\begin{enumerate}
\item {Donner une représentation sagittale de }$\mathcal{R}$%
{\ et de }$\mathcal{S}.$

\item {Déterminer le graphe de }$\mathcal{R}\cup \mathcal{S},$%
{\ de }$\mathcal{R}\cap \mathcal{S},${\ de }$\overline{%
\mathcal{R}},${\ de }$\mathcal{S}^{\sim},${\ de }$\mathcal{RS}$%
{\ de }$\mathcal{SR}.$

\item {Déterminer le graphe de }$\mathcal{R}^{+}${\ et de }%
$\mathcal{S}^{\ast }.$
\end{enumerate}
\end{exercice}


\begin{exercice}
$\mathcal{R}$ est une relation binaire sur l'ensemble $E$ et on supose que $%
\mathcal{R}$ n'est pas une relation vide.

\begin{enumerate}
\item {Rappeler ce qu'est }$\mathcal{R}^{k\in \mathbf{N}^{\ast }}.$

\item {Rappeler ce qu'est }$\mathcal{R}^{+}.$

\item {Rappeler ce qu'est }$\mathcal{R}^{\ast }.$

\item {Démontrer que si }$x\mathcal{R}^{9}z${\ et }$z%
\mathcal{R}^{2001}y${\ alors }$x\mathcal{R}^{\ast }y$

\item {Traduire correctement }$x\mathcal{R}^{\ast }y.$

\item {Démontrer que }$\mathcal{R}^{\ast }${\ est une
relation transitive.}
\end{enumerate}
\end{exercice}


\begin{exercice}
$\mathcal{R}$ est une relation binaire sur $E$

\begin{enumerate}
\item {Démontrer que }$\mathcal{R}\cup \mathcal{R}^{\sim}${\
et }$\mathcal{R}\cap \mathcal{R}^{\sim}${\ sont symétriques.}

\item {Démontrer que }$\mathcal{R}^{+}${\ est transitive.}

\item {Démontrer que si }$\mathcal{R}${\ est transitive
alors }$\mathcal{R}=\mathcal{R}^{+}.$

\item {Démontrer que si }$\mathcal{R}${\ est réflexive
et transitive alors }$\mathcal{R}=\mathcal{R}^{\ast }$
\end{enumerate}
\end{exercice}



\begin{exercice}
$\mathcal{R}$ est une relation binaire sur $E=\left\{ a,b,c,d,e\right\} $
dont le graphe est 
\begin{equation*}
G=\left\{ \left( a,a\right) ,\left( a,b\right) ,\left( a,c\right) ,\left(
b,a\right) ,\left( d,a\right) ,\left( b,e\right) \right\}
\end{equation*}

\begin{enumerate}
\item {Complétez l'écriture : }$G\in $

\item {Déterminer le graphe de }$\mathcal{R}^{2}.$

\item {Déterminer le graphe de }$\mathcal{R}^{3},$ {dé%
terminer le graphe de }$\mathcal{R}^{k\geq 2}.$

\item {Quel est le graphe de }$\mathcal{R}^{0}${\ ?}

\item {Quel est le graphe de }$\mathcal{R}^{+}?$

\item {Quel est le graphe de }$\mathcal{R}^{\ast }${\ ?}

\item $\mathcal{R}^{\ast }${\ est-elle transitive ? justifier votre r%
éponse.}

\item {Déterminer le graphe de }$\mathcal{R}^{\sim},${\ de }$%
\mathcal{R}^{-k},${\ }$k\in N^{\ast }.$
\end{enumerate}

\end{exercice}






\subsection{Relations d'équivalence}



\begin{exercice}
Dans $\mathbb{Z}$ on considère la relation $x\mathcal{R}y\Leftrightarrow
x-y\in 3\mathbb{Z}=\left\{ 3k\mid k\in \mathbb{Z}\right\} .$ Démontrer
que c'est une relation d'équivalence et déterminer l'ensemble
quotient ; vérifier que l'ensemble quotient détermine une partition
de $\mathbb{Z}.$
\end{exercice}



\begin{exercice}
$E$ est un ensemble non vide et $A$ est une partie non vide fixée de $E.$
On considére la relation binaire $\mathcal{R}$ sur $\mathcal{P}\left(
E\right) $ définie par : 

$$X\mathcal{R}Y\Leftrightarrow X\cap A=Y\cap A$$

\begin{enumerate}
\item \textit{Démontrer que }$\mathcal{R}$\textit{\ est une relation d'%
équivalence.}

\item \textit{On suppose ici que }$E=\left\{ a,b,c,d\right\} $\textit{\ et }$%
A=\left\{ a,d\right\} .$\textit{\ Déterminer toutes les classes d'é%
quivalence.}
\end{enumerate}

\end{exercice}



\begin{exercice}
Soit $ \ER$ l'ensemble des fonctions dérivables de $\bbr$ dans $\bbr$.

On considère la relation $\RR$ définie sur $\ER$ qui contient toutes les
couples $(f,g)$ tels que $f'(x)=g'(x)$ pour tout réel $x$.

\begin{enumerate}
\item Est-ce que $\RR$ est une relation d'équivalence?
\item Décrire la classe de $f:x\mapsto x^2$.
\end{enumerate}
\end{exercice}

\subsection{Ordre}



\begin{exercice}
On considère la relation $\preceq $ sur $\mathbb{N}^{2}$ définie par
: 
$$
(a;b)\preceq (a^{\prime };b^{\prime })\Leftrightarrow a\leq a^{\prime }\text{
et }b\geq b^{\prime }
$$
Est-elle une relation d'ordre ?
\end{exercice}

\begin{exercice}
$E$ est un ensemble totalement ordonné par $\leq .$ On considére la
relation binaire sur $E^{2}$ définie par : 
$$
(x,y)\preceq (x^{\prime },y^{\prime })\Leftrightarrow \left\{ 
\begin{array}{l}
x<x^{\prime }\text{ ou} \\ 
x=x^{\prime }\text{ et }y\leq y^{\prime }%
\end{array}%
\right.
$$
Démontrer que c'est une relation d'ordre total. Cet ordre porte le nom
d'ordre lexicographique, expliquer pourquoi ?
\end{exercice}

\begin{exercice}
Dans $\mathbb{N}^{\ast }$ on considère la relation notée \og $\mid $\fg{}
qui est  la relation \og  divise\fg{}, $a\mid b$  se lit \og  $a$ divise
$b$\fg{} ou encore \og $%
b $ est un multiple de $a$\fg{}; la définition mathématique de cette
relation étant%
$$
a\mid b\text{ si, et seulement si,  il existe }k\in \mathbb{N}^{\ast }\text{ vérifiant }%
b=ka
$$

\begin{enumerate}
\item {Démontrer que c'est une relation d'ordre sur }$\mathbb{N}%
^{\ast }.${\ Cet ordre est-il total ? Donner des éléments
comparables et non comparables.}

\item {Démontrer que c'est une relation d'ordre sur toute partie }%
$A${\ de }$N^{\ast }.$

\item {On considère la relation divise dans }$E=\left\{
2,4,6,8,10,12\right\} .$

\begin{enumerate}
\item {Construire le diagramme sagittal de cette relation.}

\item {Construire le diagramme de Hasse de cette relation.}

\item $E${\ admet-il un élément minimum ?}

\item $E${\ admet-il un élément maximum ?}

\item $E${\ admet-il des éléments minimaux ?}

\item $E${\ admet-il des éléments maximaux ?}

\item $V=\left\{ 2,4\right\} ,${\ donner trois majorants de }$V$%
{\ dans }$E.$

\item $T=\left\{ 8,10\right\} ${\ admet-il des majorants dans }$E$%
{\ ? Donner des majorants de }$T${\ dans }$\mathbb{N}^{\ast }.$

\item {Donner des minorants de }$T${\ dans }$E.$

\item {Donner tous les minorants de }$T${\ dans }$\mathbb{N}%
^{\ast }.$

\item $U=\left\{ 4,6,8\right\} ${\ admet-il une borne supérieure
dans }$E${\ ?}

\item $U=\left\{ 4,6,8\right\} ${\ admet-il une borne supérieure
dans }$\mathbb{N}^{\ast }${\ ?}

\item $U=\left\{ 4,6,8\right\} ${\ admet-il une borne inférieure
dans }$E${\ ?}

\item $U=\left\{ 4,6,8\right\} ${\ admet-il une borne inférieure
dans }$\mathbb{N}^{\ast }$?
\end{enumerate}


\end{enumerate}

\end{exercice}









\begin{exercice}
$(E,\leq )$ est un ensemble ordonné. Représenter les différents
diagrammes  de  Hasse  pour  un  ensemble  $E$  de  trois  éléments.  On
précisera,  pour chaque diagramme  si $E$  est totalement  ordonné. Même
question pour un ensemble de 4 éléments.
\end{exercice}





\begin{exercice}
$\mathbb{R}$ est muni de sa relation d'ordre habituelle et $\mathbb{R}^{2}$
est ordonné comme produit direct des ensembles ordonnés $\left( 
\mathbb{R},\mathbb{\leq }\right) $ et $\left( \mathbb{R},\mathbb{\leq }%
\right) .$ Le plan $P$ est rapporté à un repère orthonormé $%
\left( O,\overrightarrow{i},\overrightarrow{j}\right) $ et on pourra
confondre tout point $M$ du plan, qui a pour coordonnées $x$ et $y$ dans
ce repère, avec le couple $(x,y)$ de $\mathbb{R}^{2}.$ Cela permet
d'ordonner $P$ par la relation : 
$$
M_{1}\preceq M_{2}\Leftrightarrow (x_{1},y_{1})\leq (x_{2},y_{2})
$$
$\mathcal{C}$ désigne le cercle de centre $O$ et de rayon 1, $\mathcal{D}
$ désigne le disque de centre $O$ et de rayon 1.

\begin{enumerate}
\item {Donner 5 majorants et 5 minorants de }$\mathcal{C}${\
et de }$\mathcal{D}.$

\item $\mathcal{C}${\ et }$\mathcal{D}${\ admettent-ils une
borne sup ? une borne inf ? un plus petit élément ? un plus grand 
élément?}

\item {On note }$\mathcal{D}^{+}${\ l'ensemble des points de }$%
\mathcal{D}${\ qui ont leurs deux coordonnées positives ou
nulles, }$\mathcal{D}^{+}${\ admet-il un plus petit élément ?}
\end{enumerate}

\end{exercice}








\begin{exercice}
Vérifier que $\left( \mathcal{P}(E),\subseteq \right) $ est bien un
ensemble ordonné. Soit $\left\{ A,B\right\} $ une partie de $\mathcal{P}%
(E),$ déterminer sa borne sup et sa borne inf dans $\mathcal{P}\left(
E\right) .$
\end{exercice}

\begin{exercice}
$\mathbb{N}_{10}$ est ordonné par la relation de divisibilité
(rappel : $\mathbb{N}_{10}=\left\{ 1,2,\cdots ,10\right\} $).

\begin{enumerate}
\item {Tracer le diagramme sagittal de cette relation puis son
diagramme de Hasse.}

\item $\mathbb{N}_{10}${\ admet-il un plus petit élément, un
plus grand élément ?}

\item {étudier les éléments remarquables (plus petit 
élément, majorant, borne sup, }$\cdots )${\ des parties de }$%
\mathbb{N}_{10}${\ suivantes :}

\begin{enumerate}
\item $A=\left\{ 1,3,6\right\} $

\item $B=\left\{ 2,3\right\} $

\item $C=\left\{ 2,3,4\right\} $

\item $D=\left\{ 2,4\right\} $
\end{enumerate}
\end{enumerate}

\end{exercice}



\vfill\eject


\subsection*{CAML}

\subsubsection*{Le type relation}


On  reprend la  représentation donnée  dans le  cours utilisant  le type
\texttt{ens} construit au début du module.


\begin{lstlisting}[caption={}]
type ('a,'b) relation =
  Rel of ('a * 'b ens)  ens ;;
\end{lstlisting}

On a donc une construction arborescente d'une relation, plus précisément
sous forme de peigne:


\begin{lstlisting}[caption={}]
let r =  Rel
   (Ens
      ((1, Ens ('a', Ens ('b', Vide))),
       Ens((2, Ens ('c', Vide)),
           Ens((3, Ens ('b', Vide)),
               Ens((4, Vide),
		   Ens ((5, Ens ('b', Vide)),
			Vide))))));;
\end{lstlisting}



Il sera malgré tout plus pratique  de rentrer une relation sous la forme
d'une  liste de  couples  \texttt{(sommet,liste des  images)} mais  nous
aurons  d'abord besoin  d'une fonction  qui calcule  la réunion  de deux
relations qui sera calculée plus tard.


Pour faciliter la \textbf{lecture} d'une relation, nous allons créer une
fonction qui  \og affiche\fg{}  la relation sous  forme d'une  liste. On
utilise  \texttt{fst}  et  \texttt{snd}  qui donnent  respectivement  la
première et la seconde composante d'un couple.

\begin{lstlisting}[caption={}]
let rec liste_of_ensemble = function
  |Vide -> []
  |Ens(t,q) -> t::(liste_of_ensemble q);;


let rec liste_of_relation rel =
  match rel with
  |Rel(Vide) -> []
  |Rel(Ens(tete,queue)) -> (fst tete,liste_of_ensemble (snd tete))::(liste_of_relation (Rel(queue)));;
\end{lstlisting}

Par exemple dans l'interpréteur:

\begin{lstlisting}[caption={}]
# liste_of_relation r;;
- : (int * char list) list =
[(1, ['a'; 'b']); (2, ['c']); (3, ['b']); (4, []); (5, ['b'])]
\end{lstlisting}


\subsubsection*{Images et antécédents}

Créez  une  fonction  \texttt{domaine}  qui  renvoie  le  domaine  d'une
relation:


\begin{lstlisting}[caption={}]
# domaine r;;
- : int ens = Ens (1, Ens (2, Ens (3, Ens (4, Ens (5, Vide)))))
\end{lstlisting}


Faites de même pour le codomaine:


\begin{lstlisting}[caption={}]
# codomaine r;;
- : char ens = Ens ('a', Ens ('c', Ens ('b', Vide)))
\end{lstlisting}


Vous utiliserez les fonctions \texttt{ajoute} et \texttt{union} mises au
point pour le type \texttt{ens}.

Créez  une  fonction \texttt{ens\_images  relation  sommet} qui  renvoie
l'ensemble des images de \texttt{sommet} par \texttt{relation}:

\begin{lstlisting}
# ens_images r 1;;
- : char ens = Ens ('a', Ens ('b', Vide))
\end{lstlisting}


Créez  une  fonction \texttt{a\_images  relation  s1  s2}  qui teste  si
\texttt{s2} est une image de \texttt{s1} par \texttt{rel} puis une fonction
\texttt{a\_antecedent s2 s1} qui  teste si \texttt{s1} est un antécédent
de \texttt{s2} par \texttt{rel}.


\begin{lstlisting}[caption={}]
# a_antecedent r 'a' 1;;
- : bool = true
\end{lstlisting}




% Pour cela,
% nous avons  d'abord besoin d'une  fonction \texttt{ensemble\_of\_liste}
% qui transforme une liste en ensemble:

% \begin{lstlisting}[caption={}]
% let rec ensemble_of_liste liste =
%   match liste with
%   |[] -> Vide
%   |t::q -> Ens(t,ensemble_of_liste q);;
% \end{lstlisting}


% Puis la fonction \texttt{relation} proprement dite:


% \begin{lstlisting}[caption={}]
% let rec relation liste =
%   match liste with
%   |[] -> Rel(Vide)
%   |tete::queue -> rel_union (Rel(Ens((fst tete,ensemble_of_liste (snd tete)),Vide))) (relation queue);;
% \end{lstlisting}


\subsubsection*{Réunion de relations}



Analysez les fonctions suivantes:

\begin{lstlisting}[caption={}]
let rec fusionne_image_ens couple ens_couples =
  match ens_couples with
  |Vide -> Ens(couple,Vide)
  |Ens(t,q) ->
    if fst t = fst couple then Ens((fst t,union (snd t) (snd couple)) ,q)
    else Ens(t,fusionne_image_ens couple q);;

let fusionne_image_rel couple relation =
    match relation with
    |Rel(Vide) -> Rel(Ens(couple,Vide))
    |Rel(Ens(a,b)) -> Rel(ajoute couple (Ens(a,b)));;

let rec rel_union r1 r2 =
    match r1 with
    |Rel(Vide) -> r2
    |Rel(Ens(tete,queue)) -> rel_union (Rel(queue)) (fusionne_image_rel tete r2);;

let (+@) r1 r2 = rel_union r1 r2;;
\end{lstlisting}





On aura besoin d'obtenir la  liste fusionnée des images par $\mathcal R$
des éléments d'un ensemble de sommets:

\begin{lstlisting}[caption={}]
let rec images_d_un_ens rel ens =
...
\end{lstlisting}


Par exemple:

\begin{lstlisting}[caption={}]
# images_d_un_ens r (Ens(1,Ens(2,Ens(3,Vide))));;
- : char ens = Ens ('a', Ens ('c', Ens ('b', Vide)))
\end{lstlisting}


On peut  alors créer une fonction  qui renvoie la  relation $\mathcal R$
suivie de $\mathcal S$:

\begin{lstlisting}[caption={}]
let suivie_de r s =
...
\end{lstlisting}

Puis sous forme infixe:


\begin{lstlisting}[caption={}]
let (@@) r s = suivie_de r s;; (* opérateur infixe de la composition *)
\end{lstlisting}




On peut itérer la composition:

\begin{lstlisting}[caption={}]
let rec iter_compo r n =
...
\end{lstlisting}



\subsubsection*{Inclusion de relations}

Tester  l'inclusion  de  deux  relations  c'est tester  celle  de  leurs
graphes. Nous  avons donc besoin de  créer le produit  cartésien de deux
ensembles. À quoi peuvent servir ces deux fonctions:

\begin{lstlisting}[caption={}]
let rec couples el ens =
  match ens with
    |Vide -> Vide
    |Ens(t,q) -> Ens((el,t),couples el q);;


let rec produit_cart ens1 ens2 =
  match ens1 with
    |Vide -> Vide
    |Ens(t,q) -> union (couples t ens2) (produit_cart q ens2);;
\end{lstlisting}

Comment les utiliser pour le test d'inclusion?




\subsubsection*{Propriétés des relations}

% \paragraph*{Fermeture transitive}



% On utilise le fait que $\mathcal  R^+$ est la réunion des $\mathcal R^k$
% pour $k\in \bigl\{1,..,n\bigr\}$, avec $n$ le cardinal de l'ensemble sur
% lequel est défini $\mathcal R$.
 
% \begin{lstlisting}[caption={}]
% let r_plus r =
% ...
% \end{lstlisting}


% \paragraph*{Fermeture transitive et réflexive}


% On forme $\mathcal R^+ \cup  \mathcal I_E$. On crée d'abord une fonction
% calculant la relation identité sur le domaine de définition de $\mathcal R$:

% \begin{lstlisting}[caption={}]
% let id r =
% ...
% \end{lstlisting}



% puis $\mathcal R^\star=\mathcal R^+ \cup \mathcal I_E$:

% \begin{lstlisting}[caption={}]
% let r_star r =
% ...
% \end{lstlisting}



\paragraph*{test \og pour tout\fg{}}

Nous aurons  besoin de tester si  tous les éléments du  domaine vérifient un
certain prédicat. Vous allez  donc créer une fonction \texttt{pour\_tout
pred ens}  qui teste si tous  les éléments de  \texttt{ens} vérifient le
prédicat \texttt{pred}.

Vous obtiendrez alors:

\begin{lstlisting}[caption={}]
# let positif nb  =
  nb >= 0;;
  val positif : int -> bool = <fun>

# let ensemble_1 = Ens(-1,Ens(1,Ens(2,Ens(3,Vide))));;
val ensemble_1 : int ens = Ens (-1, Ens (1, Ens (2, Ens (3, Vide))))

# pour_tout positif ensemble_1;;
- : bool = false
\end{lstlisting}


\paragraph*{Test de réflexivité}

On teste si chaque sommet appartient à son image:

\begin{lstlisting}[caption={}]
let est_reflexive1 r =
...
\end{lstlisting}

\begin{lstlisting}[caption={}]
# let u = relation ([
                (1,[1]);
                (2,[1;2]);
                (3,[2]);
                (4,[]);
                (5,[2;4])
                ]);;
val u : (int, int) relation

# est_reflexive u;;
- : bool = false
\end{lstlisting}

\paragraph*{Test de transitivité}

On teste si $\mathcal R^2 \subseteq \mathcal R$:

\begin{lstlisting}[caption={}]
let est_transitive r =
...
\end{lstlisting}




\paragraph*{Test de symétrie}

Teste si chaque sommet 
      appartient à la liste des images de ses images par $\mathcal R$:

\begin{lstlisting}[caption={}]
let est_symetrique r =
...
\end{lstlisting}



\begin{lstlisting}[caption={}]
# let v = relation ([
                (1,[1;2]);
                (2,[1;2;3;5]);
                (3,[2]);
                (4,[5]);
                (5,[2;4])
                ]);;
val v : (int, int) relation

# est_symetrique v;;
- : bool = true
\end{lstlisting}







On peut  tester aussi l'antisymétrie:  aucun sommet a n'appartient  à la
liste des images de ses images par $\mathcal R$:

\begin{lstlisting}[caption={}]
let est_antisymetrique r =
...
\end{lstlisting}






% \subsubsection*{Transposée}






% On utilise \texttt{find\_all pred liste} qui renvoie la
% liste de tous les éléments vérifiant le prédicat \texttt{pred}.

% On parcourt alors les sommets et on filtre ceux qui ont pour antécédent
% le sommet étudié.

% On crée d'abord  une fonction qui teste si  \texttt{s1} est un antécédent
% de \texttt{s2}:


% \begin{lstlisting}[caption={}]
% let a_antecedent r s2 s1 =
% ...
% \end{lstlisting}



% puis:

% \begin{lstlisting}[caption={}]
% let transposee r =
% ...
% \end{lstlisting}


\subsubsection*{Fonctions}



La  relation  est une  fonction  si, et  seulement  si,  la longueur  de
l'ensemble des images de chaque élément de son domaine est inférieure à 1:

\begin{lstlisting}[caption={}]
let est_fonction r =
...
\end{lstlisting}



Créez ensuite une fonction qui teste si une fonction est totale:


\begin{lstlisting}[caption={}]
let est_totale r =
...
\end{lstlisting}








On aura par la suite besoin de la fonction suivante: que fait-elle?....

\begin{lstlisting}[caption={}]
let trouve_tout pred ens  = 
  let  rec remplit pred ens panier =
  match ens with
    |Vide -> panier
    |Ens(t,q) ->
      if pred t then remplit pred q (ajoute t panier) 
      else remplit pred q panier
  in remplit pred ens Vide ;;
\end{lstlisting}


et celle-ci?...

\begin{lstlisting}[caption={}]
let transposee r =
  let rec recherche_antecedents ens =
    match ens with
    |Vide -> Rel(Vide)
    |Ens(tete,queue) ->
      fusionne_image_rel (tete, trouve_tout (a_antecedent r tete) (domaine r)) (recherche_antecedents queue)
  in recherche_antecedents (codomaine r);;
\end{lstlisting}











Une relation est injective si, et seulement si, sa transposée est une ...:


\begin{lstlisting}[caption={}]
let est_injective r =
...
\end{lstlisting}



Une relation est surjective si, et seulement si, sa transposée est ...:

\begin{lstlisting}[caption={}]
let est_surjective r =
...
\end{lstlisting}





ou si, et seulement si, sa transposée suivie d'elle-même est ...:

\begin{lstlisting}[caption={}]
let est_surjective2 r =
....
\end{lstlisting}

Enfin:

\begin{lstlisting}[caption={}]
let est_bijective r =
...
\end{lstlisting}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{listeexercices}
\modenormal % restaure les définitions de sections, sous-sections, etc.

%%% Local Variables: 
%%% TeX-master: "Poly_ERCB_2012"
%%% End: 
