Relations, applications
\(\def\Id{{\text{Id}}}\def\rel{\,{\mathscr R}\,}\def\rg{{\rightarrow}}\def\Rg{{\Rightarrow}}\def\iff{{\;\Leftrightarrow\;}}\def\N{{\mathbb N}}\def\Z{{\mathbb Z}}\def\Q{{\mathbb Q}}\def\R{{\mathbb R}}\)

Relations, fonctions, applications

Mettre en relation des entités de toute nature est une opération commune et universelle. Le dé­ve­lop­pe­ment rapide des techniques, rebaptisées technologies par tropisme anglophile, n'a-t-il pas trans­for­mé notre planète en monde connecté ? Connecter, associer, relier, joindre, etc. sont des opérations incontournables, fon­da­men­ta­les et om­ni­pré­sen­tes en informatique et en ma­thé­ma­ti­ques.

Relations et correspondances

Soit \(q\) un entier non-nul et \(X_1,X_2,\ldots, X_q\) des ensembles. On appelle re­la­tion \(q\)-aire entre les ensembles \(X_i\) tout prédicat \(\rel\) à \(q\) variables \(x_i\) à valeur dans l'ensemble \(X_i\) res­pec­ti­ve­ment. Tous les termes \(x_i\) d'un \(q\)-uplet \((x_1,x_2,\ldots, x_q)\) tel que \({\rel}(x_1,x_2,\ldots, x_q)\) est vrai sont dits en re­la­tion par \(\rel\).

On parle de re­la­tion unaire quand \(q=1\), de re­la­tion binaire quand \(q=2\), de re­la­tion ternaire quand \(q=3\), etc. La re­la­tion de pa­ren­ta­li­té est un exemple de re­la­tion ternaire entre pères, mères et enfants. Les couples formés par deux individus définissent une re­la­tion binaire. La pos­si­bi­li­té ou non d'as­sem­bler deux pièces d'un puzzle définit une re­la­tion binaire entre les différentes pièces du puzzle, etc.

Parmi tous les types de relations, les relations binaires sont les plus utilisées et font l'objet d'une attention toute particulière. Con­si­dé­rons une re­la­tion binaire \(\rel\) entre deux ensembles \(X\) et \(Y\). Le sous-­ensemble \(G\subseteq X\times Y\) des couples \((x,y)\) qui sont en re­la­tion pour \(\rel\), c'est-à-dire \begin{equation} G:=\{(x,y)\in X\times Y\mid {\rel}(x,y)\} \end{equation} existe d'après l'axiome de sélection, on l'appelle graphe de la re­la­tion binaire \({\rel}\). Une section spé­ci­fi­que de ce chapitre sera consacrée aux re­la­tions binaires entre éléments d'un même ensemble, i.e. \(Y=X\).

Le jumelage entre communes françaises et étrangères constitue une re­la­tion binaire. Ainsi la ville de La Garde est jumelée avec la ville de Montesarchio en Italie ainsi que la ville de Spa en Belgique. Un jumelage fait correspondre certaines communes françaises à certaines communes étran­gères.

Dans le cadre de l'étude des fonctions, une re­la­tion binaire est souvent appelée correspondance, sa dé­fi­ni­tion s'appuie directement sur un graphe sans faire référence à un prédicat pour le définir :
Soient \(X\) et \(Y\) deux ensembles et \({\color{#FF0}G}\subseteq X\times Y\) un graphe. Le triplet \((X,{\color{#FF0}G},Y)\) est appelé correspondance d'ensemble de départ \(X\), d'ensemble d'arrivée \(Y\) et de graphe \({\color{#FF0}G}\).

On représente souvent une correspondance à l'aide d'un diagramme sagittal*(*) En forme de flèche. qui fournit une in­ter­pré­ta­tion plus concrète du graphe. Les ensembles de départ \(X\) et d'arrivée \(Y\) sont représentés par deux patates, et chaque couple \({\color{#FF0}(x,y)}\in G\) du graphe par une flèche reliant \(x\) à \(y\), \(x\,{\color{#FF0}\rg}\,y\). Ce symbole a pour premier mérite de mettre en évi­dence l'asymétrie du couple, on rappelle en effet que \((x,y)\not=(y,x)\).

Diagramme sagittal du jumelage de certaines villes.

Le diagramme sagittal ci-dessus illustre le jumelage de quelques villes. On constate que les villes de Mazaugues et Signes ne sont pas jumelées avec des villes étrangères et que les villes étran­gères de Liski et Vegen ne correspondent à aucun jumelage.

Décrivez en extension les ensembles de départ, d'arrivée et le graphe \( G\) de la cor­res­pon­dan­ce définie par le diagramme ci-dessus.
Nous avons noté \((X,{\color{#FF0}G},Y)\) une correspondance alors que dans la littérature ma­thé­ma­ti­que, une correspondance est souvent représentée par un triplet \((X,Y,{\color{#66F}G})\) (rarement \(({\color{#F66}G},X,Y)\)). Formellement, ces différentes écritures définissent des modèles distincts, mais le triplet joue simplement le rôle d'une boite à trois casiers pour y ranger les données qui ca­rac­té­ri­sent l'objet à modéliser, ces trois modèles sont donc strictement équivalents. La mo­ti­va­tion de la position infixe plutôt que postfixe ou préfixe du graphe \(G\) dans le triplet est didactique, le graphe \(G\) est la description abstraite des flèches du diagramme qui se situent entre les en­semb­les \(X\) et \(Y\). L'écriture usuelle postfixe est évidemment justifiée par le fait que nous lisons de gauche à droite et qu'il est logique de présenter les deux ensembles \(X\) et \(Y\) avant de parler du graphe qui en dépend.

En inversant le sens des flèches du diagramme sagittal d'une cor­res­pon­dan­ce \(c=(X,G,Y)\) et en in­ver­sant les rôles des ensembles de départ \(X\) et d'arrivée \(Y\) on obtient une nouvelle cor­res­pon­dan­ce ap­pe­lée cor­res­pon­dan­ce réciproque de \(c\) et on la note \(c^{-1}\). Attention, il s'agit d'une no­ta­tion, qui ne désigne pas le rapport \(\frac{1}{c}\) ce qui n'aurait aucun sens ici !

Écrivez la définition de la cor­res­pon­dan­ce réciproque d'une cor­res­pon­dan­ce \(c=(X,G,Y)\).

Fonctions

Une fonction désigne un type de cor­res­pon­dan­ce particulière telle qu'il y a au plus une flèche qui part d'un élément \(x\in X\). C'est la transposition mathématique du terme largement employé dans le langage courant. Le montant à régler au parcmètre est fonction de la durée de stationnement, votre note au contrôle continu de l'ecue de Mathématiques pour l'Informatique est fonction du nombre de bonnes réponses, etc. Dans ce contexte, il ne peut y avoir qu'un seul montant à régler qui cor­res­pond avec la durée de stationnement et qu'une seule note qui cor­res­pond avec le nombre de bonnes ré­pon­ses.

Ainsi, l'exemple de la figure 1 n'est pas une fonction car, entre autres, la ville de La Garde est en cor­res­pon­dan­ce avec deux villes étrangères. La condition à respecter pour qu'une cor­res­pon­dan­ce définisse une fonction s'exprime for­mel­le­ment de la manière suivante :

Une cor­res­pon­dan­ce \(f=(X,G,Y)\) est appelée cor­res­pon­dan­ce fonctionnelle ou plus simplement fonction si et seulement si elle satisfait la condition suivante : \begin{equation} \label{eq:corrfon} \forall x\in X\ \ \forall (y,z)\in Y\times Y\quad \big((x,y)\in G\ \wedge\ (x,z)\in G\big)\Rightarrow y=z. \end{equation}

La façon d'exprimer mathématiquement au plus dans cette expression formelle peut sembler sur­pre­nante mais elle répond bien à la contrainte : si deux couples ayant même première projection appartiennent au graphe de la cor­res­pon­dance, leurs deuxièmes projections sont né­ces­sai­re­ment éga­les, autrement dit ces deux couples sont égaux.

Exprimez formellement qu'une correspondance n'est pas fonctionnelle en écrivant la négation de l'expression \((\ref{eq:corrfon})\). Réécrivez la définition d'une fonction en remplaçant l'expression \((\ref{eq:corrfon})\) par sa contraposée.

Dans le diagramme ci-dessous nous représentons la fonction qui associe le taux de tva à une activité ou une vente (si elle est assujettie à cette taxe).

Diagramme sagittal d'une fonction \(f=(X,{\color{#FF0}G},Y)\).

Comme on peut le constater par l'absence d'une flèche, les soins d'une carrie dentaire ne sont pas assujetis à la tva (les actes médicaux ne sont pas soumis à cette taxe). On aurait pu rajouter un taux de \(0\%\) dans l'ensemble d'arrivée et inclure le couple \((\text{carrie},0\%)\) au graphe \( G\), mais il est plus cohérent de le modéliser sans cet arc puisque la tva ne s'applique pas aux actes médicaux. On note également que certains taux de tva ne correspondent à aucune activité/vente.

Soit \(f=(X,G,Y)\) une fonction et \(x\in X\). S'il existe un élément \(y\in Y\) tel que \((x,y)\in G\), on dit que \(f\) est définie en \(x\) et que \(y\) est l'image de \(x\) par \(f\), on la note \(f(x)\). Dans le cas contraire on dit que \(f\) n'est pas définie en \(x\). Réciproquement soit \(y\in Y\). S'il existe un élé­ment \(x\in X\) tel que \((x,y)\in G,\) on dit que \(x\) est un antécédent de \(y\) par \(f\).

La fonction \(f\) associée au diagramme de la figure 2 n'est pas définie en carrie. L'image de cinéma est \(2,1\%\), ce que l'on écrit \(f(cinema)=2,1\%\). Il est important de réaliser que la notation \(f(x)\) n'a de sens que si la fonction \(f\) est définie en \(x\). Autant il y a au plus une image pour un élément \(x\in X\) par une fonction \(f\), autant il peut y avoir plusieurs antécédents à un élément \(y\in Y\). Par exemple smartphone et alcool sont deux antécédents de \(20\%\). Les valeurs \(15\%\), \(30\%\) et \(75\%\) n'admettent pas d'antécédents.

Le lecteur averti pourrait contester ce modèle ma­thé­ma­ti­que simplifié en avan­çant que la tva de certains produits dépend du lieu de consommation. En effet, la tva ap­pli­quée à une glace est différente selon qu'elle est consommée sur place \((5,5\%)\) ou emportée \((10\%)\). Au­tre­ment dit, il faudrait deux flèches pour la glace, une vers la valeur \(5,5\%\), l'autre vers \(10\%,\) le bon modèle mathématique serait alors la cor­res­pon­dan­ce. Ce modèle serait tout de même incomplet, puisque l'information codant le fait que la glace est consommée ou non sur place n'est pas intégrée au modèle. Ce type de modélisation sera étudié en détail dans l'enseignement de théorie des graphes de la licence.

Parfois l'image d'un élément \(x\) de \(X\) par une fonction \(f\) peut être calculée. En effet, nous verrons dans un prochain chapitre que les ensembles peu­vent être équipés de lois de composition internes, comme l'addition ou la multiplication par exemple. Dans ce cas, cela induit une vision dynamique de la fonction*(*) l'utilisation mas­sive de flèches renforce éga­le­ment cette dynamique., comme s'il s'agissait d'une machine qui traitait la matière première \(\color{#FF0}x\) en entrée et qui fournissait le produit fini \(\color{#BBF}y\) en sortie :

\(\longrightarrow\) \(\longrightarrow\) y
Vision schématique d'une fonction calculable.

Par exemple la fonction définie par \(f(r):=2\pi r\) sur les ensembles \(X=Y={\R}\) calcule la circonférence d'un cercle en fonction de son rayon \(r\). On utilise souvent la notation classique suivante pour définir une telle fonction (noter le talon de la flèche qui relie un élément de l'ensemble de départ à l'en­sem­ble d'arrivée) : \begin{align} \label{fonc:circonf} f:{\R}&\longrightarrow {\R}\\ \notag r&\longmapsto 2\pi r \end{align}

Il n'est pas toujours possible de calculer une fonction. La théorie de la calculabilité enseignée en mas­ter d'informatique a précisément pour objectif d'étudier les questions de cette nature et d'en déduire des résultats sur ce que les ordinateurs sont capables de calculer ou non.

Soit \(f=(X,G,Y)\) une fonction. On appelle domaine de définition de \(f\) le sous-ensemble \({\mathscr D}_f\subseteq X\) constitué des éléments de \(X\) qui admettent une image par \(f\) : \[ {\mathscr D}_f:=\{x\in X\mid\ \exists y\in Y\ \ y=f(x)\}. \]

Le domaine de définition de la fonction dont le diagramme sagittal est donné en figure 2 est :

\begin{equation} \label{liste} {\mathscr D}_f=\{glace,\ alcool,\ cinéma,\ smartphone,\ livre\}. \end{equation}

Si une cor­res­pon­dan­ce \(f=(X,G,Y)\) est une fonction, on la décrit plus simplement par la notation \[ f:X\rightarrow Y \] qui ne mentionne plus son graphe \(G\). Cette notation est justifiée par le fait que \(f\) étant une fonction, elle est définie en tout élément \(x\in {\mathscr D}_f\). Par conséquent son graphe \(G\) est constitué par l'ensemble des coup­les \((x,f(x)),\ x\in{\mathscr D}_f\), il est donc défini implicitement.

Définissez le domaine de définition \({\mathscr D}_f\) d'une fonction \(f:X\rg Y\) avec une écriture en com­pré­hen­sion. Comment qualifie-t-on l'écriture \((\ref{liste})\) de l'ensemble \({\mathscr D}_f\) ?

Applications

Une fonction \(f=(X,G,Y)\) dont l'ensemble de départ est con­fon­du avec son do­mai­ne de définition, i.e. telle que \(X={\mathscr D}_f\), est appelée application de \(X\) dans \(Y.\)

La fonction \((\ref{fonc:circonf})\) est une application, elle est bien définie en tout réel \(r\). En revanche, la fonction

\begin{align} \label{fonc:inverse} f:{\R}&\longrightarrow {\R}\\ \notag x&\longmapsto\frac{1}{x} \end{align}

n'est pas une application puisqu'elle n'est pas définie en \(0\). Son domaine de définition est l'ensemble \({\mathscr D}_f={\R}\setminus\{0\}\). Notons que si cette fonction n'est pas définie en \(0\), ce n'est pas pour un quelconque interdit, mais parce qu'elle est définie via son graphe qui est constitué des couples \((x,y)\in{\R}\times{\R}\) satisfaisant l'équation \(xy=1.\) Ce graphe ne contient donc aucun couple \((x,y)\) tel que \(x=0\) ou \(y=0\).

On dit que deux applications \(f:X\rg Y\) et \(g:X'\rg Y'\) coïncident sur une partie \(A\subseteq X\cap X'\) si et seu­le­ment si elles sont égales en tout élément de \(A\) :

\begin{equation} \forall x\in A\quad f(x)=g(x). \end{equation}

Soit \(f:X\rg Y\) une application et \(A\) une partie de \(X\). L'application de \(A\rightarrow Y\) qui coïncide avec \(f\) sur \(A\) est ap­pe­lée restriction de \(f\) à \(A\) et notée \(f|A\).

Il est très facile d'obtenir une application à partir d'une fonction qui n'est pas définie en tout point de son ensemble de départ \(X\). Il suffit de remplacer \(X\) par le domaine de définition \({\mathscr D}_f\) de cette fonc­tion, autrement dit de considérer sa restriction \(f|{\mathscr D}_f\). Dans le cas de la fonction de la figure 2, il suffit d'éliminer carrie de l'en­sem­ble \(X\), i.e. le nouvel ensemble de départ est \(X':={\mathscr D}_f\) :

Diagramme sagittal de l'application obtenue par res­tric­tion de cette fonction à son domaine de définition.

Quant à la fonction \(f\) définie en \((\ref{fonc:inverse})\), il suffit d'éliminer \(0\) pour en faire une application, il s'agit de la fonction \(g:{\R}\setminus\{0\}\rg{\R}\) définie par \(g(x):=\frac{1}{x}.\) Attention, \(g\not=f\), en effet il faut se souvenir qu'une fonction est avant tout une cor­res­pon­dan­ce, c'est-à-dire un triplet, or deux triplets sont égaux si et seulement si leurs trois projections sont égales respectivement. Autrement dit deux cor­res­pon­dan­ces sont égales si et seu­le­ment si elles ont même en­sem­ble de départ, même ensemble d'arrivée et même graphe.

L'ensemble des applications de \(X\) dans \(Y\) est noté \(Y^X\). Cette notation peut sembler étrange à pre­miè­re vue, mais nous verrons pourquoi il s'agit d'une bonne notation dans le chapitre consacré à la com­binatoire.

Soient \(X,Y,X',Y'\) des ensembles tels que \(X\subseteq X'\) et \(Y\subseteq Y'\). On considère deux ap­pli­ca­tions \(f:X\rg Y\) et \(g:X'\rg Y'\). Quelle définition proposez-vous pour exprimer que \(g\) est un prolongement de \(f\) selon votre acception du terme prolongement ?
Fonctions et applications sont deux concepts très voisins en théorie des en­semb­les. Historiquement le terme fonction était plutôt utilisé pour exprimer qu'une quantité physique variait selon une autre quantité physique (autrement dit les fonctions numériques de \({\R}\) dans \({\R}\)) alors que le terme application avait une connotation plus géométrique, comme une carte. Le terme anglo-saxon map qui est la traduction du mot application est explicite à ce sujet.

Si la cor­res­pon­dan­ce réciproque \(f^{-1}\) d'une fonction \(f\) est elle-même une fonction, elle est appelée fonction réciproque. La section suivante est consacrée à l'étude des cor­res­pon­dan­ces ré­ci­pro­ques et de leur statut.

Les cor­res­pon­dan­ces réciproques des cor­res­pon­dan­ces des figures 1 & 2 définissent-elles des fonctions ? La fonction de \({\R}\) dans \({\R}\) définie par \(x\mapsto x^2\) est-elle une application ? Sa cor­res­pon­dan­ce ré­ci­pro­que est-elle une fonction ?
Une correspondance \(f:=(X,G,Y)\) est fournie via son graphe codé dans un fichier texte contenant un couple du graphe par ligne du fichier. Chaque couple est simplement encodé par deux valeurs séparées par le symbole strictement supérieur  : x > y. Une ligne contenant > y sans premier membre (resp. x > sans second membre) permet de coder des éléments dans l'ensemble de départ (resp. d'arrivée) qui ne sont pas en relation avec des éléments de l'ensemble d'arrivée (resp. de départ).

Écrivez une fonction Python Lecture() qui lit ce fichier et renvoie un dictionnaire qui code la cor­res­pon­dance. Les clefs du dictionnaire sont les premières projections et on associe à chaque clef \(x\) la liste des \(y\) tels que \((x,y)\in G\). Écrivez une fonction Python inverse qui renvoie la correspondance inverse.

On rappelle que l'ouverture d'un fichier en lecture et la création de la liste des chaînes de caractères correpondant aux différentes lignes du fichier texte s'obtiennent grâce aux instructions
 fichier = open("nomfichier","r")
 liste = fichier.readlines()
On découpe une chaîne de caractères chaine suivant un séparateur sep (une chaîne de caractère également, par défaut un espace) grâce à la méthode split(sep) qui renvoie la liste des sous-chaînes séparées par la chaîne sep. Ici on obtient la liste constitué des deux termes du couple en utilsant le symbole > comme séparateur :
 couple = chaine.split(">")
Écrivez une fonction Python EstFonction(f) qui décide (renvoie vrai ou faux) si la correspondance \(f\) est une fonction. Écrivez une fonction Python EstApplication(f) qui décide si une correspondance est une application.

Injections, surjections, bijections

Quand on se donne une cor­res­pon­dan­ce, il est naturel de s'intéresser à la cor­res­pon­dan­ce réciproque (voir exercice), ne serait-ce que parce que sa construction est extrêmement simple, il suffit d'inverser le sens des flèches et d'échanger le rôle de l'ensemble de départ et de l'ensemble d'arrivée. L'étude de la réversibilité du processus est intéressante, en particulier quand il s'agit d'une fonction calculable.

On réalise immédiatement en construisant la cor­res­pon­dan­ce réciproque de l'application de ce dia­gram­me que celle-ci n'est plus une application, (ni \(30\%\), ni \(75\%\) n'ont d'image), ni mê­me une fonction (deux flè­ches partent de la valeur \(20\%\)). Quelles sont les conditions que doit satisfaire une application pour que sa cor­res­pon­dan­ce réciproque soit une fonction, ou mieux une application ?

Pour que la cor­res­pon­dan­ce réciproque soit une fonction, il ne faut pas que deux éléments distincts \(x_1\) et \(x_2\) de l'ensemble de départ aient la même image \(y\) (comme smart­phone et alcool qui ont la même tva à \(20\%\)), sans quoi la cor­res­pon­dan­ce inverse aurait deux flèches partant de \(y\), l'une vers \(x_1\) et l'autre vers \(x_2\) ce qui est interdit pour une fonction.

Injections

Soit \(f=(X,G,Y)\) une application. On dit que \(f\) est une application injective ou plus simplement une injection si deux éléments distincts de \(X\) ont des images distinctes dans \(Y\) : \begin{equation}\label{eq:injection} \forall x_1,x_2\in X\quad x_1\not=x_2\Rightarrow f(x_1)\not=f(x_2). \end{equation}

C'est souvent la contraposée de l'expression logique \((\ref{eq:injection})\) qui est utilisée pour démontrer qu'une ap­pli­ca­tion est injective : \begin{equation}\label{eq:injectioncontraposée} \forall (x_1,x_2)\in X\times X\quad f(x_1)=f(x_2)\Rightarrow x_1=x_2. \end{equation}

Indépendamment de l'étude des cor­res­pon­dan­ces réciproques, l'in­jec­ti­vi­té est une propriété fort in­té­res­sante et qui est souvent nécessaire pour définir certains modèles. Pour établir une communication té­lé­pho­ni­que, on cherche a priori à exclure la possiblité que deux numéros de téléphone soient as­so­ciés à la même carte sim*(*) Subscriber Identity Module, la table de cor­res­pon­dan­ce dont disposent les opérateurs n'est ni plus ni moins qu'une application in­jec­ti­ve. De la même manière, deux numéros de sécurité sociale dis­tincts sont associés à des in­di­vi­dus dis­tinc­ts, etc.

À gauche une application injective, à droite non.

Soient \(X\) et \(Y\) deux ensembles tels que \(X\subseteq Y\). L'application \(f:X\rg Y\) définie par \(f(x):=x\) est une injection appelée injection canonique. Si \(Y=X\), cette application est appelée application iden­ti­té de \(X\) et on la note \(\text{Id}_X\).

Une injection \(f\) admet donc une correspondance réciproque \(f^{-1}\) qui est une fonction. Si l'on veut que cette fonction réciproque soit également une application, il faut également que tous les éléments de l'ensemble d'arrivée soient atteints par une flèche de manière à ce que tous les éléments de l'ensemble \(Y\) aient une image pour la cor­res­pon­dan­ce réciproque.

Surjections

Soit \(f=(X,G,Y)\) une application. On dit que \(f\) est une application surjective ou plus simplement une surjection si tout élément \(y\in Y\) admet (au moins) un antécédent dans \(X\) : \begin{equation}\label{eq:sujection} \forall y\in Y\ \ \exists x\in X\quad y=f(x). \end{equation}

Cette propriété peut être satisfaite sans que l'application soit injective, il peut donc y avoir plus d'un antécédent. C'est le cas de l'application à gauche dans la figure ci-dessous, elle est surjective mais pas injective. Celle de droite n'est ni injective ni surjective.

À gauche une application surjective, à droite non.

Bijections

Soit \(f=(X,G,Y)\) une application. On dit que \(f\) est une application bijective ou plus simplement une bijection si elle est à la fois injective et surjective.

On aurait tout aussi bien pu donner la définition suivante : une application \(f\) est bijective si et seu­le­ment si sa cor­res­pon­dan­ce réciproque \(f^{-1}\) est une application.

Une bijection associe de manière unique chaque élément d'un ensemble à un autre et ré­ci­pro­que­ment. Si les ensembles de départ et d'arrivée sont par exemple constitué respectivement par des étu­diant(e)s de sciences et de lettres, disposer d'une bi­jec­tion revient à créer des couples monogames où chacun a exactement un(e) petit(e) ami(e) :

Diagramme sagittal d'une application bijective.

Les trois notions, injection, surjection et bijection sont absolument fondamentales en mathématiques et en informatique. Ces objets servent non seulement à la modélisation mais également à compter (entre autres). Avant même d'avoir défini ce qu'est un ensemble fini*(*) la compréhension in­tui­ti­ve du concept est suf­fi­san­te ici., il semble évident que si les ensembles de départ et d'arrivée sont finis et en bijection, ils ont le même nombre d'éléments. Il n'est pas rare que l'on dénombre les éléments d'un ensemble en établissant une bijection avec un autre en­sem­ble dont on connaît le cardinal. Dans le même ordre d'idées et intuitivement, disposer d'une injection (resp. une surjection) entre un ensemble \(X\) et un ensemble \(Y\) impose que l'ensemble \(Y\) est plus grand que \(X\) (resp. plus petit que \(X\)).

Soient \(X\) et \(Y\) deux ensembles. Démontrez que les deux assertions suivantes sont équi­va­len­tes 
  1. il existe une injection de \(X\) dans \(Y\) ;
  2. il existe une surjection de \(Y\) dans \(X\).

Composition des applications

Si l'on se donne deux cor­res­pon­dan­ces \(f=(X,G,Y)\) et \(g=(Y,H,Z)\) telles que l'ensemble d'arrivée de la première coïncide avec l'ensemble de départ de la seconde, il est tentant de rabouter les flèches et d'observer pour chaque élément de \(X\) quels sont les éléments correspondants dans \(Z\) en suivant les chemins constitués par les flèches :

Diagramme sagittal de deux cor­res­pon­dan­ces.

On observe dans le diagramme ci-dessus que \(a\) est associé à \(u\), \(b\) à \(w\), \(c\) à \(w\), \(e\) à \(u\) et \(w\) et \(d\) à \(w\). Il s'agit évidemment d'une cor­res­pon­dan­ce entre les ensembles \(X\) et \(Z\). Il ne reste qu'à la définir for­mel­le­ment.

Soient \(f=(X,G,Y)\) et \(g=(Y,H,Z)\) deux cor­res­pon­dan­ces. On appelle com­po­si­tion des cor­respondances \(f\) et \(g\) la cor­res­pon­dan­ce \(h=(X,I,Z)\) dont le graphe est défini par \begin{equation} I:=\{(x,z)\in X\times Z\ |\ \exists y\in Y\ \ (x,y)\in G\ \wedge\ (y,z)\in H\}. \end{equation} On note cette cor­res­pon­dan­ce \(g\circ f\) (que l'on lit \(g\) rond \(f\)).
Il ne faut pas être perturbé par l'ordre dans lequel on écrit la composition \(g\circ f\) alors que la correspondance \(f\) s'applique avant la correspondance \(g\). Nous mettons souvent et très logiquement la chronologie des événements que nous décrivons en cohérence avec l'ordre de lecture. Ici il faut simplement se souvenir que la notation des cor­res­pon­dan­ces est préfixe, et comme la cor­res­pon­dan­ce \(g\) s'applique après la cor­res­pon­dan­ce \(f\), elle agit sur \(f(x)\) soit \(g(f(x))\). Si les cor­res­pon­dan­ces avaient été notées de manière postfixe, i.e. \((x)f\) au lieu de \(f(x)\), tout rentrerait dans l'ordre…
Soient \(f=(X,G,Y)\), \(g=(Y,H,Z)\) et \(h=(Z,I,T)\) trois cor­res­pon­dan­ces. Vérifiez que \begin{equation} h\circ(g\circ f)=(h\circ g)\circ f. \end{equation} Cette propriété est appelée associativité de la composition.

Dans la suite nous n'utiliserons la composition que dans le cas où les cor­res­pon­dan­ces \(f\) et \(g\) sont des applications. Un premier résultat important sur les bijections est lié à la composition des ap­pli­ca­tions.

La composée de deux applications injectives (resp. surjective, bijective) est injective (resp. surjective, bijective).
Notons \(f:X\to Y\) et \(g:Y\to Z\) ces applications. Supposons que \(g\circ f\) soit injective. Alors pour tout \((x,x')\in X^2\) tel que \(x\not=x'\), on a \(g(f(x))\not= g((f(x'))\) ce qui impose que \(f(x)\not = f(x')\) c'est-à-dire que \(f\) soit injective. Supposons que \(g\circ f\) soit surjective. Alors pour tout \(z\in Z\), il existe \(x\in X\) tel que \(g(f(x))=z\), donc \(z\) admet au moins \(f(x)\) comme antécédent par \(g\) qui est par conséquent surjective.
Une application \(f:X\rg Y\) est bijective si et seulement s'il existe une application \(g:Y\rg X\) telle que \begin{equation} \label{eq:gof} g\circ f = \text{Id}_X\ \ \text{et}\ \ f\circ g = \text{Id}_Y. \end{equation} Dans ce cas, l'application \(g\) est unique, il s'agit de l'application réciproque \(f^{-1}\) de \(f\) appelée bi­jec­tion réciproque.
S'il existe \(g:Y\to X\) qui satisfait \((\ref{eq:gof})\), alors d'après la proposition précédente, \(f\) est surjective comme \(\Id_Y\) et elle est injective comme \(\Id_X\) donc bijective. Symétriquement \(g\) est bijective. D'autre part, si \(f:X\to Y\) est bijective, alors il existe une application \(g:Y\to X\) qui satisfait \((\ref{eq:gof})\), c'est l'application qui a tout élément de \(Y\) associe son unique antécédent par \(f\). On conclut avec l'unicité, considérons deux applications \(g_1\) et \(g_2\) qui satisfont \((\ref{eq:gof})\), alors \begin{align*} g_1\circ f\circ g_2&=\Id_X\circ g_2=g_2\\ g_1\circ f\circ g_2&=g_1\circ \Id_Y=g_1 \end{align*} Et on en déduit que \(g_1=g_2\).

Soit \(f:X\rg X\) une application. On peut donc composer \(f\) avec elle même puisque les ensembles de départ et d'arrivée sont confondus. Par convention, on note \(f^n:=f\circ f^{n-1}\) avec \(f^0:=\text{Id}_X\). L'ap­pli­ca­tion \(f^n\) est ap­pe­lée \(n\)-ème itérée de \(f\). Une application bijective \(f:X\rg X\) telle que \(f^2=\text{Id}_X\) est appelée in­vo­lu­tion ou dite involutive, autrement dit elle est sa propre bijection réciproque. Par exemple l'ap­pli­ca­tion \(f:\R^*\rg\R^*\) définie par \(x\mapsto\frac{1}{x}\). Une application \(f:X\rg X\) telle que \(f^2=f\) est dite idem­po­ten­te. Par exemple la valeur absolue dans \(\R\), en effet \(||x||=|x|\).

Soit \(f:X\rg Y\) et \(g:Y\rg Z\) deux bijections. Démontrez que \begin{equation} \left(g\circ f\right)^{-1} = f^{-1}\circ g^{-1}. \end{equation} Généralisez à la composition de \(n\) applications \(f_1,\,f_2,\ldots,f_n\) où pour tout \(i\in\{1,2,\ldots,n\}\), \(f_i:X_i\to Y_i\) avec \(Y_i=X_{i+1}\) : \begin{equation} \left(f_n\circ f_{n-1}\circ\cdots\circ f_{2}\circ f_1\right)^{-1} = f_1^{-1}\circ f_2^{-1}\circ\cdots\circ f_{n-1}^{-1}\circ f_{n}^{-1}. \end{equation}

Images directes et réciproques

Soit \(f:X\rg Y\) une application et \(A\) une partie de l'ensemble de départ \(X\). On définit l'image directe de \(A\) par \(f\), que l'on note \(f(A)\), comme le sous-ensemble de \(Y\) constitué par toutes les images \(f(x)\) des éléments \(x\in A\) :

\begin{equation} f(A):=\{y\in Y\mid \exists x\in A\ \ y=f(x)\}. \end{equation}

On définit l'image réciproque notée \(f^{-1}(B)\) d'une partie \(B\) de \(Y\) par \(f\), comme le sous-ensemble de \(X\) constitué par tous les éléments \(x\) dont l'image appartient à \(B\) :

\begin{equation} f^{-1}(B):=\{x\in X\mid f(x)\in B\}. \end{equation}

On rappelle que \({\mathscr P}(X)\) désigne l'ensemble des parties d'un ensemble \(X\). Soit \({\color{#F88}A:=\{g,b,e\}}\in{\mathscr P}(X)\) et \({\color{#88F}B:=\{0,7,8\}}\in{\mathscr P}(Y)\) pour l'application \(f:X\rg Y\) définie par le diagramme sagittal ci-dessous. On a \(f({\color{#F88}A})=\{5,1\}\) et \(f^{-1}({\color{#88F}B})=\{a,c,d\}\).

Diagramme sagittal d'une application \(f:X\rg Y\). L'en­semb­le \(A\) (resp. \(B\)) est une partie de \(X\) (resp. de \(Y\)).
Avec la fonction définie par le diagramme sagittal de la figure 8, calculez
  1. \(f(X)\),
  2. \(f^{-1}(\{0,-2\})\),
  3. \(f^{-1}(f(\{e,c\}))\),
  4. \(f(f^{-1}(\{5,8\}))\),
  5. \(f^{-1}(\varnothing)\).
En toute rigueur, les notations \(f(A)\) ou \(f^{-1}(B)\) ne sont pas cor­rectes. En effet, \(f\) est définie sur l'ensemble \(X\) et la cor­res­pon­dan­ce réciproque \(f^{-1}\) sur l'en­semble \(Y\), or \(A\) n'est pas un élément de \(X\) mais de \({\mathscr P}(X)\) et \(B\) n'est pas un élément de \(Y\) mais de \({\mathscr P}(Y)\). Il faut donc définir deux applications \(\hat f:{\mathscr P}(X)\rg {\mathscr P}(Y)\) et \(\check f:{\mathscr P}(Y)\rg {\mathscr P}(X).\) On sacrifie comme souvent la rigueur à la simplicité, d'autant que cet abus de langage ne prê­te pas à conséquence.

Attention néanmoins à ne pas confondre \(f(\{x\})\) avec \(f(x)\), ainsi avec l'exemple de la figure ci-dessus, on a \(f(\{c\})=\{7\}\) alors que \(f(c)=7.\) Dans l'autre sens, il ne faut surtout pas confondre \(f^{-1}(\{y\})\) avec \(f^{-1}(y)\), la confusion est encore plus grave. En effet, autant l'image ré­ci­pro­que \(f^{-1}(\{y\})\) existe toujours, autant l'expression \(f^{-1}(y)\) n'a de sens que si la cor­res­pon­dan­ce réciproque \(f^{-1}\) de \(f\) est bien une fonction et définie en \(y\) de surcroît ce qui impose que \(f\) soit injective et que \(y\in{\mathscr D}_{f^{-1}}\). Cependant, les abus de langage sont légions et il n'est pas rare de voir écrit \(f^{-1}(y)\) au lieu de \(f^{-1}(\{y\})\) quand bien même la fonction n'est pas injective. Tout ceci est sans conséquence si l'on comprend ce que l'on fait et les objets que l'on manipule. Avec l'exemple précédent, on a \(f(c)=7\), alors que \(f(\{c\})=\{7\}.\) Pour l'application injective dans la figure 5 à gauche, \(f^{-1}(\{7\})=\{c\}\) alors que \(f^{-1}(7)=c.\)

L'image directe \(f(X)\) de l'ensemble de départ est appelée image de \(f\) et notée \(\text{Im}(f)\). De la même ma­niè­re que l'on transforme facilement une fonction \(f:X\rg Y\) en application en remplaçant son en­semb­le de départ \(X\) par le domaine de définition \({\mathscr D}_f\), on transforme une application quelconque en surjection en remplaçant son ensemble d'arrivée \(Y\) par son image \(\text{Im}(f)\).

Montrez qu'une application \(f:X\rg Y\) est une bijection si et seulement s'il existe une ap­pli­ca­tion \(g:Y\rg X\) telle que \begin{align} \label{eq:idcirc} g\circ f=\text{Id}_X\quad&\text{et}\quad f\circ g=\text{Id}_Y. \end{align} Montrez dans ce cas que \(g\) est l'application réciproque \(f^{-1}\) de \(f\).

Soit \(f:X\rg X\) une application. On dit que \(A\subseteq X\) est une partie stable par \(f\) si elle vérifie \begin{equation} f(A)\subseteq A \end{equation} Si \(f(A)=A\) on dit que c'est une partie invariante par \(f\). Si \(\{x\}\subset X\) est une partie invariante par \(f\), on qualifie \(x\) de point fixe de \(X\) par \(f\).

Soient \(X\) et \(Y\) deux ensembles et \(f\) et \(g\) deux applications de \(X\rg Y\). Tout \(x_0\in X\) tel que \(f(x_0)=g(x_0)\) est appelé solution de l'équation \(f(x)=g(x)\) d'inconnue \(x\).
Soient \(I\) et \(X\) deux ensembles. On appelle famille d'éléments d'un ensemble \(X\) toute application de \(I\) dans \(X\). L'ensemble \(I\) est appelé ensemble d'indexation, et l'image de l'application est l'ensemble des éléments de la famille. On note \((x_i)_{i\in I}\) une telle famille.

Rien ne distingue une famille d'une application, si l'on excepte l'usage des lettres \(I\) et \(X\) pour dé­si­gner respectivement l'ensemble de départ et d'arrivée en lieu et place des usuels \(X\) et \(Y\). Il s'agit ici de formaliser l'écriture mathématique indicielle \(x_i\) pour désigner un élément d'un ensemble \(X\). For­mel­lement on définit la famille \(x:I\rg X\) et on écrit simp­le­ment \(x_i\) au lieu de \(x(i)\).

Nous n'avons pas encore étudié l'ensemble des entiers naturels, mais il est plus pertinent de ne pas différer les définitions suivantes :

Soit \(X\) un ensemble. On appelle suite d'éléments de \(X\) toute famille dont l'en­semb­le d'indexation est l'ensemble des entiers naturels \(\N\). On appelle système d'éléments de \(X\) toute famille dont l'en­semb­le d'indexation est un ensemble fini. On appelle séquence ou suite finie d'éléments de \(X\), tout système dont l'en­semb­le d'indexation est \(\{i\in\N\mid 1\leq i\leq n\}\).

Certains auteurs donnent des définitions différentes des suites. L'existence de plusieurs définitions pour un même objet peut sembler déroutant mais ne pose aucun problème tant que l'on rappelle le sens que l'on donne à cet objet dans un discours mathématique. Ces rappels préalables sont in­dis­pen­sa­bles si la définition utilisée n'est pas celle qui est communément admise.

Ce qui importe dans ces trois notions est l'ordre dans lequel les éléments de ces trois types de familles sont rangés. C'est explicite pour la suite ou la séquence et implicite pour le système puisque si son ensemble d'indexation est fini, cela signifie qu'il est en bijection avec \(\{i\in\N\mid 1\leq i\leq n\}\), ses éléments peuvent donc être ordonné via cette bijection.

Nous avons vu au chapitre précédent comment était construit le produit cartésien de deux ensembles \(X\) et \(Y\) et plus généralement de plusieurs ensembles. Cette construction se généralise.

Soit \((X_i)_{i\in I}\) une famille d'ensembles. On appelle ensemble produit de la famille \((X_i)_{i\in I}\), l'ensemble défini par \begin{equation} \prod_{i\in I}X_i:=\left\{(x_i)_{i\in I}\mid \forall i\in I\ \ x_i\in X_i\right\}. \end{equation}

Soit \((X_i)_{i\in I}\) une famille d'ensembles, \(X\) l'ensemble produit et soit \(i\in I\), la fonction \(p_i:X\rg X_i\) est ap­pe­lée i-ème projection, elle est définie par \begin{equation} p_i(x):=x_i\ \ \text{où}\ \ x:=(x_j)_{j\in I}. \end{equation}

On suppose toujours qu'une correspondance est fournie sous la forme d'un fichier contenant son graphe. Écrivez une fonction Python ImageDirecte qui renvoie l'image directe d'une partie. Écrivez une fonction Python ImageReciproque qui renvoie l'image réciproque d'une partie donnée en paramètre.

Opérations sur les ensembles

Réunion, intersection. Soit \((X_i)_{i\in I}\) une famille d'ensembles. On montre que les deux ensembles suivant existent :

\begin{align} \bigcup_{i\in I}X_i:=&\{x\mid\exists i\in I, x\in X_i\}\\ \bigcap_{i\in I}X_i:=&\{x\mid\forall i\in I, x\in X_i\}\\ \end{align}

Il s'agit respectivement de la réunion de la famille \((X_i)_{i\in I}\) et de l'intersection de la famille \((X_i)_{i\in I}\).

Réindexation. Si l'on se donne une application surjective \(\varphi:J\rg I\), on peut faire une réindexation de la famille \((X_i)_{i\in I},\) i.e.

\begin{align} \bigcup_{i\in I}X_i &= \bigcup_{j\in J}X_{\varphi(j)},\\ \bigcap_{i\in I}X_i &= \bigcap_{j\in J}X_{\varphi(j)}. \end{align}

Autre opérations. Soient \((X_i)_{i\in I}\) et \((Y_j)_{j\in J}\) deux familles d'ensembles. On a

\begin{align} \left(\bigcup_{i\in I}X_i\right)\cap\left(\bigcup_{j\in J}Y_j\right) &=\bigcup_{(i,j)\in I\times J}\left(X_i\cap Y_is\right),\\ \left(\bigcap_{i\in I}X_i\right)\cup\left(\bigcap_{j\in J}Y_j\right) &=\bigcap_{(i,j)\in I\times J}\left(X_i\cup Y_is\right).\\ \end{align}

Soient \((X_i)_{i\in I}\) et \((Y_j)_{j\in I}\) deux familles d'ensembles de même ensemble d'indexation \(I\) telles que \(\forall i\in I\ \ X_i\subseteq Y_i\). Alors

\begin{align} \bigcup_{i\in I}X_i&\subseteq \bigcup_{i\in I}Y_i,\\ \bigcap_{i\in I}X_i&\subseteq \bigcap_{i\in I}Y_i. \end{align}

Soient \((X_i)_{i\in I}\) une famille de parties d'un ensemble \(X\). Alors

\begin{align} X\setminus\bigcup_{i\in I}X_i&= \bigcap_{i\in I}(X\setminus X_i),\\ X\setminus\bigcap_{i\in I}X_i&= \bigcup_{i\in I}(X\setminus X_i). \end{align}

Image et image inverse. Soit \(f:X\rg Y\) une application, \((X_i)_{i\in I}\) une famille de parties de l'ensemble \(X\) et \((Y_i)_{i\in I}\) une famille de parties de l'ensemble \(Y\). On a

\begin{align} f\left(\bigcup_{i\in I}X_i\right)&= \bigcup_{i\in I}f(X_i),\\ \label{eq:careful}f\left(\bigcap_{i\in I}X_i\right)&\subseteq \bigcap_{i\in I}f(X_i),\\ f^{-1}\left(\bigcup_{i\in I}X_i\right)&=\bigcup_{i\in I}f^{-1}(X_i),\\ f^{-1}\left(\bigcap_{i\in I}X_i\right)&= \bigcap_{i\in I}f^{-1}(X_i). \end{align}

L'image inverse d'une réunion (ou d'une intersection) est donc toujours la réunion (ou l'intersection) des images inverses, alors que si l'image d'une réunion est bien la réunion des images, l'image d'une intersection n'est pas l'intersection des images, cf. \((\ref{eq:careful})\).

Dans le plan euclidien, tracez les deux demi-droites \(A\) et \(B\) définies par \begin{equation} A:=\{(x,y)\in{\R}\times {\R}\mid x\geq 0\ \ y=1\},\quad B:=\{(x,y)\in{\R}\times {\R}\mid x\leq 0\ \ y=0\}. \end{equation} Montrez que \(A\cap B=\varnothing\). Considérons l'application \(f:{\R}\times {\R}\rg {\R}\times {\R}\) définie par \(f(x,y):=(x,0)\). Calculez \(f(A)\cap f(B)\). Quelle propriété une application \(f\) devrait satisfaire pour que \((\ref{eq:careful})\) soit une égalité ?

Étudier un ensemble \(X\) en le découpant en morceaux cohérents est très utile. On peut par exemple partitionner la population mondiale selon les pays, ou les instruments de musique selon qu'ils sont à vent, à corde ou à percussion, etc. Les proprités ma­thé­ma­ti­ques de ce découpage sont très naturelles, on ne veut pas de morceau vide, deux morceaux n'ont pas d'éléments communs et la réunion des morceaux constitue l'intégralité de l'ensemble :

On appelle partition d'un ensemble \(X\) toute famille \((X_i)_{i\in I}\) de parties de \(X\) qui satisfait les trois conditions :
  1. \(\forall i\in I\quad X_i\not=\varnothing\),
  2. \(\forall (i,j)\in I\times I\quad i\not= j\Rightarrow X_i\cap X_j=\varnothing\),
  3. \(\displaystyle\bigcup_{i\in I}X_i=X\).
Les éléments qui constituent la partition sont appelés classes de la partition.

Une famille d'ensembles \((X_i)_{i\in I}\) dont la réunion contient un ensemble \(X\) s'appelle un recouvrement de \(X\). Une partition est donc un cas particulier de recouvrement.

Re­la­tions binaires sur un ensemble

Comme nous l'avions déjà annoncé dans la première section, une re­la­tion binaire sur un ensemble \(X\) est tout simplement une re­la­tion binaire qui met en re­la­tion des éléments du même ensemble \(X\). Ce modèle est si versatile et fécond, qu'il a engendré à lui seul une théorie, la théorie des graphes. Cette théorie connaît des développements permanents, elle est enseignée dans toutes les formations d'in­for­ma­ti­que et à tous niveaux. C'est l'un des modèles les plus utisés dans cette discipline scien­ti­fi­que, il est donc très important de le comprendre et le maîtriser. Son rôle universel justifie d'en donner une définition spécifique, même s'il s'agit d'un cas particulier de la définition d'une re­la­tion \(q\)-aire.

On appelle re­la­tion binaire sur un ensemble \(X\) tout prédicat \(\rel(x,y)\) à deux variables dans l'ensemble \(X.\) L'ensemble \(\{(x,y)\in X\times X\mid R(x,y)\}\) est appelé le graphe de la re­la­tion \(\rel\).

On note gé­né­ra­le­ment une re­la­tion binaire de manière infixe \(x{\rel}y\), plus en adéquation avec l'ex­pres­sion en langue naturelle : \(x\) est en re­la­tion avec \(y\). Une re­la­tion binaire n'étant qu'un cas particulier de cor­res­pon­dan­ce, on pourra également lui associer un diagramme sagittal qui ne contient cette fois que les flèches reliant les éléments entre eux, autrement dit son graphe. Le dessin de la patate pour représenter l'ensemble de référence \(X\) est généralement omis. Par exemple :

Graphe d'une re­la­tion binaire sur un ensemble \(X\).

Les re­la­tions binaires peuvent posséder des propriétés re­mar­qua­bles :

  1. Réflexivité : \(\forall x\in X\quad x{\rel}x\) ;
  2. Symétrie : \(\forall (x,y)\in X^2\quad x{\rel}y\Rightarrow y{\rel}x\) ;
  3. Transitivité : \(\forall (x,y,z)\in X³\quad(x{\rel}y\ \text{et}\ y{\rel}z)\Rightarrow x{\rel}z\).
  4. Anti-symétrie : \(\forall (x,y)\in X^2\quad(x{\rel}y\ \text{et}\ y{\rel}x)\Rightarrow y= x\) ;
  5. Anti-réflexivité : \(\forall x\in X\quad\neg x{\rel}x\) ;
  6. Anti-transitivité : \(\forall (x,y,z)\in X^3\quad(x{\rel}y\ \text{et}\ y{\rel}z)\Rightarrow\ \neg x{\rel}z\).

Il faut immédiatement noter que les propriétés 4, 5 et 6 ne sont pas les négations des propriétés 1, 2 et 3 respectivement. La négation de la réflexivité s'écrit :

\begin{equation*} \exists x\in X\ \ \neg (x{\rel}x). \end{equation*}

Autrement dit, il suffit d'un seul élément dans \(X\) qui n'est pas en re­la­tion avec lui-même pour dis­qua­li­fier la propriété de réflexivité, quand bien même tous les autres éléments de \(x\) sont en re­la­tion avec eux-même. L'anti-réflexivité est bien plus contraignante, et le préfixe anti est là pour le signifier, une re­la­tion antiréflexive impose qu'aucun élément n'est en re­la­tion avec lui-même. Une re­la­tion peut donc être non-symétrique sans être anti-symétrique.

Toute relation binaire sur un ensemble définit un graphe et ré­ci­pro­que­ment, les propriétés ci-dessus peuvent également qualifier des graphes \(G\subseteq X\times X\) définis sur un ensemble \(X\).
Écrivez le graphe de la figure 9 en extension. Cette re­la­tion satisfait-elle quelques pro­prié­tés ?
Pour chacune des propriétés 1, 2 et 3, trouvez un exemple de re­la­tion binaire sur un ensemble à deux éléments, qui satisfait :
  1. Une seule des trois propriétés,
  2. Deux des trois propriétés,
  3. Les trois propriétés.
et dessiner son graphe.

Faites de même avec une re­la­tion sur un ensemble à trois éléments. Listez toutes les re­la­tions binaires sur une ensemble à 1 élement. Quelles propriétés satisfont ces re­la­tions ?
Écrivez la négation logique de chacune des propriétés d'un graphe.

Il est courant quand on dispose d'une relation binaire \(\rel\) sur un ensemble de considérer sa fermeture transitive. L'idée est simple et naturelle, l'expression les amis de mes amis sont mes amis l'illustre parfaitement. On construit à partir d'une relation \(\rel\) sa fermeture transitive \(\overline{\rel}\) en rajoutant*(*) La construction ef­fec­ti­ve de cette nou­vel­le re­la­tion né­ces­si­te d'éla­bo­rer un al­go­ri­thme. au graphe de la relation \(\rel\) les couples \((x,y)\) nécessaires pour que cette nouvelle relation soit transitive.

On dit qu'une application \(f:X\rg Y\) est compatible avec une relation binaire \(\rel\) sur \(X\) si et seulement si \begin{equation} \label{eq:appcompatiblerel} \forall(x,y)\in X\quad x{\rel}y\Rightarrow f(x)=f(y). \end{equation}

Re­la­tions d'équivalence

La re­la­tion d'équivalence est une notion déjà parfaitement intégrée par tous et en dehors de tout contexte mathématique. Quand on parle d'un homme, d'une twingo ou d'un tournevis, on ne fait bien sûr pas référence à un(e) homme/voiture/tournevis en particulier, mais à un ensemble dont les éléments ont tous des caractéristiques communes. Le formalisme mathématique tente de saisir l'essence de ce concept en identifiant ce qui le caractérise :

Une re­la­tion binaire définie sur un ensemble \(X\) à la fois réflexive, symétrique et transitive est appelée re­la­tion d'équi­valen­ce sur \(X\).

On peut définir aisément une re­la­tion sur l'ensemble des voitures, on dira par exemple que deux voitures sont en re­la­tion s'il s'agit du même modèle. La re­la­tion est évidemment réflexive, une voiture est bien du même modèle qu'elle même. La re­la­tion est également symétrique, si la voiture \(x\) est du même modèle que la voiture \(y\), la voiture \(y\) est bien du même modèle que \(x\). Elle est aussi transitive, puisque si la voiture \(x\) est du même modèle que la voiture \(y\), qui elle même est du même modèle que la voiture \(z\), alors la voiture \(x\) est du même modèle que la voiture \(z\). Le lecteur perspicace aura deviné qu'en définissant une re­la­tion binaire à partir de caractéristiques communes entre objets, elle sera toujours une re­la­tion d'équivalence.

Si \(\rel\) est une re­la­tion d'équivalence sur un ensemble \(X\) et \(x\in X\), le sous-ensemble de \(X\) constitué par tous les éléments qui sonten re­la­tion avec \(x\) est appelé classe d'équivalence de \(x\), elle est parfois notée \(\overline{x}\) :

\begin{equation} \overline{x}:=\{y\in X\mid x{\rel}y\}. \end{equation}

Un élément quelconque d'une classe d'équivalence est appelé représentant de la classe d'équivalence. David Hilbert est un représentant de la classe des hommes, l'Interceptor de Mad Max est un re­pré­sen­tant de la classe des Ford Falcon XB. Le tournevis de MacGyver est un re­pré­sentant de la classe des tournevis.

Sur quels ensembles et quels critères (informels) définiriez-vous la re­la­tion d'équivalence qui aboutit à la classe d'équivalence des hommes ? Même question pour les tournevis.

L'ensemble des classes d'équivalences d'un ensemble \(X\) pour une re­la­tion binaire \(\rel\) est appelé en­semb­le quotient de \(X\) par \(\rel\) et noté \(X/{\rel}\) comme une division, ce qui est légitime puisque l'on a divisé l'ensemble \(X\) en classes suivant la relation \(R.\)

Soit \(\rel\) une relation d'équivalence définie sur un ensemble \(X\). L'ensemble \(X/{\rel}\) est une partition de l'ensemble \(X\). Réciproquement soit \(Y\subseteq{\mathscr P}(X)\) une partition d'un ensemble \(X\). Il existe une unique relation d'équivalence \(\rel\) sur \(X\) telle que \(X/{\rel}=Y\), elle est définie par \begin{equation} x{\rel}y\iff\exists A\in Y\ \ (x\in A)\ \text{et}\ (y\in A). \end{equation}
Démontrez ce théorème.

L'application \(\varphi:X\rg X/{\rel}\) définie par \(\varphi(x):=\overline{x}\) qui à un élément \(x\) de \(X\) associe sa classe d'équi­va­len­ce \(\overline{x}\) est évidemment surjective puisque l'ensemble d'arrivée est constitué de ses images, elle est appelée surjection canonique.

Que doit satisfaire une application \(f:X\rg Y\) pour être compatible avec une relation d'équivalence \(\rel\) (deux éléments de \(X\) en relation doivent posséder la même image) ?

Soit \(f:X\rg Y\) une application, \(\rel\) une relation d'équivalence définie sur \(X\) et \(\varphi:X\rg X/{\rel}\) la surjection canonique. L'application \(f\) est compatible avec \(\rel\) si et seulement s'il existe une ap­pli­ca­tion \({\color{#88F}g}:X/{\rel}\rg Y\) telle que \(f=g\circ\varphi\) : \begin{equation} \require{AMScd} \begin{CD} X @>{f}>> Y\\ @V{\varphi}VV {\color{#88F}\nearrow g} \\ X/{\rel} \end{CD} \end{equation} Dans ce cas \(g\) est unique, on dit qu'elle est déduite de \(f\) par passage au quotient \(X/{\rel}\).

Malgré les apparences, ça n'a rien de bien compliqué. On a fait des paquets de tous les individus qui ont la même image par \(f\), et \(g\) n'est rien d'autre que \(f\) définie sur ces paquets.

Dans la section consacrée aux fonctions et aux applications, nous avons étudié comment transformer une fonction \(f:X\rg Y\) quelconque en application, il suffit de remplacer l'ensemble de départ par le domaine de définition \({\mathscr D}(f)\) de la fonction, puis comment transformer cette application en surjection, il suffit de remplacer l'ensemble d'arrivée par l'image \(f(X)\) de \(f\). Mais comment transformer cette dernière application en injection afin d'obtenir une bijection ?

L'étude que nous venons de mener nous donne la solution, il suffit de regrouper tous les éléments qui ont la même image par \(f\), autrement dit de remplacer les éléments de l'ensemble de départ par leur classe d'équivalence pour la relation d'équivalence \({\color{#88F}x{\rel}y}\iff f(x)=f(y)\) (par construction \(f\) est com­pa­tib­le avec \(\rel\)). Le diagramme sagittal ci-dessous explicite cette construction. Les éléments \(h\) et \(i\) sont écartés de l'ensemble de départ \(X\) pour faire de \(f\) une fonction et \(3\) et \(6\) sont écartés de l'ensemble d'arrivée \(Y\) pour faire de \(f\) une surjection. On obtient les \(3\) classes d'équivalence \(\color{#88F}\{b,g,e\}\), \(\color{#88F}\{c\}\) et \(\color{#88F}\{a,d\}.\)

Décomposition canonique d'une application \(f:X\rg Y.\) Les éléments \(y\not\in f(X)\) sont grisés.

L'application bijective ainsi construite est notée \({\color{#FF0}\overline{f}}\) et appelée décomposition canonique de \(f\). Les ap­pli­ca­tions qui relient les quatre ensembles \(X\), \(Y\), \(\color{#88F}{X/\rel}\) et \(f(X)\) sont souvent représentées dans un dia­gram­me appelé diagramme commutatif :

\begin{equation} \require{AMScd} \begin{CD} X @>{f}>> Y\\ @V{\varphi}VV @AAjA \\ {\color{#88F}X/{\rel}} @>>{\color{#FF0}\overline{f}}> f(X) \end{CD} \end{equation}
Diagramme commutatif de la décomposition ca­no­ni­que d'une application \(f:X\rg Y\).

Dans un diagramme commutatif, plusieurs chemins peuvent relier deux ensembles et les différentes compositions d'applications suivant ces chemins différents sont égales. Ici deux chemins relient \(X\) à \(Y\), le premier est constitué d'une seule flèche, celle étiquetée \(f\), et l'autre est constitué de trois flèches étiquetées \(\varphi\), \(\color{#FF0}\overline{f}\) et \(j\) l'injection canonique. On a donc \(f=j\circ{\color{#FF0}\overline{f}}\circ \varphi.\)

Écrivez un script Python qui réalise la décomposition canonique d'une application \(f:X\rg Y\). Les fonctions sont encore une fois encodées par leurs graphes codé dans un fichier texte. Pour cela, écrivez une fonction DC(f) qui renvoie la liste des couples \((A,y)\) formés par les classes d'équivalence \(A\) suivant \(\rel\) et de l'image commune \(y\) des représentants de la classe \(A\).

Relations d'ordre

Trier des objets est une opération très courante, même pour un être humain, mais de toutes les opérations réalisées par les ordinateurs, c'est celle qui occupe de loin la plus grande part du temps cpu mondial. Trier des objets n'est possible que si l'on a dispose d'un critère de comparaison entre eux.

Une re­la­tion binaire définie sur un ensemble \(X\) à la fois réflexive, an­ti­sy­mé­tri­que et transitive est appelée re­la­tion d'ordre sur \(X\).

On note souvent \(\preceq\) ou \(\preccurlyeq\) une relation d'ordre sur un ensemble \(X\) et le couple \((X,\preceq)\) est appelé un ens­em­ble ordonné. Si \(\preceq\) est une re­la­tion d'ordre sur un ensemble \(X\), on dit que deux éléments \(x\) et \(y\) sont comparables si et seulement si \(x\preceq y\) ou \(y\preceq x\). Si tous les éléments de \(X\) sont deux-à-deux com­pa­ra­bles, la relation est dite d'ordre total sinon d'ordre partiel. La re­la­tion binaire \(\prec\) définie sur \(X\) par \(x\prec y\) si et seulement si \(x\preceq y\) et \(x\not=y\) est appelée ordre strict associé à \(\preceq\). Attention ! l'ordre strict n'est pas une re­la­tion d'ordre.*(*) La terminologie est ici particulièrement ma­la­droi­te.

Certaines relations d'ordre sont tellement utilisées qu'elles bénéficient d'un symbole spécifique. C'est le cas de l'or­dre naturel défini sur l'ensemble \({\N}\) des entiers naturels qui est noté \(\leq\) ou \(\leqslant\). Il s'agit d'une relation d'ordre total. C'est précisément par analogie avec l'ordre naturel que le symbole générique \(\preceq \) a été choisi pour représenter une relation d'ordre quelconque. On dira d'ailleurs de deux éléments \(x\) et \(y\) tels que \(x\preceq y\) que \(x\) est plus petit que \(y\). Il faut néanmoins garder à l'esprit que cette analogie ne concerne que la terminologie, on peut parfaitement définir d'autres re­la­tions binaires \(\preceq\) sur l'ensemble des entiers naturels telles \(x\preceq y\) alors que \(x > y\) pour l'ordre strict associé à l'ordre naturel, (cf. par exemple la relation de divisibilité dans cet exercice).

On démontre aisément que l'inclusion \(\subseteq\) définie sur l'ensemble \({\mathscr P}(X)\) des parties d'un ensemble \(X\) est une re­la­tion d'ordre. L'ordre strict associé est noté \(\subset\). La terminologie héritée de l'ordre naturel ne prête pas à confusion ici puisqu'il est d'usage de dire que l'ensemble \(A\) est plus petit que l'en­sem­ble \(B\) si \(A\subseteq B\).

Démontrez que la relation binaire d'inclusion \(\subseteq\) définie sur l'ensemble \({\mathscr P}(X)\) des parties d'un ensemble \(X\) est une re­la­tion d'ordre.
Nous utilisons le symbole \(\subseteq\) pour représenter la relation d'inclusion entre en­sem­bles alors que de nombreux auteurs utilisent encore le symbole \(\subset\). Il s'agit de garder une cohérence entre les notations des différentes relations d'ordre. La propriété de réflexivité d'une relation d'ordre invite à suggérer l'égalité dans la graphie du symbole et à l'enlever pour l'ordre strict associé. C'est le choix qui a été fait pour la relation d'ordre naturel avec les symboles \(\leq\) (ou \(\leqslant\)) pour l'ordre et \(<\) pour l'ordre strict. Si l'inclusion est représentée par le symbole \(\subset\), comment représenter l'inclusion stricte ? Des solutions ont été fournies par l'in­tro­duc­tion d'une multitude de notations plus ou moins ésotériques  : \(\subsetneq\) ou encore \(\subsetneqq\) voire \(\varsubsetneqq\), ce que nous souhaitons éviter.

La relation d'inclusion définie sur des ensembles est une relation d'ordre partiel. Considérons par exemple l'ensemble \(X:=\{a,b,c\}\). L'ensemble de ses parties est

\begin{equation} \label{parties3} {\mathscr P}(X)=\big\{\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},X\big\}. \end{equation}

On ne peut pas comparer les parties \(\{a,b\}\) et \(\{c\}\) par exemple. Quand on dispose d'une relation d'ordre sur un ensemble fini comme ici, on représente le graphe de la relation à l'aide d'un dia­gram­me appelé diagramme de Hasse#(#) Helmut Hasse est un mathématicien allemand. de la relation :

Diagramme de Hasse de la relation \(\subseteq\) sur l'en­semb­le .

Le diagramme de Hasse d'une relation d'ordre est construit de bas en haut. Si l'on a \(x\preceq y\), on dessine un arc reliant le sommet \(x\) vers le sommet \(y\) qui est placé au dessus de \(x\). On ne représente aucune des relations que l'on peut déduire par transitivité. Dans l'exemple ci-dessus, l'ensemble vide \(\varnothing\) est inclus dans toutes les parties de \(X\), mais on ne trace que les trois arcs le reliant aux trois singletons, puisque les autres arcs peuvent être déduits par transitivité. Ce diagramme permet dans une certaine mesure de visualiser la relation étudiée et mettre en évidence quelques éléments re­mar­qua­bles que nous allons étudier dans la suite.

Cette représentation n'a d'intérêt que pour une relation d'ordre partielle. En effet si la relation d'or­dre est totale, le diagramme sera constitué de tronçons verticaux reliant les différents éléments de l'ensemble \(X\). Par exemple pour l'ensemble \(X:=\{0,1,2,3\}\) muni de l'ordre naturel :

Diagramme de Hasse de la relation \(\leq\) sur l'en­semb­le \(\{0,1,2,3\}\).

Quand on dispose d'une relation d'ordre \(\preceq\) sur un ensemble \(X\), certains éléments de l'ensemble peu­vent posséder des propriétés remarquables.

Soit \((X,\preceq)\) un ensemble ordonné. S'il existe un élément \(a\in X\) tel que \begin{equation} \forall x\in X\ \ \ a\preceq x\quad (\text{resp.}\ \forall x\in X\ \ \ x\preceq a), \end{equation} alors cet élément est unique. On l'appelle le plus petit élément (resp. le plus grand élément) de \(X\) et on le note \(\text{min}\ X\) (resp. \(\text{max}\ X\)).

Dans l'exemple de la figure 10, le plus petit élément et le plus grand élément de \({\mathscr P}(X)\) pour l'inc­lu­sion existent, il s'agit respectivement de \(\text{min}\ {\mathscr P}(X)=\varnothing\) et \(\text{max}\ {\mathscr P}(X)=X\). L'ensemble des en­tiers naturels \({\N}\) admet un plus petit élément pour l'ordre naturel, il s'agit de \(0\). En revanche \({\N}\) n'admet pas de plus grand élément par essence, c'est l'une des trois propriétés qui le caractérisent comme nous le verrons au chapitre suivant.

Si une relation d'ordre est partielle, tous les éléments ne sont donc pas comparables, on peut néan­moins se demander s'il existe un élément qui soit plus petit (ou plus grand) que tous ceux avec qui on peut le comparer ?

Soit \((X,\preceq)\) un ensemble ordonné. S'il existe un élément \(a\in X\) tel que \begin{equation} \forall x\in X\ \ \ x\preceq a\Rightarrow x=a\quad (\text{resp.}\ \forall x\in X\ \ \ a\preceq x\Rightarrow x=a) \end{equation} on dit que \(a\) est un élément minimal (resp. un élément maximal) de \(X\) pour la relation \(\preceq\).

Si l'on reprend la relation d'inclusion de la figure 10 mais que l'on restreint la relation à l'en­sem­ble *(*) Cliquez pour mo­di­fier le diagramme de la figure 10., les éléments minimaux sont les trois singletons \(\color{#88F}\{a\}\), \(\color{#88F}\{b\}\) et \(\color{#88F}\{c\}\). L'en­sem­ble des élé­ments maximaux est réduit à \(X\) qui est aussi le plus grand élément.

Il existe des moyens conventionnels de définir de nouvelles relations d'ordre à partir d'une ou plu­sieurs relations d'ordre prédéfinies. Quand on se donne une relation d'ordre \(\preceq\) sur un ensemble \(X\), la relation d'ordre notée \(\succeq\) définie par \(x\succeq y\iff y\preceq x\) est appelée l'ordre opposé de l'ordre \(\preceq\). Quand on restreint une relation d'ordre définie sur un ensemble \(X\) à une partie \(Y\subseteq X\), la relation ainsi crée s'appelle l'ordre induit par l'ordre \(\preceq\) sur \(Y\). Si l'on se donne une famille \((X_i,\preceq_i)_{i\in I}\) d'ensembles ordonnés, la relation \(\preceq\) définie sur l'ensemble produit \(X:=\prod_{i\in I}X_i\) par

\begin{equation} (x_i)_{i\in I}\preceq (y_i)_{j\in I}\iff \forall i\in I\ \ x_i\preceq_i y_i. \end{equation}

est une relation d'ordre appelée l'ordre produit des relations \(\preceq_i\). Les relations d'ordre \(\preceq_i\) peuvent être totales sans que l'ordre produit \(\preceq\) le soit. Considérons par exemple l'ordre produit sur l'ensemble des couples d'entiers naturels munis chacun de l'ordre naturel : \[(x,y)\preceq (x',y')\iff (x\leq x')\wedge (y\leq y').\] Les couples \((1,2)\) et \((2,1)\) ne sont pas comparables. Pour obtenir une relation d'ordre total sur ce produit cartésien il faut fournir un peu plus d'efforts.

Limitons nous au cas fini où l'ensemble d'indexation est \(I:=[1,n]\) avec \(n\) un entier naturel non-nul. On définit une relation binaire \(\preceq\) entre deux \(n\)-uplets \((x_i)_{i\in I}\) et \((y_i)_{i\in I}\) par \((x_i)_{i\in I}\preceq (y_i)_{i\in I}\) si et seulement s'il existe un rang \(k\in [1,n-1]\) tel que leurs \(i\)-èmes projections coïncident pour tout \(i\in[1,k-1]\) et que \(x_k\prec_k y_k\) ou que leurs \(i\)-èmes projections sont toutes égales sauf pour \(i=n\) où \(x_n\preceq_n y_n\). Il s'agit d'une relation d'ordre total appelée ordre lexicographique.

Malgré une définition qui semble alambiquée, c'est une relation bien connue du lecteur. Si les en­sem­bles \(X_i\) désignent tous le même alphabet latin muni de l'ordre alphabétique, il s'agit de l'ordre du dictionnaire. C'est également l'ordre qui est utilisé pour ranger les nombres réels quand ils sont re­pré­sen­tés sous forme décimale.

On définit la relation de divisibilité \(\mid\) sur l'ensemble des entiers naturels \({\N}\) par \[a\mid b\iff \exists c\in {\N}\ \ ac=b.\] Démontrez qu'il s'agit d'une relation d'ordre partiel. Vérifiez que 0 est le plus grand élément pour cette relation. Existe-t-il un plus petit élément ? Si l'on restreint cette relation à l'ensemble \({\N}\setminus\{0,1\}\), existe-t-il toujours un plus petit élément ? Un plus grand élément ? Quels sont alors les éléments minimaux s'il en existe ? Les éléments maximaux s'il en existe ?

Tracez le diagramme de Hasse de la relation de divisibilité restreinte à l'ensemble \(\{1,2,3,\ldots,20\}\).
Écrivez sous forme logique avec quantificateurs la définition de l'ordre lexicographique entre \(n\)-uplets \((x_i)_{i\in I}\) et \((y_i)_{i\in I}\). Démontrez qu'il s'agit bien d'une relation d'ordre et que si les \(n\) relations d'ordre \(\preceq_i\) sont totales alors l'ordre lexicographique est une relation d'ordre total.
Écrivez une fonction en Python Comparer(x,y) qui renvoie \(1\) si \(x\prec y\), \(0\) si \(x=y\) et \(-1\) si \(x\succ y\) pour l'ordre lexicographique sur l'alphabet latin. Écrivez un programme qui saisit deux chaînes de caractères et les compare.

Pour réaliser des tris comparatifs, il est évidemment implicite que la relation d'ordre utilisée pour comparer les objets soit totale.

Soit \((X,\preceq)\) un ensemble ordonné et \(A\subseteq X\). S'il existe un élément \(m\in X\) tel que

\begin{equation} \forall x\in A\ \ a\preceq x\quad(\text{resp.}\ x\preceq a) \end{equation}

on dit que \(a\) est un minorant (resp. majorant) de \(A\) et que \(A\) est une partie minorée (resp. majorée). Une partie \(A\) à la fois minorée et majorée, est appelée partie bornée. Si l'ensemble des minorants d'une partie \(A\) admet un plus grand élément, on l'appelle la borne inférieure de \(A\), notée \(\text{inf}\;A\). Si l'ensemble des majorants d'une partie \(A\) admet un plus petit élément, on l'appelle la borne supérieure de \(A\), notée \(\text{sup}\;A\). La borne inférieure de \(A\) appartient à \(A\) si et seu­le­ment si \(A\) admet un plus petit élément et dans ce cas \(\text{inf}\;A = \text{min}\;A\). De même, la borne supérieure de \(A\) appartient à \(A\) si et seu­le­ment si \(A\) admet un plus grand élément et dans ce cas \(\text{sup}\;A = \text{max}\;A\).

Soit \(f:X\rg Y\) une application à valeurs dans un ensemble ordonné \((Y,\preceq)\) et \(A\subseteq X\). On parlera du minimum et du maximum de \(f\) en lieu et place de \(\text{min}\ f(A)\) et \(\text{max}\ f(A)\), s'ils existent. De même on parlera de la borne inférieure et de la borne supérieure de \(f\) pour \(\text{inf}\ f(A)\) et \(\text{sup}\ f(A)\), s'ils existent. On les note respectivement

\begin{equation} \underset{x\in A}{\text{min}}\ f(x),\quad\underset{x\in A}{\text{max}}\ f(x),\quad \underset{x\in\ A}{\text{inf}}\ f(x),\quad\underset{x\in\ A}{\text{sup}}\ f(x). \end{equation}

Soient \(a\) et \(b\) deux éléments d'un ensemble totalement ordonné \((X,\preceq)\) tels que \(a\preceq b\). On définit les intervalles suivants :

\begin{align*} [a,b]&:=\{x\in X\mid a\preceq x\ \text{et}\ x\preceq b\},\\ ]a,b]&:=\{x\in X\mid a\prec x\ \text{et}\ x\preceq b\},\\ [a,b[&:=\{x\in X\mid a\preceq x\ \text{et}\ x\prec b\},\\ ]a,b[&:=\{x\in X\mid a\prec x\ \text{et}\ x\prec b\}.\\ \end{align*}

Ces intervalles sont dits respectivement fermé, semi-ouvert à gauche, semi-ouvert à droite et ouvert. On définit également les demi-droites :

\begin{align*} [a,\rg[&:=\{x\in X\mid a\preceq x\},\\ ]a,\rg[&:=\{x\in X\mid a\prec x\},\\ ]\leftarrow,b]&:=\{x\in X\mid x\prec b\},\\ ]\leftarrow,b[&:=\{x\in X\mid x\prec b\}. \end{align*}

Certains auteurs utilisent les symboles doubles crochets \([\![\) et \(]\!]\) au lieu des symboles \([\) et \(]\) quand les intervalles sont définis sur l'ensemble des entiers naturels muni de l'ordre naturel.

Démontrez que pour tout couple \((x,y)\in I\times I\) où \(I\) est un intervalle ou une demi-droite, tout élément compris entre \(x\) et \(y\) appartient à l'intervalle \(I\).
Soient \((X,\preceq_X)\) et \((Y,\preceq_Y)\) deux ensembles ordonnés. Une application \(f:X\rg Y\) est appelée application croissante si et seulement si elle vérifie \begin{equation} \forall (x,x')\in X\times X\quad x\preceq_X x'\Rightarrow f(x)\preceq_Y f(x'). \end{equation} C'est une application décroissante si et seulement si \begin{equation} \forall (x,x')\in X\times X\quad x\preceq_X x'\Rightarrow f(x)\succeq_Y f(x'). \end{equation}

Attention, la négation de la croissance n'est pas la décroissance ! En effet une application peut très bien croître par moment et décroître par d'autres. Si l'on remplace dans la définition les relations d'ordre \(\preceq_X\) et \(\preceq_Y\) par leurs ordres stricts \(\prec_X\) et \(\prec_Y\) on parle d'application strictement croissante et strictement décroissante. Une application qui est croissante ou décroissante (resp. strictement croissante ou décroissante) est dite application monotone (resp. application strictement monotone).

Démontrez que toute application monotone et injective est strictement monotone. Démontrez que la composition de deux applications monotone est monotone.

Re­la­tions de précédence

Dans les systèmes multiprocesseurs multiprogrammés, on modélise le fonctionnement des processus par un ensemble \(\mathscr T\) de tâches à réaliser. Ces tâches sont re­pré­sen­tées par des couples \(T=(d,f)\) dont la première projection \(d\) est l'instant où la tâche \(T\) débute son exécution et la seconde projection \(f\) est l'instant où elle finit son exécution. Certaines tâches ne peuvent débuter leur exécution qu'une fois que d'autres tâches ont fini la leur. Ces différentes contraintes temporelles son modélisées par une relation binaire \(\propto\) définie sur l'ensemble \(\mathscr T\) des tâches à réaliser. Si \(T\) et \(T'\) sont deux tâches, on interprète \(T\propto T'\) par la tâche \(T\) termine son exécution avant que la tâche \(T'=(d',f')\) ne débute la sienne, i.e.

\[d'\geq f.\]

On dit alors que la tâche \(T\) précède la tâche \(T'\) ou que la tâche \(T'\) succède la tâche \(T\) et la relation \(\propto\) est appellée relation de précédence. Si deux tâches \(T\) et \(T'\) sont telles que l'exécution de l'une ne nécessite pas l'exécution de l'autre au préalable, i.e. \(\neg (T\propto T')\) et \(\neg(T'\propto T)\), elles sont dites parallèles et on écrit \(T\;\Vert\;T'.\) La relation \(\propto\) est antiréflexive — une tâche \(T\) ne peut pas terminer son exécution avant qu'elle n'ait com­men­cé — elle est antisymétrique et bien sûr transitive.

Le graphe d'une relation de précédence est représenté par un diagramme qui omet tous les arcs que l'on peut déduire par transitivité. Deux questions classiques sont étudiées dans les cours de systèmes d'exploitation des formations en informatique :

  1. Trouver un ordonnancement séquentiel de l'ensemble des tâches compatible avec la relation de précédence ;
  2. Trouver un ordonnancement parallèle de l'ensemble des tâches compatible avec la relation de précédence.

Le premier cas correspond à la situation où les différentes tâches sont exécutées par un unique pro­ces­seur, le deuxième cas si le système alloue plusieurs processeurs pour exécuter des tâches en pa­ral­lè­le. Considérons par exemple la relation de précédence définie sur l'ensemble \({\mathscr T}:=\{T_1,T_2,\ldots,T_9\}\) par la fermeture transitive \(\overline{G}\) du graphe

\[ G:=\left\{(T_7,T_4),\ (T_4,T_1),\ (T_1,T_2),\ (T_2,T_3),\ (T_4,T_5),\ (T_5,T_2),\ (T_5,T_6),\ (T_8,T_5),\ (T_8,T_9),\ (T_9,T_6) \right\}. \]

Son diagramme de précédence est représenté ci-dessous. Seuls les numéros des tâches sont indiqués :

Diagramme de précédence de la relation \(\propto\) sur un en­semb­le de tâches.

Pour organiser un séquencement de ces \(9\) tâches, que ce soit de manière séquentielle ou parallèle, il faut bien sûr commencer par des tâches \(T\) qui n'ont aucun arc incident vers le sommet correspondant dans le diagramme, c'est-à-dire telles qu'il n'existe aucune tâche \(T'\) telle que \(T'\propto T\). Il n'y a que les tâches \(\color{#88F}T_7\) et \(\color{#88F}T_8\) qui ne sont précédées par aucune tâche.

Un ordonnancement séquentiel possible (il n'y pas nécessairement unicité) comme solution du pre­mier problème est :

\begin{equation*} {\color{#88F}T_7}\rg T_4\rg {\color{#88F}T_8}\rg T_5\rg T_1\rg T_9\rg T_6\rg T_2\rg T_3. \end{equation*}

Nous verrons au chapitre consacré à la combinatoire qu'une telle solution constitue une permutation de l'ensemble \(\{1,2,\ldots,9\}\). L'ordonnancement parallèle solution du second problème est :

\begin{equation*} ({\color{#88F}T_7}\;\Vert\;{\color{#88F}T_8})\rg (T_4\;\Vert\;T_9)\rg (T_5\;\Vert\;T_1)\rg (T_2\;\Vert\;T_6)\rg T_3. \end{equation*}

Ces solutions sont faciles à trouver à la main sur une instance aussi petite que celle de cet exemple, mais dans toute leur généralité ces problèmes nécessitent d'élaborer des algorithmes pour les résoudre et on souhaite qu'ils soient efficaces.

D'autres questions sont soulevées par les relations de précédences. Il ne faut pas que dans un graphe de précédence apparaisse un circuit, c'est-à-dire une séquence \(T_{i_1},T_{i_2},\ldots,T_{i_k}\) de tâches telle que

\begin{equation} \label{circuit} \forall j\in [1,k-1]\ \ T_{i_j}\propto T_{i_{j+1}}\ \ \text{et}\ \ T_{i_k}\propto T_{i_1}. \end{equation}

Plus simplement, la condition \((\ref{circuit})\) exprime qu'il ne faut jamais être en mesure de partir d'une tâche \(T\) du graphe et d'y revenir en suivant des flèches. La raison est simple, si un tel circuit existe, alors par transitivité de la relation \(\propto\), on a \(T\propto T\) ce qui contredit l'antiréflexivité.

Comment savoir s'il existe des circuits dans un graphe ? Est-on capable de les trouver rapidement ? C'est ce genre de questions qui sont étudiées en théorie des graphes et on en saisit bien l'utilité.