pgcd, euclide,...

[cours-maths-dis.git] / ensembles / Correspondances2.tex

\setcounter{Exo}{0}
\setcounter{Def}{0}
\setcounter{Th}{0}
\setcounter{Rem}{0}
\setcounter{Notation}{0}
\setcounter{Ex}{0}

\chapter{Correspondances entre ensembles}

\section{Relations binaires entre ensembles}


\subsection{Définition}
On se donne deux ensembles $E$ et $F$.


\begin{Def}[Relation binaire, graphe]
On dit que :
 \begin{itemize}
\item l'on a défini une \emph{relation binaire} \index{relation binaire} ${\mathcal{R}}$ entre ces deux ensembles lorsqu'on s'est donné une partie $G$ de l'ensemble produit $E\times F$ (: $G\sse E\times F$).
\item Cette partie est appelée \emph{graphe} \index{graphe} de la relation binaire.
\item Si $x (\in E)$ et $y (\in F)$ sont tels que $(x,y)\in G$, on dit que $x$ est \emph{en relation avec} $y$ par la relation ${\mathcal{R}}$.
 \end{itemize}
\end{Def}


On utilise, pour formaliser cette proposition, la notation $x {\mathcal{R}} y$. Donc :

\begin{Notation}
$$x {\mathcal{R}} y\quad\hbox{[\og x est en relation avec y\fg{}  ]}\Ssi
(x,y)\in G\quad\hbox{[$G$: graphe de la relation ${\mathcal{R}}$]}.$$
\end{Notation}

\begin{Rem}
Lorsque $E=F$, on parle de relation binaire définie dans l'ensemble $E$.
Son graphe est une partie de $E^2$.
\end{Rem}

\begin{Rem}
Il est possible que $x \mathcal{R} y$ sans que $y \mathcal{R} x$.
\end{Rem}


\begin{Exo}
Sur l'ensemble des mots de la langue française, on définit la relation : \og le mot M est lié au mot N s'ils coïncident après qu'on ait retourné l'ordre des lettres de M \fg{}.

Déterminer quelques couples de mots en relation, ainsi que des mots en relation avec eux-mêmes.
\end{Exo}


\begin{Exo}
Sur l'ensemble $\Z$ des entiers relatifs, on définit deux relations, notées respectivement $\Sigma$ et $\Delta$, de la façon suivante :
\begin{itemize}
 \item $x \Sigma y$ quand la somme $x+y$ est paire
\item  $x \Delta y$ quand la différence $x-y$ est paire
\end{itemize}
Sont-elles égales ?
\end{Exo}

\noindent\textit{\underline{Réponse : }} $x \Sigma y \Leftrightarrow x+y = 2k \Leftrightarrow x+y-2y = 2k-2y.$

Donc $x \Sigma y \Leftrightarrow x-y = 2(k-y) = 2k' \Leftrightarrow x \Delta y.$


\subsection{Application d'un ensemble dans un autre}

\subsubsection{Définition d'une application}

\begin{Def}[Application]
Une \emph{application}\index{application} de l'ensemble $E$ dans l'ensemble $F$ est une relation binaire particulière ${\mathcal{R}}$ entre $E$ et $F$, dont le graphe doit posséder les propriétés suivantes :

\begin{itemize}
 \item pour tout élément $x$ de $E$, il doit exister un élément $y$ de $F$ tel que $(x,y)$ soit élément de $G$,
 \item cet élément $y$ doit être unique.
\end{itemize}
\end{Def}



\noindent Voici la formalisation (partielle) de ces propositions :

\begin{itemize}
\item $\qqs x\in E,\ \exi y\in F,\ (x,y)\in G$
\item $\qqs x\in E,\ \qqs y\in F,\ \qqs y'\in F, [(x,y)\in G\ {\rm
et}\ (x,y')\in G\Ssi y=y']$.\\
\end{itemize}

Il existe un intermédiaire entre relation et application...

\begin{Def}[Relation fonctionnelle]
On parle de \emph{relation fonctionnelle}\index{relation!fonctionnelle} quand tout élément de l'ensemble de départ possède au plus une image.
\end{Def}

\begin{Rem}
Une application est donc une relation fonctionnelle particulière : tout élément de l'ensemble de départ possède exactement une image.
\end{Rem}


\begin{Exo}
Parmi les relations suivantes de $\mathbb{R}$ vers $\mathbb{R}$, repérez les relations fonctionnelles, repérez les applications :
\begin{enumerate}
\item $\mathcal{R} = \{ (x,y) \in \mathbb{R}^2, |y| = \sqrt{x} \}$
\item $\mathcal{R} = \{ (x,y) \in \mathbb{R}^2, xy = 1 \}$
\item $\mathcal{R} = \{ (x,y) \in \mathbb{R}^2, y-x+2 = 0 \}$
\end{enumerate}
\end{Exo}

\noindent\textit{\underline{Réponse :}} Les deux dernières sont des relations fonctionnelles, et la dernière est la seule application. 

\subsubsection{Image d'un élément}

Pour un $x$ donné de $E$, il lui correspond un et un seul $y$ de $F$ qui est en relation avec lui par ${\mathcal{R}}$.

\begin{Def}
Cet unique $y$ est alors appelé \emph{image}\index{image} de $x$ par l'application définie par ${\mathcal{R}}$ dans un tel cas.
\end{Def}

\begin{Notation}
Si l'on désigne par $f$ cette application, l'expression \og $y$ est l'image de $x$ par $f$\fg{} est formalisée par $y=f(x)$.
\end{Notation}


\begin{Notation}
 On formalise la proposition \og $f$ est une application de $E$ dans $F$\fg{} par $f: E\vers F$, et la proposition \og $y$ est l'image de $x$ par $f$\fg{}   peut aussi être traduite par: $f: x \fc y$.
\end{Notation}



\begin{Exo}
 Interpréter chacune des situations suivantes au moyen d'une application. Pour cela, on définira deux ensembles $A$ et $B$ ainsi que $f: A\vers B$.

\begin{enumerate}
 \item Le résultat d'une course de tiercé.
\item Le registre d'un hôtel qui possède 55 chambres.
\item Le numéro d'INSEE.
\item La parité d'un entier naturel.
\item Un emploi du temps.
\end{enumerate}

\end{Exo}

 
Réciproquement...



\subsubsection{Applications injectives}

\begin{Def}[Antécédent]
Si $y$ est l'image de $x$ par $f$, alors $x$ est appelé \emph{antécédent} \index{antécédent} de $y$ par $f$.
\end{Def}

\begin{Th}[Nombre d'antécédents, définition de l'injectivité]
 L'antécédent de $y$ n'est pas nécessairement unique. S'il l'est, l'application $f$ est dite \emph{injective} \index{application!injective}.
\end{Th}

Sous forme (partiellement) formalisée:
$$\hbox{\og $f$ est (une application) injective\fg{}  } \Ssi [ f(x)=f(x') \Imp x=x' ]$$

\begin{Exo}
Tracez le graphe d'une application qui est injective, et d'une application qui ne l'est pas. On le fera entre ensembles finis, et entre ensembles infinis.
\end{Exo}

\begin{Exo}
Donnez des exemples (sous forme analytique) de fonctions injectives, et de fonction qui ne le sont pas.
\end{Exo}


\begin{Rem}
Le terme injection\index{injection} est synonyme d'\og application injective\fg{}. 
\end{Rem}

\begin{Rem}
Un bon algorithme de hachage, comme on en utilise dans les antivirus, dans emule et pour la recherche des titres d'un CD musical, doit éviter les collisions. Idéalement, il devrait être injectif.
\end{Rem}


\begin{Exo}
On suppose $g o f$ injective. Montrer que $f$ est injective. Est-ce que $g$ est obligatoirement injective ?
\end{Exo}


\subsubsection{Applications surjectives}


La définition d'une application $f$ exige seulement que chaque élément $x$ de $E$ admette une image (unique) $y$ dans $F$, mais pas que tout élément $y$ de $F$ admette un antécédent dans $E$.\\


S'il en est néanmoins ainsi, l'application est dite surjective :
\begin{Def}
Une application \emph{surjective}\index{application!surjective} $f: E\vers F$ est une application telle que tout $y$ de $F$ admette un antécédent dans $E$.\\
\end{Def}

\begin{Rem}
\emph{Surjection} est synonyme d'\og application surjective\fg{}. \index{surjection}. 
\end{Rem}


\begin{Exo}
Tracez le graphe d'une application qui est surjective, et d'une application qui ne l'est pas. On le fera entre ensembles finis, et entre ensembles infinis.
\end{Exo}

\begin{Exo}
Donnez des exemples (sous forme analytique) de fonctions surjectives, et de fonction qui ne le sont pas.
\end{Exo}


D'une manière générale, on peut considérer l'ensemble des images des éléments de $E$ par une application $f$ de $E$ dans $F$ (ils en ont tous une, et une seule).\\


Cet ensemble, qui est évidemment une partie de $F$, est noté $f<E>$, et est appelé image de $E$ par $f$ : $f<E>=\{f(x)\in F \mid x\in E\}$.\\


Si tous les éléments de $F$ ont un antécédent dans $E$ ($f$ est surjective), cela signifie que tout élément de $F$ est élément de $f<E>$, donc que $F\sse f<E>$; comme on a remarqué par ailleurs que $f<E>\sse F$, on a, dans ce cas, $f<E>=F$.\\


Cette dernière remarque autorise la formalisation suivante : 

\begin{Th}[Caractérisation de la surjectivité]
$$\hbox{\og $f$ est (une application) surjective\fg{}  } \Ssi f<E>=F$$
\end{Th}


\begin{Ex}
Soit l'application \og élévation au carré \fg{} $f : x \longmapsto x^2$ de $\R$ dans $\R$. Elle est :
\begin{itemize}
\item non surjective : $f < \R > = \R^+$,
\item non injective : $f(-2) = f(2) = 4$.
\end{itemize}
\end{Ex}

\begin{Exo}
On suppose $g o f$ surjective. Montrer que $g$ est surjective. Est-ce que $f$ est obligatoirement surjective ?
\end{Exo}

\subsubsection{Applications bijectives}

\begin{Def}[Applications bijectives]
Une application qui est à la fois injective et surjective est dite \emph{bijective} \index{application!bijective}. 
\end{Def}


\begin{Rem}
Synonyme d'\og application bijective\fg{} : bijection \index{bijection}.
\end{Rem}

\begin{Exo}
Dans chaque cas, dire si l'application $f:A \vers B$ est injective, surjective ou bijective.

\begin{enumerate}
\item $A = \R, B = \R, f(x) = x+7$
\item $A = \R, B = \R, f(x) = x^2+2x-3$
\item $A = \{ x \in \R | 4 \leqslant x \leqslant 9 \}, B = \{ x \in \R | 21 \leqslant x \leqslant 96 \}, f(x) = x^2+2x-3$
\item $A = \R, B = \R, f(x) = 3x-2|x|$
\item $A = \R, B = \R, f(x) = e^x+1$
\item $A = \N, B = \N, f(x) = x(x+1)$
\end{enumerate}
\end{Exo}


\begin{Th}
Dans le cas d'une bijection, à chaque élément $x$ de $E$ correspond un et un seul élément $y$ de $F$ (définition d'une application) et, réciproquement, à chaque (surjectivité) élément $y$ de $F$ correspond un et un seul (injectivité) élément $x$ de $E$.
\end{Th}


Cette dernière proposition est précisément l'affirmation de l'existence d'une application $g$ de $F$ dans $E$, telle que $x = g(y) \Longleftrightarrow f(x) = y $.




\begin{Def}[Application inverse]
Cette application est appelée application inverse de l'application $f$.
\end{Def}

\begin{Notation}
 On la note $f^{-1}$
\end{Notation}

\begin{Exo}
Reprendre l'exercice précédent, en trouvant l'application réciproque des applications bijectives.
\end{Exo}


\begin{Rem}
On peut démontrer que la bijectivité est une condition nécessaire et suffisante pour qu'une application admette une inverse.
\end{Rem}

\begin{Rem}
Un cryptosystème (algorithme de chiffrement/déchiffrement) est une application bijective.
\end{Rem}

\begin{Rem}
Les algorithmes de hachage ne sont pas bijectifs.
\end{Rem}



\begin{Ex}
Soit l'application \og multiplication par 2 \fg{} $f : x \longmapsto 2 x$ de $\R$ dans $\R$. Elle est :
\begin{itemize}
\item surjective,
\item injective.
\end{itemize}
Elle admet donc une application inverse, à savoir : $f^{-1} : x \longmapsto x/2$.
\end{Ex}

\begin{Exo}
Soit $f : \Z \vers \Z$ définie par $f(n) = n + (-1)^n$.
\begin{enumerate}
 \item Montrer que $n$ et $f(n)$ sont toujours de parité différente.
\item Montrer que $f$ est bijective.
\item Calculer $f(f(n))$. En déduire une expression de $f^{-1}$ et résoudre l'équation $347 = n+(-1)^n$.
\end{enumerate}

\end{Exo}


\subsection{Cardinal et puissance d'un ensemble}

Il s'agit ici de proposer une réflexion sur la notion intuitive de \og nombre d'éléments d'un ensemble\fg{}  , nécessaire pour pouvoir
aborder ultérieurement les notions de dénombrabilité et de calculabilité, fondamentaux en informatique.\\


\subsubsection{Cas des ensembles finis}


On commence par prendre deux ensembles $E=\{a,b,c,d\}$ et $F=\{1,2,3\}$ et à remarquer que :
\begin{itemize}
 \item il est possible de définir une injection de $F$ dans $E$, mais pas une surjection,
 \item de définir une surjection de $E$ sur $F$, mais pas d'injection,
\end{itemize}
...tout simplement parce qu'il n'y a \og pas assez\fg{} d'éléments dans $F$ (ou \og trop\fg{}  dans $E$).\\


Si l'on  veut pouvoir définir une bijection entre deux ensembles, il semble nécessaire et suffisant qu'ils aient le même \og nombre d'éléments\fg{} (on se limite ici au domaine fini).



Cette notion intuitive, résultat immédiat d'une simple opération de comptage, est reliée à la notion mathématique de mise en bijection avec une partie de $\Net$ de la forme $\{1\vir 2\vir\ldots\vir n\}$. 



 Ainsi, pour $n\in\Net$ donné, les ensembles à $n$ éléments sont tous ceux qui peuvent être mis en bijection avec $\{1\vir 2\vir\ldots\vir n\}$ (et, par convention, $\vide$ a 0 élément).


\begin{Def}[Cardinal d'un ensemble fini]
L'élément maximum de cette partie finie de $\Net$ est un représentant du \emph{cardinal}\index{ensemble!cardinal} des ensembles en question.
\end{Def}



Pas de problème donc lorsqu'on s'en tient aux ensembles finis, dont la définition mathématique est :


\begin{Def}[Ensemble fini]
Un ensemble est dit fini\index{ensemble!fini} s'il ne peut pas être mis en bijection avec une partie stricte de lui-même.
\end{Def}


\subsubsection{Cas des ensembles infinis}



Lorsqu'on se pose la question du \og nombre d'éléments\fg{}  d'un ensemble infini, on peut être tenté, dans un premier temps, de répondre par \og une infinité\fg{} , ce qui n'est pas satisfaisant pour au moins deux raisons : 
\begin{itemize}
 \item jusqu'à présent, le \og nombre d'éléments\fg{}  était un entier, et l'infini n'est pas un nombre entier,
 \item cela laisserait supposer que tous les ensemble infinis ont le même \og nombre d'éléments\fg{}
\end{itemize}


Une réflexion plus appronfondie apparaît comme nécessaire. On décide donc de se calquer sur le domaine fini...


\begin{Def}[Puissance d'un ensemble infini]
Deux ensembles ont \emph{même puissance}\index{ensemble!puissance}\index{puissance!d'un ensemble} (\og même nombre d'éléments\fg{}) si l'on peut les mettre en bijection.
\end{Def}



\begin{Ex}
Il existe des bijections entre $\N$ et l'ensemble des entiers pairs ($2\N$) ou impairs ($2\N+1$), qui conduisent à des formulations du style \og il y a autant d'entiers que d'entiers pairs \fg{}.
\end{Ex}
 

\begin{Rem}
 $2\N \cup 2\N+1 = \N$, bien que ces trois ensembles \og on le même nombre d'éléments \fg{}, les deux premiers étants disjoints... à rapprocher de $\infty\plinf=\infty$.
\end{Rem}


\begin{Rem}
 Pour ce genre de raisons, on a tendance à abandonner ce vocabulaire (sur les nombres d'individus) pour dire simplement que ces ensembles ont même puissance.
\end{Rem}



\subsubsection{Nombre d'infinis}

\paragraph{Notion de puissance d'un ensemble}

Le résultat fondamental est...

\begin{Th}
Il est impossible de définir une surjection de $E$ sur $\mathcal{P}(E)$.
\end{Th}

\begin{Proof}
 Admis
\end{Proof}

Ce résultat montre que, même si $E$ est un ensemble infini, il ne peut être mis en bijection avec ${\cal P}(E)$, qui a donc \og strictement plus d'éléments\fg{}  que $E$.


Conséquemment, $\N$ et ses parties infinies, $\Z$, et même $\Q$ ont la même puissance, dite \emph{puissance du dénombrable}\index{puissance!du dénombrable}, mais...


\begin{Def}[Puissance du continu]
 ${\cal P}(\N)$ n'est pas dénombrable, et est de puissance supérieure, dite \emph{puissance du continu}\index{puissance!du continu}.
\end{Def}

\begin{Ex}
 C'est la puissance de $\R$.
\end{Ex}


De même, ${\cal P}(\R)$ est de puissance supérieure à $\R$, et ainsi de suite\ldots...

\paragraph{$\mathbb{R}$ est indénombrable : une démonstration de Cantor.}

Supposons que $\mathbb{R}$ soit dénombrable.

On pourrait alors écrire la liste de TOUS les réels, à partir du premier, en écriture décimale $r_1$, $r_2$, $r_3$, etc.

\begin{Rem}
On choisit pour les nombres décimaux l'écriture qui ne comporte que des zéros à partir d'un certain rang, s'il y a ambiguïté.
\end{Rem}

\begin{Ex}
On préférera l'écriture 1 à 0,9999999......
\end{Ex}

Construisons alors le nombre $S$ de la manière suivante :
\begin{enumerate}
\item sa partie entière est 0,
\item et pour sa partie décimale,
\begin{itemize}
\item le premier chiffre est différent du premier chiffre après la virgule de $r_1$,
\item le deuxième chiffre est différent du deuxième chiffre après la virgule de $r_2$,
\item etc.
\end{itemize}
\end{enumerate}

Le nombre $S$ ne fait alors pas partie de la liste des réels, ce qui est contradictoire : l'hypothèse $\mathbb{R}$ dénombrable (on peut numéroter tous les réels avec $\mathbb{N}$) est erronée.


\subsection{Relations d'ordre}
Dans ce paragraphe, on se place dans le cas où $E=F$.



\subsubsection{Définition}

Soit ${\mathcal{R}}$ une relation binaire définie dans un ensemble $E$, de graphe $G$.

\paragraph{Réflexivité, antisymétrie, transitivité}


\begin{Def}[Réflexivité]
 ${\mathcal{R}}$ est dite \emph{réflexive} \index{relation!réflexive} quand tout élément de $E$ est en relation avec lui-même :
$$\qqs x\in E,\ (x,x)\in G$$
\end{Def}


\begin{Rem}
 C'est-à-dire $\qqs x\in E,\ x {\mathcal{R}} x$, ou encore : la diagonale de $E^2$ est incluse dans $G$.
\end{Rem}



\begin{Def}[Antisymétrie]
 ${\mathcal{R}}$ est dite \emph{antisymétrique} \index{relation!antisymétrique} si, lorsque  $x$ est en relation avec $y$, alors $y$ ne peut pas être en relation avec $x$ (sauf si $x=y$) :

$$\qqs x\in E,\ \qqs y\in E,\ (x,y)\in G ~{\rm et}\ (y,x)\in G\ \Imp x=y$$
\end{Def}


\begin{Rem}
 C'est-à-dire $\qqs(x,y)\in E^2,\ x {\mathcal{R}} y\ {\rm et}\ y {\mathcal{R}} x\Imp\ x=y$.
\end{Rem}



\begin{Def}[Transitivité]
 ${\mathcal{R}}$ est dite \emph{transitive} \index{relation!transitive} lorsque, si $x$ est en relation avec $y$, et si $y$ l'est avec $z$, alors $x$ est en relation avec $z$ : 
$$\qqs x\in E,\qqs y\in E,\ \qqs z\in E,\ (x,y)\in G\ {\rm et}\ (y,z)\in G
\Imp (x,z)\in G$$
\end{Def}


\begin{Rem}
C'est-à-dire : $\qqs x\in E,\ \qqs y\in E,\qqs z \in E,\ x {\mathcal{R}} y\ {\rm et}\ y {\mathcal{R}} z \Imp x {\mathcal{R}} z$. 
\end{Rem}


\begin{Exo}
Les relations suivantes sont-elles réflexives, antisymétriques ou transitives ?
\begin{enumerate}
\item $A = \mathbb{R}$ et $x \mathcal{R} y$ si $|x| = |y|$.
\item $A = \mathbb{R}$ et $x \mathcal{R} y$ si $sin^2 x + cos^2 y = 1 $.
\item $A = \mathbb{N}$ et $x \mathcal{R} y$ s'il existe $p$ et $q$ entiers tels que $y = p x^q$.
\item $A$ est l'ensemble des points du plan, et $x \mathcal{R} y$ si la distance de $x$ à $y$ est inférieure à 52,7 km.
\end{enumerate}
\end{Exo}



\paragraph{Relation d'ordre}

\begin{Def}[Relation d'ordre]
${\mathcal{R}}$ est une \emph{relation d'ordre}\index{relation!d'ordre} lorsqu'elle est réflexive, antisymétrique et transitive.
\end{Def}


\begin{Ex}[Exemples de relations d'ordre]
Quelques relations d'ordre : 
\begin{itemize}
\item $(\R,\leqslant )$
\item $({\cal P}(E),\sse)$
\end{itemize}
\end{Ex}

\begin{Ex}[Relation de divisibilité]
On note $a|b$ si et seulement si $b$ est un multiple de $a$ ( $\exists k \in \Net, b=ka$).

C'est une relation d'ordre définie dans $\Net$. En effet, elle est

\begin{itemize}
\item reflexive : $a=1a$, donc $a|a$ est vrai,
\item antisymétrique : si $a|b$ et $b|a$, alors $\exists k,k' \in \Net, a=kb$ et $b=k'a$. Donc $a = kk' a$. Comme $a \neq 0$, $kk'=1$. Mais $k,k' \in \Net$, donc $k = k' = 1$, et $a = b$.
\item transitive : si $a|b$ et $b|c$, alors alors $\exists k,k' \in \Net, a=kb$ et $b=k'c$. Donc $a = k k' c$ : il existe $k'' \in \Net$ ($k''=k k'$) tel que $a = k''c$ : $a|c$.
\end{itemize}

\end{Ex}


La structure algébrique constituée par l'ensemble $E$, muni de la
relation d'ordre ${\mathcal{R}}$, (c'est-à-dire: le couple $(E,{\mathcal{R}})$) est
celle d'\emph{ensemble ordonné}\index{ensemble!ordonné}.



\subsubsection{Ordre partiel, ordre total}

Une relation d'ordre définie dans un ensemble $E$ peut posséder une propriété supplémentaire, celle selon laquelle tous les éléments de $E$ sont comparables entre eux.


Cela signifie que, si l'on choisit deux éléments $x$ et $y$ quelconques dans $E$, $x$ est en relation avec $y$, ou $y$ est en relation avec $x$ : $\qqs x\in E, \qqs y\in E, (x,y)\in G\ {\rm ou}\ (y,x)\in G$.


\begin{Def}[Relation d'ordre totale]
 Une relation d'ordre qui possède cette dernière propriété est dite relation d'\emph{ordre total}\index{relation!d'ordre!totale}, et la structure algébrique correspondante est celle d'\emph{ensemble totalement ordonné}\index{ensemble!totalement ordonné}.
\end{Def}


\begin{Rem}
 Cette propriété est aussi équivalente à : $\qqs x\in E,\ \qqs y\in E,\ x\ {\mathcal{R}}\ y\ {\rm ou}\ y {\mathcal{R}} x$, ou encore : si $x$ n'est pas en relation avec $y$, alors $y$ est en relation avec $x$.
\end{Rem}


\begin{Def}[Relation d'ordre partiel]
Dans le cas contraire, il existe des éléments qui ne sont pas comparables : on parle alors d'\emph{ordre partiel} \index{relation!d'ordre!partiel}.
\end{Def}


\begin{Ex}
$\leqslant$ est une relation d'ordre totale dans $\R$.
\end{Ex}

\begin{Ex}
$\subset$ dans $\mathcal{P}(E)$, et $|$ dans $\N$ sont des relations d'ordre partiels.
\end{Ex}


\subsubsection{Exercices}

\begin{Exo}
Parmi les relations suivantes sur l'ensemble $E$, repérez les relations d'ordre, les relations d'ordre total :
\begin{enumerate}
\item $E = \mathbb{Z}$, $x \mathcal{R} y \Leftrightarrow \exists k \in \mathbb{N} : x = y^k$.
\item $E = \mathbb{N}$, $x \mathcal{R} y \Leftrightarrow x<y$.
\item $E = \mathbb{R}$, $x \mathcal{R} y \Leftrightarrow x^2 = y^2$.
\item $E = \mathbb{R}^2$, $(x_1,x_2) \mathcal{R} (y_1,y_2) \Leftrightarrow (x_1 \leqslant y_2) \et (x_2 \leqslant y_1)$.
\end{enumerate}
\end{Exo}



\begin{Exo}
On se place dans l'ensemble $E=\{1,2,3,\ldots,20\}$.


Représenter, dans le plan rapporté à deux axes de coordonnées rectangulaires, les graphes des relations binaires sur E dont les définitions suivent:
\begin{itemize}
\item $x {\mathcal{R}} y \Ssi x\leqslant y$
\item $x {\mathcal{R}} y \Ssi x\mid y$ (x divise y)
\item $x {\mathcal{R}} y \Ssi x\equiv y\ [3]$ (x est congru à y
modulo 3, voir cours) 
\item $x {\mathcal{R}} y \Ssi y=x^2$
\item Tenter de caractériser par son graphe, à l'aide
des dessins précédents, une relation d'ordre (partiel,
total), une relation d'équivalence, une application.
\item Définir, par leurs graphes, les relations d'équivalence dans E qui comportent respectivement le moins et le plus possible de points; que peut-on dire de ces relations? Même question pour les relations d'ordre.
\end{itemize}
\end{Exo}





\begin{Exo}[Relations d'ordre en Algèbre de Boole]
Soit $\cal A$ une algèbre de Boole.

On considère la relation binaire, de symbole $<$, définie par $$a<b \Ssi a+b=b.$$
\begin{enumerate}
\item Montrer qu'il s'agit d'une relation d'ordre.
\item Montrer que $a<b\ \Ssi\ a\cdot b=a$.
\item Montrer que, $\forall (a,b,c)\in {\cal A}^3,\ b\cdot c<a\cdot b+{\sur a}\cdot c$.
\item On définit la relation binaire $\sse$ par: $a\sse b$ si et seulement si 
$a\cdot{\sur b}=0$; montrer que c'est une relation d'ordre, comparer avec les 
résultats précédents.
\item En utilisant l'une ou l'autre des définitions ci-dessus pour la relation d'ordre, trouver,
lorsqu'ils existent, les éléments $\sup\{a,b\}$ et $\inf\{a,b\}$. Trouver $\max{\cal A}$ et
$\min{\cal A}$.
\end{enumerate}
\end{Exo}


\subsubsection{\'Eléments maximaux}

Soit $(E,{\mathcal{R}})$ un ensemble ordonné et $A$ une partie de $E$. Quelques définitions...


\begin{Def}[Majorant]
On appelle \emph{majorant} \index{majorant} de $A$ tout élément $M$ de $E$ tel que, quel que soit $a\in A$, $a{\mathcal{R}}M$.
\end{Def}


\begin{Def}[Partie majorée]
La partie $A$ de $E$ est dite \emph{majorée}\index{partie majorée} s'il existe un majorant de $A$.
\end{Def}

\begin{Exo}
Trouvez des exemples de majorants et de parties majorées sur $\mathbb{N}$ et $\mathcal{R}$.
\end{Exo}


\begin{Rem}
Il existe des parties non majorées ($\mathcal{R}^+$ pour $\leqslant$ dans $\R$)
\end{Rem}

\begin{Rem}
Il peut exister une infinité de majorants pour une partie majorée.
\end{Rem}


\begin{Def}[Minorant]
On appelle \emph{minorant} \index{minorant} de $A$ tout élément $m$ de $E$ tel que, quel que soit $a\in A$, $m{\mathcal{R}}a$.

On parle aussi de partie minorée.
\end{Def}

\begin{Exo}
Trouvez des exemples de minorants et de parties minorées sur $\mathbb{Z}$ et $\mathcal{Q}$.
\end{Exo}



\begin{Def}[Élément maximum]
On appelle \emph{élément maximum} \index{maximum} de $A$ un élément de $A$ qui est majorant de $A$.
\end{Def}
 
\begin{Exo}
Trouvez des exemples d'élément maximum sur $\mathbb{N}$ et $\mathcal{R}$.
\end{Exo}

\begin{Notation}
 $\max A$.
\end{Notation}

\begin{Rem}
 Si $A$ est non majorée, il est exclu qu'elle admette un élément maximum.
\end{Rem}

\begin{Rem}
 Cet élément maximum n'existe pas toujours, même pour une partie majorée. Ainsi, l'intervalle réel ]2,3[ est majoré, mais n'a pas d'élément maximum.

Cependant, s'il existe, cet élément est unique.
\end{Rem}



\begin{Def}[Élément minimum]
 On appelle \emph{élément minimum} \index{minimum} de $A$ un élément de $A$ qui est minorant de $A$.
\end{Def}
 

\begin{Notation}
 $\min A$.
\end{Notation}


\begin{Def}[Borne supérieure]
On appelle \emph{borne supérieure}\index{borne!supérieure} de $A$ l'élément minimum, s'il existe, de l'ensemble des majorants de $A$.
\end{Def}
 

\begin{Notation}
 $\sup A$.
\end{Notation}


\begin{Def}[Borne inférieure]
 On appelle \emph{borne inférieure}\index{borne!inférieure} de $A$ l'élément maximum de l'ensemble des minorants de $A$.
\end{Def}
 

\begin{Notation}
 $\inf A$.
\end{Notation}



\begin{Exo}
Trouvez des exemples de bornes sup et de bornes inf sur $\mathcal{R}$.
\end{Exo}





\begin{Exo}[Une relation d'ordre]
On considère l'ensemble des points d'un plan affine euclidien, et on y définit une relation binaire (symbole $\leqslant $) par $P_1\leqslant P_2 \Ssi (x_1\leqslant x_2\  {\rm et}\ y_1\leqslant y_2)$.

\begin{enumerate}
 \item Définir, lorsqu'ils existent, les points $\sup\{P_1,P_2\}$ et $\inf\{P_1,P_2\}$.
 \item Existent-ils toujours, quels que soient les points $P_1$ et $P_2$ ?
\end{enumerate}
\end{Exo}


\begin{Th}
Il est clair que :
\begin{itemize}

\item dans certains cas, les éléments définis ici n'existent pas,

\item que l'élément maximum est aussi borne supérieure.
\end{itemize}

\noindent Et finalement, pour une partie $A$ d'un ensemble ordonné $E$ :

\begin{itemize}
 \item $A$ peut ne pas être majorée.
\item Si $A$ est majorée, elle peut ne pas admettre de borne supérieure.
\item Si $Sup A$ existe ($A$ est majorée), $A$ peut ne pas admettre d'élément maximum.
\item Si $Max A$ existe, alors $Sup A = Max A$.
\end{itemize}

\noindent ...et on a les mêmes résultats pour les parties minorées.
\end{Th}




\begin{Ex}
 Cas de $E=\{x\in\Q\mid x\leqslant 32\}$.
\begin{itemize}
\item ensemble majoré de nombres réels
\item 56 , 32 sont majorants
\item ensemble $E'$ des majorants : $E'=\{y\in\Q\mid y\geqslant 32\}$
\item $\max E=32$
\item $\min E'=32$, donc $\sup E=32$.
\end{itemize}
\end{Ex}

\begin{Ex}
Cas de $E=\{x\in\Q\mid x<32\}$.
\begin{itemize}
\item ensemble majoré de nombres réels
\item 56, 32 sont majorants
\item ensemble $E'$ des majorants : $E'=\{y\in\Q\mid y\geqslant 32\}$
\item $E$ n'a pas d'élément maximum
\item $\min E'=32$, donc $\sup E=32$.
\end{itemize}
\end{Ex}





\subsubsection{Treillis}

\paragraph{Cas des ensembles totalement ordonnés}

Dans un ensemble totalement ordonné, si l'on choisit une paire d'éléments quelconques $(x,y)$ il est possible de décider lequel est le plus petit et lequel est le plus grand.



Et, comme cette partie $\{x\vir y\}$ admet un élément minimum et un élément maximum, ces deux éléments sont aussi (respectivement) borne inférieure et supérieure, on peut écrire $\inf\{x\vir y\}=x$ et $\sup\{x\vir y\}=y$.



L'existence de ces deux éléments est assurée, ce qui n'est pas le cas dans un ensemble qui n'est que partiellement ordonné.



\paragraph{Cas des ensembles partiellement ordonnés}


Il existe alors des paires d'éléments $(x,y)$ qui ne sont pas comparables et, pour une telle paire, les éléments $\min\{x\vir y\}$ et $\max\{x\vir y\}$ ne sont pas définis.



Il se peut, cependant, que les éléments $\inf\{x\vir y\}$ et
$\sup\{x\vir y\}$ soient, eux, définis.



Si cette propriété est vérifiée pour tous les couples d'éléments $(x,y)$, alors l'ensemble est un treillis :


\begin{Def}[Treillis]
Un ensemble ordonné est un \emph{treillis} \index{treillis} lorsque toute partie finie admet une borne sup et une borne inf.
\end{Def}

\begin{Rem}
 Il suffit que la propriété soit vraie pour deux éléments distincts (\emph{i.e.} une partie à deux éléments) pour qu'elle soit vrai pour toutes les parties finies.
\end{Rem}

\begin{Exo}
Démontrez l'assertion de la remarque précédente.
\end{Exo}


\begin{Def}[Treillis complet]
 Si la propriété est vrai pour toute partie, alors le treillis est dit \emph{complet}\index{treillis!complet}.
\end{Def}


\begin{Ex}
Un ensemble totalement ordonné est toujours un treillis. 
\end{Ex}


\begin{Rem}
 Cette notion n'offre un intérêt que dans le cas d'un ensemble partiellement ordonné, car l'existence d'une borne inférieure et d'une borne supérieure pour tout couple (et donc pour toute partie finie) permet de les comparer aux autres par l'intermédiaire de ces bornes, même si on ne peut pas les comparer entre eux.


En effet, on a toujours $\inf\{x\vir y\}\leqslant x\leqslant \sup\{x\vir
y\}$ et $\inf\{x\vir y\}\leqslant y\leqslant \sup\{x\vir y\}$ (on reprend les exemples vus plus haut).
\end{Rem}




\begin{Exo}[Diagrammes de transitivité]
On considère...
\begin{enumerate}
\item $E=\{1\vir 2\vir 3\vir 4\vir 5\vir 6\vir 7\vir 8\vir 9\}$ et on
définit la relation binaire $\mathcal{R}$ dans $E$ par son graphe
$G=\{ $ (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (2,2), (2,3), (2,4), (2,6), (2,8), (2,9), (3,3), (4,3), (4,4), (4,6), (4,8), (4,9), (5,3), (5,4), (5,5), (5,6), (5,7), (5,8), 
(5,9), (6,6), (6,8), (6,9), (7,7), (7,8), (7,9), (8,8), (9,9) $\}$
(c'est-à-dire: $1{\mathcal{R}}1$, etc\ldots). Montrer que cette relation est une relation d'ordre. $E$ est-il totalement ordonné par cette relation ? est-il un treillis ?

\item Mêmes questions pour $E'=\{1\vir 2\vir 3\vir 4\vir 5\vir 6\}$ et
$G'=\{$ (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), 
(2,2), (2,4), (2,5), (2,6), (3,3), (3,4), (3,6), (4,4), (4,6), (5,5), (5,6), (6,6)$\}$.
\end{enumerate}
\end{Exo}







\subsection{Relations d'équivalence}


On se place encore dans ce paragraphe dans le cas où $E=F$.



\subsubsection{Définition}
Soit ${\mathcal{R}}$ une relation binaire définie dans un ensemble (non vide) $E$, de graphe $G$.

\begin{Def}[Relation symétrique]
${\mathcal{R}}$ est dite \emph{symétrique} \index{relation!symétrique} si, dès que $x$ est en relation avec $y$, alors $y$ est en relation avec $x$
$$\qqs x\in E,\ \qqs y\in E, (x,y)\in G \Imp (y,x)\in G$$
\end{Def}



\begin{Rem}
 Ou encore: $\qqs x\in E, \qqs y\in E,\ x {\mathcal{R}} y \Imp y {\mathcal{R}} x$.
\end{Rem}


\begin{Exo}
 Est-ce qu'une relation sur un ensemble A dont le graphe est constitué uniquement de couples (x,x) est symétrique ? transitive ?
\end{Exo}




\begin{Def}[Relation d'équivalence]
${\mathcal{R}}$ est une relation d'équivalence lorsqu'elle est réflexive, symétrique et transitive.
\end{Def}


\begin{Ex}
 L'égalité est une relation d'équivalence.
\end{Ex}



\begin{Ex}[Relation de congruence modulo $n$ dans $\Z$]
Par définition: $$x\equiv y\ [n]
\hbox{(lire: \og $x$ est congru à $y$ modulo $n$\fg{}  )} \Ssi
\exi k\in\Z,\ x-y=k\cdot n$$.
\begin{itemize}
\item réflexivité: $x\equiv x [n]$: en effet, $x-x=0\cdot n$, et
$0\in\Z$.
\item symétrie: si $x\equiv y\ [n]$, $\exists k\in\Z$, $x-y=k\cdot n$;
alors $y-x=(-k)\cdot n$; or, si $k\in\Z$, $(-k)\in\Z$, donc $y\equiv x\
[n]$.
\item transitivité: si $x\equiv y\ [n]$ et $y\equiv z\ [n]$, $\exi
k\in\Z$, $x-y=k\cdot n$ et $\exi l\in\Z$, $y-z=l\cdot n$. En
aditionnant membre à membre ces deux égalités, on obtient
$x-z=(k+l)\cdot n$, or $(k,l)\in\Z^2$, donc $k+l \in\Z$, donc
$x\equiv z\ [n]$.
\end{itemize}
C'est bien une relation d'équivalence. 
\end{Ex}



\begin{Exo}
Sur $\mathbb{Z}$, on écrit \og $x \mathcal{R} y$ quand $x+y$ est pair. \fg{}

Montrez que $\mathcal{R}$ est une relation d'équivalence.
\end{Exo}

\begin{Exo}
Sur $\mathbb{R}$, on définit la relation \og $x \mathcal{R} y$ quand $cos(2x)=cos(2y)$.\fg{}

Montrez que $\mathcal{R}$ est une relation d'équivalence.
\end{Exo}






\subsubsection{Classes d'équivalence}

\paragraph{Définition}

\begin{Def}[Classe d'équivalence]
Soit $x$ un élément de $E$.

On appelle \emph{classe d'équivalence} \index{classe d'équivalence} de cet élément l'ensemble des éléments de $E$ qui sont en relation avec $x$ (on dit encore : \og qui sont équivalents à $x$ \fg{} ).
\end{Def}




\begin{Notation}
On note $\dot x$ la classe de l'élément $x$ : $\dot x=\{y\in E \mid y {\mathcal{R}} x\}$
\end{Notation}


\begin{Exo}
Trouvez les classes d'équivalences des deux exercices précédents.
\end{Exo}

\begin{Exo}
On définit une relation sur l'ensemble des mots de la langue française de la façon suivante : \og le mot $M$ est lié au mot $N$ si $N$ est une anagramme\index{anagramme}\footnote{Mot obtenu par transposition des lettres d'un autre mot. Une anagramme intéressante : aimer - Marie. Le pseudonyme de Alcofribas Nasier est, à peu près, l'anagramme de François Rabelais.} de $M$.\fg{}

Quelle est la classe d'équivalence du mot chien?
\end{Exo}


\paragraph{Propriétés des classes d'équivalence}



\begin{Th}
Une classe d'équivalence n'est jamais vide. 
\end{Th}

\begin{Proof}
En effet, la classe de $x$ contient toujours au moins l'élément $x$ lui-même, par réflexivité.
\end{Proof}



\begin{Th}
L'intersection de deux classes d'équivalence distinctes est vide.
\end{Th}

\begin{Rem}
 On dit aussi que les classes sont deux à deux disjointes.
\end{Rem}


\begin{Proof}
On considère deux classes, $\dot x$ et $\dot y$, soit $z\in\dot x\inter\dot y$; $\qqs t\in\dot x$, on a $(t,x)\in G$; mais
$z\in\dot x$, donc $(z,x)\in G$, donc (symétrie) $(x,z)\in G$, donc
(transitivité) $(t,z)\in G$; mais $z\in\dot y$, donc $(z,y)\in G$, donc
(transitivité) $(t,y)\in G$, donc (finalement) $t\in\dot y$, et donc
$\dot x\sse\dot y$; raisonnement analogue pour tout $t\in\dot y$, qui
aboutit à $\dot y\sse\dot x$, et enfin (par double inclusion)
$\dot x=\dot y$; si deux classes ont un élément commun, elles sont
confondues; donc deux classes distinctes sont disjointes). 
\end{Proof}

\begin{Def}[Partition d'un ensemble]
Une \emph{partition}\index{partition} d'un ensemble $E$ est une famille de sous-ensembles de $E$, 2 à 2 disjoints, et dont la réunion est égale à E$.$
\end{Def}



\begin{Th}
Les classes d'équivalence réalisent une partition de $E$.
\end{Th}

\begin{Proof}
Comme les classes sont des parties de $E$, leur réunion est une partie de
$E$.

Réciproquement, tout élément de $E$ appartient à une classe (\og tout élément est classé\fg{} ). Donc $E$ est une partie de la réunion des classes; et $E$ est égal à la réunion des classes.
\end{Proof}

\begin{Ex}
On reprend la congruence modulo $n$, par exemple pour $n = 4$.On a:

$\dot 0=\{\ldots,-12,-8,-4,0,4,8,12,\ldots\}$

$\dot 1=\{\ldots,-11,-7,-3,1,5,9,13,\ldots\}$

$\dot 2=\{\ldots,-10,-6,-2,2,6,10,14,\ldots\}$

$\dot 3=\{\ldots,-9,-5,-1,3,7,11,15,\ldots\}$
 
\end{Ex}






\begin{Exo}[Une relation d'équivalence]
On considère l'ensemble des points du plan rapporté à
deux axes de coordonnées rectangulaires et deux points $P_1$ et
$P_2$ de coordonnées respectives $(x_1,y_1)$ et $(x_2,y_2)$; on
définit dans cet ensemble la relation binaire ${\mathcal{R}}$ par:
$$P_1 {\mathcal{R}} P_2 \Ssi x_1y_1=x_2y_2$$
\begin{itemize}
\item S'agit-il d'une relation d'équivalence? Si oui, étudier
les classes d'équivalence.
\item Mêmes questions pour la relation ${\mathcal{R}}'$, définie par
$$P_1 {\mathcal{R}}' P_2 \Ssi x_1y_1=x_2y_2\ {\rm et}\ x_1x_2\geqslant 0$$
\end{itemize}
\end{Exo}




\subsubsection{Ensemble-quotient}

\begin{Def}[Ensemble-quotient]
Il s'agit de l'ensemble des classes d'équivalence de tous les éléments de $E$.
\end{Def}


\begin{Notation}
$E/{\mathcal{R}}$.
\end{Notation}


Pour parler aisément d'une classe, on choisit un de ses éléments, et cet élément, surmonté d'un point, sert à représenter la classe en question.


Une fois que ce choix est fait, il est définitif, et il n'est plus question d'évoquer les autres éléments de cette classe, il faut
se tenir, sous peine d'incohérence, au choix qui a été fait.



\begin{Ex}[Congruence modulo 4]
On choisit pour représentants les entiers $<4$, donc 0, 1, 2 et 3.

L'ensemble-quotient est $\Z/4\Z=\{\dot 0,\dot 1,\dot 2,\dot 3\}$.
\end{Ex}



\subsubsection{Exercices}

\begin{Exo}
Sur un ensemble à $n$ éléments, combien y a-t-il de relations...
\begin{enumerate}
\item réflexives~? 
\item symétriques~?
\end{enumerate} 
\end{Exo}



\begin{Exo}
Déterminer quand une relation $R$ dans un ensemble $A$ est 
\begin{enumerate}
\item non réflexive
\item non symétrique
\item non transitive
\item non antisymtrique
\end{enumerate}
\end{Exo}


\begin{Exo}
Donner des exemples de relation $R$ dans $\{1,2,3\}$ ayant les propriétés suivantes:
\begin{enumerate}
\item $R$ est symétrique,
\item $R$ n'est ni symétrique ni antisymtrique,
\item $R$ est transitive mais $R \cup R^{-1}$ n'est pas transitive.
\end{enumerate}
\end{Exo}


\begin{Exo}
Soit $R$ et $S$ deux relations dans $A$.
\begin{enumerate}
\item Montrer que si $R$ et $S$ sont transitives alors $R\cap S$ est transitive.
\item Si $R$ est antisymétrique alors $R \cap S$ est antisymétrique.
\end{enumerate}
\end{Exo}


\begin{Exo}
Soit $R$ la relation d'équivalence suivante dans l'ensemble $A=\{A,2,3,4,5,6\}$:
$$
R = \{(1,1), (1,5), (2,2), (2,3), (2,6), (3,2), (3,3), (3,6),
(4,4),(5,1),(5,5), (6,2),(6,3),(6,6)\}
$$
Trouver la partition de $A$ induite par $R$, c'est-à-dire trouver les classes d'équivalence de $R$.
\end{Exo}


\subsection{Compatibilité entre une opération et une relation binaire}

\begin{Def}
La relation binaire (dans $E$) de symbole ${\mathcal{R}}$ est dite
\emph{compatible avec l'opération} (définie dans $E$) de symbole $\circ$ lorsque, quels que soient les éléments $x$, $x'$, $y$ et $y'$ de $E$ : si $x{\mathcal{R}}x'$ et si $y{\mathcal{R}}y'$, alors $(x\circ y){\mathcal{R}}(x'\circ y')$
\end{Def}


Autrement dit, l'opération conserve la relation.


\begin{Ex}
On considère la relation classique d'inégalité dans $\R$ : si on a $x\leqslant x'$ et $y\leqslant y'$, on peut écrire $x+x'\leqslant y+y'$.

Ce résultat est bien connu : on a le droit \og d'additionner des inégalités membre à membre\fg{}. En d'autres termes, l'addition des réels est compatible avec l'inégalité.


Mais, de $-2\leqslant 1$ et de $-3\leqslant -1$, on ne peut pas déduire que $6\leqslant -1$... On n'a pas le droit de \og multiplier des inégalités membre à membre\fg{}.

La multiplication des réels, quant a elle, n'est donc pas compatible avec l'inégalité. 
\end{Ex}



\begin{Exo}[Congruences modulo $n$]
Montrer que la relation de congruence modulo $n$ dans $\Z$ définie en cours est compatible avec addition et multiplication.

Établir les tables des opérations que l'on peut alors définir dans les ensembles $\Z/5\Z$, $\Z/6\Z$.
\end{Exo}

Lorsqu'une relation d'équivalence est compatible avec une opération, on peut définir dans {l'en\-sem\-ble-quo\-tient} une opération, dite \emph{induite} de celle qui existe dans l'ensemble d'origine.


\begin{Exo}
Montrer que la congruence modulo $n$ est compatible avec l'addition et la multiplication des entiers relatifs. 
\end{Exo}




\section{Relations $n$-aires}

\subsection{Définitions}

\subsubsection{Relations orientées et non orientées}

Exactement comme dans le cas des relations binaires, on considère une partie $G$ de l'ensemble produit cartésien de $n$ ensembles $\famn E$, soit $G\sse E_1\times E_2\times\cdots\times E_n$.

\begin{Def}[Relation $n$-aire]
Cette partie définit une relation $n$-aire\index{relation n-aire} entre ces ensembles. 
\end{Def}



\begin{Notation}
Pour un $n$-uplet $\famn x$ d'éléments de $E_1\times E_2\times\cdots\times E_n$, on notera $\famn x\in G$ ou ${\mathcal{R}}\famn x$ le fait que ces éléments sont en relation par la relation ${\mathcal{R}}$ de graphe $G$.
\end{Notation}





Comme dans le cas des relations binaires, les $n$-uplets sont ordonnés et, même si deux des ensembles $E_i$ et $E_j$ sont identiques (pour $i\neq j$), le couple d'éléments
$(x_i,y_j)$ est considéré comme différent du couple $(y_j,x_i)$ lorsque $x_i\neq y_j$. 



Cependant, dans la plupart des applications pratiques des relations $n$-aires, et dans toutes celles que nous verrons en tout cas, on \og étiquette les colonnes\fg{}, ce qui permet de s'affranchir de cet ordre, et de considérer ce que l'on appelle des relations
$n$-aires {\it non orientées\/}, dont les {\it domaines\/} sont les ensembles $\famn E$, dans un ordre non spécifié, car ils sont nommés.




\paragraph {Exemple de relation ternaire orientée}


Soient

\begin{itemize}
 \item $E_1=\{1,2,3,4,5,6,7,8,9\}$,
 \item $E_2=\{1988, 1989, 1990, 1991, 1992, 1993, 1994\}$
 \item $E_3=\{\hbox{Alsace}, \hbox{Beaujolais}, \hbox{Côtes du Rhône}\}$.
\end{itemize}

 et soit

\begin{center}
$G=\{$ (3,1988,\hbox{Alsace}), (4,1991,\hbox{Alsace}), (8,1989,\hbox{Beaujolais}), (4,1989,\hbox{Côtes du Rhône}) $\}$. 
\end{center}




$G$ est le graphe d'une relation ternaire orientée qui représente une cave à vins.\\




On peut la représenter par le tableau :\\


\centerline{$\begin{array}{c|c|l}
3 & 1988 & \hbox{Alsace} \\
4 & 1991 & \hbox{Alsace} \\
8 & 1989 & \hbox{Beaujolais} \\
4 & 1989 & \hbox{Côtes du Rhône} \\ \end{array}$}

\bigskip


Il est évident que l'ordre des éléments du $n$-uplet élément de $G$ a une importance fondamentale, surtout lorsque l'intersection des domaines n'est pas vide.


Autrement dit, cette relation doit être considérée comme différente de la relation définie sur $E_3\times E_2\times E_1$ par le graphe $G'$ représenté par le tableau\\



\centerline{$\begin{array}{l|l|l}
\hbox{Alsace} & 1988 & 3 \cr
\hbox{Alsace} & 1991 & 4 \cr
\hbox{Beaujolais} & 1989 & 8 \cr
\hbox{Côtes du Rhône} & 1989 & 4 \cr\end{array}$}




\paragraph {Exemple de relation ternaire non orientée}\hfill\break Pour s'affranchir de l'ordre en évitant toute ambiguïté, il faut nommer les colonnes du tableau, c'est-à-dire ajouter un ensemble d'{\it attributs\/} (ou clés, ou étiquettes) qui pourraient être ici
$\{$Nombre, Année, Région$\}$.


On obtiendrait\\

\centerline{$\begin{array}{c|c|l}
\hbox{Nombre} & \hbox{Année} & \hbox{Région} \cr
\noalign{\hrule}
3 & 1988 & \hbox{Alsace} \cr
4 & 1991 & \hbox{Alsace} \cr
8 & 1989 & \hbox{Beaujolais} \cr
4 & 1989 & \hbox{Côtes du Rhône} \cr\end{array}$}

\bigskip

Cette relation ternaire ne sera pas considérée comme différente de la relation représentée par\\


\centerline{$\begin{array}{l|c|c}
\hbox{Région} & \hbox{Année} & \hbox{Nombre} \cr
\noalign{\hrule}
\hbox{Alsace} & 1988 & 3 \cr
\hbox{Alsace} & 1991 & 4 \cr
\hbox{Beaujolais} & 1989 & 8 \cr
\hbox{Côtes du Rhône} & 1989 & 4 \cr\end{array}$}\psaut

\medskip

En effet, les attributs ne sont pas ordonnés, l'ensemble $\{$Région, Année, Nombre$\}$ est égal à l'ensemble $\{$Nombre, Année, Région$\}$.


\bigskip

Dans la suite, le terme de relation $n$-aire sera réservé aux relations non orientées.


\bigskip


On peut toujours associer à une relation $n$-aire une relation $n$-aire orientée, définie sur $D_1\times D_2\times\cdots\times D_n$, où les $D_i$ sont les domaines attachés aux attributs de $A$, énoncés dans un certain ordre.


Bien entendu, si les attributs sont énoncés dans un ordre différent, la relation $n$-aire orientée associée peut ne pas être la même, mais, pour une même relation $n$-aire, toutes les relations $n$-aires orientées associées se déduisent les unes des autres par une permutation sur les domaines.


\bigskip

C'est pourquoi on s'autorisera à utiliser l'abus de notation ${\mathcal{R}}\famn x$, pour exprimer que les $x_i$ sont en relation par la relation $n$-aire (non orientée) ${\mathcal{R}}$, en se référant à l'une quelconque des relations $n$-aires orientées associées (celle qui correspond à l'ordre des domaines $D_i$ lorsque les $x_i$ sont énoncés).


\begin{Notation}
On notera ${\mathcal{R}}[A]$ une relation $n$-aire (non orientée) d'attributs $A$.
\end{Notation}



\subsubsection{Relations équivalentes, relations égales}

\begin{Def}[Relations $n$-aires équivalentes]
Deux relations $n$-aires (non orientées) sont \emph{équivalentes}\index{relations n-aires!équivalentes} lorsque leurs domaines sont les mêmes et qu'il existe une permutation de ces domaines telle que les relations orientées associées sont égales (au sens de l'égalité des ensembles, puisqu'une relation $n$-aire orientée est définie comme un ensemble).
\end{Def}




\begin{Def}[Relations $n$-aires égales]
Deux relations $n$-aires (non orientées) sont \emph{égales}\index{relations n-aires!égale} lorsqu'elles sont équivalentes et que leurs attributs sont les mêmes. 
\end{Def}



\noindent
\begin{tabular}{ccc}

\begin{tabular}{|c|c|c|}
\noalign{\hrule}
Groupe & Nom & Age \cr
\noalign{\hrule}
1 & A & 18 \cr
\noalign{\hrule}
1 & B & 17 \cr
\noalign{\hrule}
2 & C & 18 \cr
\noalign{\hrule}
\end{tabular} 

&

\begin{tabular}{|c|c|c|}
\noalign{\hrule}
Age & Nom & Groupe \cr
\noalign{\hrule}
18 & A & 1\cr
\noalign{\hrule}
17 & B & 1\cr
\noalign{\hrule}
18 & C & 2\cr
\noalign{\hrule}
\end{tabular}

&

\begin{tabular}{|c|c|c|}
\noalign{\hrule}
Note & Matière & Nombre \cr
\noalign{\hrule}
18 & A & 1\cr
\noalign{\hrule}
17 & B & 1\cr
\noalign{\hrule}
18 & C & 2\cr
\noalign{\hrule}
\end{tabular}

\cr

Une relation ${\mathcal{R}}$

&

Une relation égale à ${\mathcal{R}}$ 

&

Une relation équivalente à ${\mathcal{R}}$

\cr

\end{tabular}


\bigskip

\subsubsection{Interprétation fonctionnelle}

Chaque ligne du tableau d'une relation $n$-aire ${\mathcal{R}}[A]$ aux attributs $A$, de domaines $\famn D$, peut être interprétée comme une application de $A$ (l'ensemble des attributs) dans $D_1\union
D_2\union\cdots\union D_n$.



\begin{Ex}
Par exemple, pour la première relation du paragraphe précédent, on peut considérer les fonctions $f_1$, $f_2$ et $f_3$ définies par $f_1(\hbox{Groupe})=1$, $f_1(\hbox{Nom})=A$, $f_1(\hbox{Age})=18$, $f_2(\hbox{Groupe})=1$, etc.
\end{Ex}



\subsubsection{SGBD}

\begin{Def}[SGBD]
Un Système de Gestion de Base de Données Relationnelles (SGBD) \index{SGBD} est une application informatique de définition et de travail sur des relations $n$-aires (non orientées).
\end{Def}





Cette application met en général à la disposition de l'utilisateur un langage (le plus souvent, SQL) qui permet 
\begin{itemize}
\item de définir les objets et leurs liens, de les modifier et d'enrichir la base de données,
\item de retrouver l'information contenue dans la base de données par la formulation de requêtes.
\end{itemize}




\subsection{Projections}

\subsubsection{Définitions}


Soit ${\mathcal{R}}[A]$ une relation $n$-aire d'attributs $A$, et $a\in A$.

On pose $A=\{a\}\union B$, et on suppose que le domaine de $a$ est $D_1$ et que les domaines des attributs de $B$ sont $D_2 \vir \ldots \vir D_n$.



\begin{Def}[Projection d'une relation]
La projection de la relation ${\mathcal{R}}$ suivant $a$ sur $B$, notée ${\mathcal{R}}_a$ (on autorise aussi ${\mathcal{R}}[B]$), est définie par :
$${\mathcal{R}}_a(x_2\vir\ldots\vir x_n)\qquad\Ssi\qquad \exi x_1\in D_1,\ {\mathcal{R}}\famn x.$$ 
\end{Def}


\begin{Rem}
Dans la pratique, on obtient la projection d'une relation :
\begin{itemize}
 \item en supprimant la colonne de l'attribut selon lequel se fait la projection,
 \item et en ne conservant qu'une seule occurrence de lignes qui
seraient devenues identiques.
\end{itemize}
\end{Rem}



\subsubsection{Théorème des projections}

Soit ${\mathcal{R}}[A]$ une relation $n$-aire d'attributs $A$, $a\in A$, $b\in A$ ($b\neq a$).

\begin{Th}[Théorème des projections]
 $$\left({\mathcal{R}}_a\right)_b=\left({\mathcal{R}}_b\right)_a\ .$$
\end{Th}



\begin{Proof}
(Démonstration immédiate). 
\end{Proof}


\begin{Rem}
Ce dernier résultat nous autorise à considérer la projection d'une relation suivant un sous-ensemble d'attributs (et sur le complémentaire de ce sous-ensemble d'attributs). 
\end{Rem}



\begin{Notation}
On notera cette projection ${\mathcal{R}}_B$ (ou ${\mathcal{R}}[A\moins B]$) (si $B\sse A$, c'est la projection suivant $B$ de ${\mathcal{R}}$ sur $C=A\moins B$. 
\end{Notation}





\subsection{Opérations sur les relations $n$-aires}


\subsubsection{Somme et produit}

Soit ${\mathcal{R}}$ une relation d'attributs $A$ et ${\cal S}$ une relation d'attributs $B$, pour lesquelles les attributs de même nom ont même domaine.

Les relations somme ${\mathcal{R}}+{\cal S}$ et produit ${\mathcal{R}}*{\cal S}$ ont pour attributs $A\union B$.

\bigskip

Pour l'énoncé de la définition, comme l'ordre dans lequel on énonce les attributs est sans importance, on suppose que, dans $A\union B$, les éléments sont énumérés dans l'ordre suivant
\begin{itemize}
\item les attributs de $A$ qui ne sont pas dans $B$, les domaines sont $D_1\vir\ldots\vir D_p\,$,
\item les attributs communs à $A$ et à $B$, les domaines sont $D_{p+1}\vir\ldots\vir D_q\,$,
\item les attributs de $B$ qui ne sont pas dans $A$, les domaines sont $D_{q+1}\vir\ldots\vir D_n\,$.
\end{itemize}
(l'un de ces sous-ensembles peut être vide).


\begin{Def}
On a alors, par définition
\begin{itemize}
 \item $({\mathcal{R}}+{\cal S}) (x_1\vir\ldots\vir x_p\vir x_{p+1}\vir\ldots\vir x_q \vir\ldots\vir x_{q+1}\vir
x_n)$ si et seulement si\\ $ {\mathcal{R}} (x_1\vir\ldots\vir x_q)$ ou ${\cal S} (x_{p+1}\vir\ldots\vir x_n)$,
\item $ ({\mathcal{R}}*{\cal S}) (x_1\vir\ldots\vir x_p\vir\ldots\vir x_q\vir\ldots\vir x_n)$ si et seulement si\\ $ {\mathcal{R}} (x_1\vir\ldots\vir x_q)$ et ${\cal S} (x_{p+1}\vir\ldots\vir x_n).$
\end{itemize}
\end{Def}

 

\begin{Notation}
On note $\left({\mathcal{R}}+{\cal S}\right)[A\union B]$ et $\left({\mathcal{R}}*{\cal S}\right)[A\union B]$. 
\end{Notation}




\begin{Ex}
Le domaine de l'attribut Groupe est $\{1,2,3\}$, celui de Nom est $\{$A,B,C$\}$ et celui de Age est $\{19,20,21\}$. 
\end{Ex}


\noindent
\begin{tabular}{cccc}
\begin{tabular}{c|c}
Groupe & Nom \cr
\noalign{\hrule}
1 & A \cr
1 & B \cr
2 & C \cr
\end{tabular}

&

\begin{tabular}{c|c}
Groupe & Age \cr
\noalign{\hrule}
1 & 20 \cr
1 & 21 \cr
2 & 21 \cr
\end{tabular}

&

\begin{tabular}{c|c|c}
Groupe & Nom & Age \cr
\noalign{\hrule}
1 & A & 20 \cr
1 & A & 21 \cr
1 & B & 20 \cr
1 & B & 21 \cr
2 & C & 21 \cr
\end{tabular}

&

\begin{tabular}{c|c|c}
Groupe & Nom & Age \cr
\noalign{\hrule}
1 & A & 19 \cr
1 & A & 20 \cr
1 & A & 21 \cr
1 & B & 19 \cr
1 & B & 20 \cr
1 & B & 21 \cr
1 & C & 20 \cr
1 & C & 21 \cr
2 & A & 21 \cr
2 & B & 21 \cr
2 & C & 19 \cr
2 & C & 20 \cr
2 & C & 21 \cr
\end{tabular}

\cr

Une relation ${\mathcal{R}}$

&

Une relation ${\cal S}$

&

La relation ${\mathcal{R}}*{\cal S}$

&

La relation ${\mathcal{R}}+{\cal S}$

\cr

\end{tabular}

\subsubsection{Réunion et intersection}
C'est le cas particulier de la somme et du produit de deux relations d'attributs $A$ et $B$ dans le cas où $A=B$.


Donc, dans le cas où $A=B$, ${\mathcal{R}}\union{\cal S}={\cal
R}+{\cal S}$ et ${\mathcal{R}}\inter{\cal S}={\mathcal{R}}*{\cal S}$.


\begin{Notation}
On note donc $\left({\mathcal{R}}\union{\cal S}\right)[A]$ et $\left({\mathcal{R}}\inter{\cal S}\right)[A]$ 
\end{Notation}



\subsubsection{Produit cartésien}

Il s'agit du cas particulier du produit de deux relations dans le cas où $A\inter B=\void$.


Donc, dans le cas où $A\inter B=\void$, ${\mathcal{R}}\times{\cal S}={\mathcal{R}}*{\cal S}$.


\begin{Notation}
On note donc $\left({\mathcal{R}}\times{\cal S}\right)[A\union B]$. 
\end{Notation}



\subsection{Sélection d'une relation $n$-aire}

Soit ${\mathcal{R}}[A]$ une relation $n$-aire d'attributs $A$ et $F$ une formule de logique dans laquelle les variables sont des éléments de $A$ et les constantes des éléments du domaine des attributs.


\begin{Def}
La sélection de ${\mathcal{R}}$ suivant $F$ est une relation ayant les mêmes attributs $A$, notée $\left({\mathcal{R}}:F\right)[A]$
et telle que  ${\mathcal{R}}\famn x$ et $F\famn x$. 
\end{Def}


Autrement dit, il s'agit des éléments des domaines des attributs qui sont en relation par ${\mathcal{R}}$ et qui satisfont la formule $F$ donnée.

\begin{Ex}
Sur une relation d'attributs $\{\hbox{Nom}\vir\hbox{Age}\vir\hbox{Note}\}$ on pourra définir la
relation $[(\hbox{Age}\leqslant 19)\ \hbox{et}\ (\hbox{Note}\geqslant 16)]$ pour sélectionner les étudiants admis à s'inscrire au département d'Informatique. 
\end{Ex}



\subsection{Dépendances fonctionnelles et clés}

\subsubsection{Dépendances fonctionnelles}

Il s'agit, lorsque c'est possible, de remplacer une relation $n$-aire par une autre, plus simple, et sans perte d'information.\\


 Soit ${\mathcal{R}}[A]$ une relation d'attributs $A$ telle que $A$ soit de la forme $X\union Y\union Z$.


On suppose pour simplifier  :
\begin{itemize}
 \item que les domaines des attributs de $X$ sont $D_1\vir D_2\vir\ldots\vir D_p$,
 \item que ceux de $Y$ sont $D_{p+1}\vir\ldots\vir D_q$
 \item que ceux de $Z$ sont $D_{q+1}\vir\ldots\vir D_n$.
\end{itemize}


\begin{Def}[Dépendance fonctionnelle]
On dit que $Y$ dépend fonctionnellement de $X$ lorsque l'on a $${\mathcal{R}}(x_1\vir\ldots\vir x_p\vir x_{p+1}\vir\ldots\vir x_q\vir x_{q+1}\vir\ldots\vir x_n)$$ et $${\mathcal{R}}(x_1\vir\ldots\vir x_p\vir x'_{p+1}\vir\ldots\vir x'_q\vir x'_{q+1}\vir\ldots\vir
x'_n)$$ si et seulement si $$x_{p+1}=x'_{p+1}\vir\ldots\vir x_q=x'_q\,$$.
\end{Def}








\begin{Notation}
 Dans la suite, et pour une situation du même type, on s'autorisera à utiliser les notations suivantes :
\begin{itemize}
 \item $D_X$ pour $D_1\vir D_2 \vir\ldots\vir D_p$,
 \item $D_Y$ pour $D_{p+1}\vir\ldots\vir D_q$,
 \item $D_Z$ pour $D_{q+1}\vir\ldots\vir D_n$,
 \item $x$ pour $(x_1\vir\ldots\vir x_p)$,
 \item $y$ pour $(x_{p+1}\vir\ldots\vir x_q)$
 \item et $z$ pour $(x_{q+1}\vir\ldots\vir x_n)$.
\end{itemize}
\end{Notation}



Ainsi, la condition énoncée peut s'écrire plus simplement ${\mathcal{R}}(x,y,z)$ et ${\mathcal{R}}(x,y',z')$ si et seulement si $y=y'$ (cette égalité devant être considérée comme une égalité de $n$-uplets, c'est-à-dire l'égalité composante par composante.


\begin{Ex}
Dans la relation suivante,\\

\centerline{\begin{tabular}{|c|c|c|c|}
\noalign{\hrule}
Groupe & Nom & Niveau & Age \cr
\noalign{\hrule}
1 & A & 1 & 20 \cr
2 & B & 3 & 21 \cr
1 & C & 3 & 20 \cr
1 & A & 3 & 20 \cr
3 & B & 1 & 21 \cr
1 & C & 1 & 20 \cr
2 & A & 1 & 20 \cr
3 & B & 2 & 21 \cr
1 & C & 2 & 20 \cr
\noalign{\hrule}
\end{tabular}}

\medskip

On distingue les dépendances fonctionnelles 
\begin{itemize}
\item $\{$Nom$\}\imp$  $\{$Age$\}$
\item $\{$Groupe , Niveau$\}\imp$  $\{$Age$\}$
\end{itemize}
\end{Ex}



\subsubsection{Théorème des dépendances fonctionnelles}

\begin{Th}[Théorème des dépendances fonctionnelles]
Si la relation ${\mathcal{R}}[A]$ d'attributs $A=X\union Y\union Z$ admet une dépendance fonctionnelle $X\imp Y$, elle est le produit de ses projections sur $X\union Y$ et $X\union Z$.
\end{Th}


\begin{Ex}
La relation précédente est le produit de ses deux projections ${\cal
R}[\{\hbox{Nom}\vir\hbox{Age}\}]$ et ${\mathcal{R}}[\{\hbox{Nom}\vir\hbox{Groupe}\vir\hbox{Niveau}\}]$.
\end{Ex}



\subsubsection{Clés}

\begin{Def}[Clé]
Pour une relation ${\mathcal{R}} [A]$ d'attributs $A$, une \emph{clé} \index{clé} est un sous-ensemble minimal $K$ de $A$ tel qu'il existe une dépendance fonctionnelle $C\imp A\moins K$.


($K$ est un sous-ensemble minimal au sens qu'il n'y a pas de partie stricte $K'$ de $K$ pour laquelle il existe une dépendance fonctionnelle $K'\imp A\moins K'$).
\end{Def}

\begin{Rem}
Cette \og minimalité\fg{}   n'entraîne en aucune manière l'unicité de la clé pour une relation donnée. 
\end{Rem}

\begin{Th}
Pour toute relation, il est possible d'introduire un attribut dont les valeurs sont toutes différentes, et qui constitue donc une clé pour la nouvelle relation obtenue (par exemple, une numérotation). 
\end{Th}






\gsaut
\centerline{\x{Fin du Chapitre}}