Opérations sur les relations et applications [C1.II.2]

1. Opérations élémentaires sur les relations et applications

1.1. Restriction et co-restriction

Si $E$ et $F$ sont deux ensembles et $R$ est une relation entre $E$ et $F$, nous avons insisté sur le fait que stricto sensu la relation $R$ est la donnée des trois ensembles $E$, $F$ et $R$, soit du triplet $(E,F,R)$, et nous avons donné des exemples où la « même » description d’une relation par son graphe donnait lieu à des relations différentes, lorsque le domaine ou le co-domaine étaient différents.

Il est important de bien comprendre ceci et de ne pas le considérer comme un formalisme stérile, ou comme du pédantisme. Il est en effet souvent nécessaire de définir de nouvelles relations ou de nouvelles applications en modifiant seulement le domaine ou le co-domaine, ce qu’on appelle restriction ou co-restriction d’une relation ou d’une application.

Nous l’avons déjà pratiqué sans le dire en définissant la « restriction » d’une relation (Produits, relations et applications, exercice 2(viii)), la « co-restriction » d’une application (exemple 6(ii), ibid.) et une application à partir d’une relation fonctionnelle (exercice 3(i), ibid.).

Ici, nous donnons des définitions rigoureuses qui ne devraient poser aucun problème à l’étudiant(e) qui a suivi attentivement le cours jusqu’ici.

1.2. Restriction d’une relation ou d’une application

Définition 1
Soit $(E,F,R)$ une relation. Si $S\subseteq E$ est une partie de $E$, la restriction de $R$ à $S$ est la relation de $S$ dans $F$ décrite par le triplet $(S,F,R_{|_S})$, autrement dit dont le graphe est le sous-ensemble $R_{|S}=\{(x,y)\in R : x\in S\}$ de $S\times F$.

Autrement dit, pour une relation $R$ entre un ensemble $E$ et un ensemble $F$, la restriction de $R$ à un sous-ensemble $S$ de $E$ consiste précisément à « restreindre » la relation $R$ aux seuls couples $(x,y)$ pour lesquels $x$ est un élément de $S$.

La restriction d’une relation a donc trait au domaine de cette relation.

Etant donné qu’une application est un cas particulier de relation, nous pouvons ici appliquer directement la notion de restriction à une application. Si $f:E\to F$ est une application, la restriction de $f$ à un sous-ensemble $S$ de $E$ est tout simplement l’application notée $f_{|S}:S\to F$, et dont la description est $(S,F,R_{|S})$, si la description de $f$ est $(E,F,R)$.

La restriction d’une application est donc sa restriction comme relation.

Exemple 1
i) Si $|$ est la relation de divisibilité sur l’ensemble $\mathbb Z\times\mathbb N$, c’est-à-dire le triplet $(\mathbb Z,\mathbb N,R)$, où $R=\{(n,m)\in \mathbb Z\times\mathbb N : n|m\}$, alors la restriction de $|$ à $\mathbb N\subseteq\mathbb Z$ est la relation de divisibilité sur $\mathbb N\times\mathbb N$.
ii) Si $+:\mathbb R\times\mathbb R\to \mathbb R$ est l’addition des nombres réels, alors comme le produit $\mathbb N\times\mathbb N$ est un sous-ensemble de $\mathbb R\times\mathbb R$, on peut définir la restriction de $+$ à $\mathbb N\times\mathbb N$, comme l’application $+_{\mathbb N\times\mathbb N}:\mathbb N\times\mathbb N\to \mathbb R$, $(m,n)\mapsto m+n$. Comme opération, il s’agit bien de l’addition des entiers naturels mais attention : c’est une application différente de l’addition $+:\mathbb N\times\mathbb N\to \mathbb N$ (on utilise la même notation par abus), car les co-domaines sont différents ! On peut bien sûr, dans cet exemple, remplacer $\mathbb N$ par $\mathbb Z$ ou $\mathbb Q$ par exemple.

Remarque 1
Nous avons parlé de relations binaires sur un ensemble $E$, comme relations de $E$ dans $E$ et en toute rigueur on devrait définir la restriction à $S$ d’une telle relation comme la relation de graphe $\{(x,y)\in S\times E : (x,y)\in R\}$. Cependant, il arrive qu’on entende par « restriction » de $R$ à $S$ la relation binaire $(S,S,R’)$ sur $S$ telle que $R’=\{(x,y)\in S\times S : (x,y)\in R\}$ ! Autrement dit, on fait aussi une restriction sur le co-domaine, qui est $E$ lui-même. C’est dans ce sens où nous l’avons pris dans la section sur les relations.

Cette confusion terminologique, regrettable, est en général levée par le contexte. Lorsqu’on considère des relations binaires sur des ensembles (et donc où le domaine et le co-domaine sont identiques), il est naturel d’appliquer la restriction aux deux.

Exemple 2
Si $\leq$ est la relation binaire d’ordre large sur $\mathbb R^2$, et si $E$ est l’un des ensembles $\mathbb N,\mathbb Z$ ou $\mathbb Q$, alors on obtient par « restriction » de $\leq$ à $E$ la relation binaire d’ordre large usuelle sur $E$.

Sur la figure suivante est représentée la restriction de la fonction $x\mapsto x^2$ au réel segment $[-2,2]$.

1.3. Co-restriction d’une relation ou d’une application

Si la restriction consiste à rapporter une relation à un sous-ensemble de son domaine, la co-restriction consiste naturellement à rapporter une relation à un sous-ensemble de son co-domaine.

Définition 2
Soit $(E,F,R)$ une relation. Si $T\subseteq F$ est une partie de $F$, la co-restriction de $R$ à $T$ est la relation $(E,T,R^{|T})$ entre $E$ et $T$, dont le graphe est $R^{|T}=\{(x,y)\in R : y\in T\}$.

Autrement dit, pour une relation $R$ entre deux ensembles $E$ et $F$, la co-restriction de $R$ à un sous-ensemble $T$ de $F$ consiste précisément à « restreindre » la relation $R$ aux seuls couples $(x,y)$ pour lesquels $y$ est un élément de $T$.

La co-restriction d’une relation a donc trait au co-domaine de cette relation.

Une application étant un cas particulier de relation, nous pouvons appliquer la définition de co-restriction à une application $f:E\to F$. Mais attention : si la co-restriction de $f$ à un sous-ensemble $T$ de $F$ est bien définie comme relation, ce n’est pas toujours une application, car un élément de $E$ n’a pas toujours un correspondant par $f$ dans $T$ !

Exemple 3
i) Si $|$ est la relation de divisibilité sur l’ensemble $\mathbb N\times\mathbb Z$, c’est-à-dire le triplet $(\mathbb N,\mathbb Z,R)$ où $R=\{(n,m)\in\mathbb N\times \mathbb Z : n|m\}$, alors la co-restriction de $|$ à $\mathbb N\subseteq \mathbb Z$ est la relation de divisibilité sur $\mathbb N\times\mathbb N$.
ii) Si $+_{|\mathbb N}:\mathbb N\times\mathbb N\to \mathbb R$ est l’addition des entiers naturels, considérée comme restriction de l’addition $+:\mathbb R\times\mathbb R\to\mathbb R$ des nombres réels (voir l’exemple du paragraphe précédent), alors la co-restriction de $+_{|\mathbb N}$ à $\mathbb N\subseteq\mathbb R$ est l’addition usuelle $+_\mathbb N:\mathbb N\times\mathbb N\to\mathbb N$ des entiers naturels. Dans ce cas, il s’agit bien d’une application.
iii) Si $s:\mathbb N\to\mathbb N, n\mapsto n+1$ est l’application « successeur », que nous avons déjà rencontrée, le graphe $R$ de la co-restriction $s^{|P}$ de $s$ au sous-ensemble $P$ de $\mathbb N$ des entiers naturels pairs est l’ensemble des couples $(m,n)$ d’entiers naturels tels que $n=m+1$ et $n$ est pair. Cette co-restriction n’est donc pas une application, puisque pour aucun entier naturel $m$ pair il n’existe d’entier naturel $n$ tel que $(m,n)\in R$ : en effet, si $m$ est pair, $m+1$ est toujours impair !

Nous verrons dans la suite du cours comment il est possible de s’assurer que la co-restriction d’une application $f:E\to F$ est une application. Comme l’étudiant(e) l’aura peut-être deviné, cela revient à ce que le sous-ensemble $T$ auquel on veut appliquer la co-restriction contienne tous les éléments de $F$ de la forme $f(x)$, pour $x\in E$. Nous introduirons des définitions spécifiques pour préciser cette idée.

1.4. Exercices

Exercice 1
i) On considère l’application $f:\mathbb Z\times\mathbb N^*\to \mathbb Z\times \mathbb N$ qui associe à un couple $(n,m)\in\mathbb Z\times\mathbb N^*$ le couple $(q,r)\in \mathbb Z\times\mathbb N$ où $q$ est le quotient et $r$ le reste de la division euclidienne de $n$ par $m$ (voir l’exercice 3(iii) de Produits, applications et relations). Décrire un sous-ensemble $S$ de $\mathbb N$, le plus petit possible, tel que la co-restriction de $f$ à $\mathbb Z\times S$ est encore une application.
ii) On note $g:\mathbb N\times\mathbb N^*\to \mathbb N\times\mathbb N$ l’application définie comme l’application $f$ au (i). Comment obtenir $g$ à partir de $f$ par une ou des opérations sur $f$ ? Si on pose la même question pour $g$ que pour $f$, le sous-ensemble $S$ de $\mathbb N$ trouvé au (i) convient-il ici ?
iii) Soit $f:\mathbb R\to\mathbb R$ la valeur absolue (voir le premier chapitre), c’est-à-dire $f(x)=|x|$ pour tout $x\in \mathbb R$, avec $|x|=x$ si $x\geq 0$, $|x|=-x$ si $x\leq 0$. On considère la restriction $g=f|_{\mathbb Q}$ de $f$ à $\mathbb Q\subseteq \mathbb R$. Trouver un sous-ensemble $S$ de $\mathbb R$, différent de $\mathbb R$ et ne contenant pas $\pi$, tel que la co-restriction de $g$ à $S$ est une application.
iv) Soit $f:E\to F$ une application. Montrer que pour tout sous-ensemble $T$ de $F$, la co-restriction de $f$ à $T$ est une relation fonctionnelle.

2. Composition des applications