Relations binaires

Plan du chapitre "Raisonner"

Généralités

Définition
Soit {E} et {F} deux ensembles.
On appelle relation {\mathcal{R}} de {E} vers {F} la donnée d’une partie {R} du produit cartésien {E\times F}.
La partie {R} est appelée le graphe de la relation {\mathcal{R}}.
On dit qu’un élément {x} de {E} est en relation avec un élément {y} de {F}, pour la relation {\mathcal{R}}, si le couple {(x,y)} appartient au graphe {R}. On exprime cette situation en écrivant {x\mathcal{R} y}.
Si {E=F} (cas fréquent) on dit que {\mathcal{R}} est une relation sur {E}.

Exemples :

  • La relation d’inclusion dans l’ensemble des parties de {E}: {A\mathcal{R} B\Leftrightarrow A\subset B}.
  • La relation de divisibilité sur les entiers relatifs: {m\mathcal{R} n\Leftrightarrow m\text{\ divise\ }n}.
  • Dans {\mathbb{Z}}, et si {a} non nul, on définit la relation de congruence modulo {a} : {m\mathcal{R} n\Leftrightarrow m-n\text{\ est divisible par\ }a}.
    On note le plus souvent {m\equiv n\;(a)}.
  • Sur tout ensemble {E}, on peut définir la relation égalité : {x\mathcal{R} y\Leftrightarrow x =y}.
    Le graphe de cette relation est la diagonale {\Delta(E)=\{(x, x), x\in E\}}.
  • Soit {E} et {F} deux ensembles quelconques.
    On définit la relation universelle de {E} vers {F} par : {\forall\, (x,y) \in E\times F, x\mathcal{R} y}.
    Le graphe de cette relation est l’ensemble {E\times F} tout entier.
  • Soit {E} un ensemble fini et {\mathcal{R}} une relation sur {E}.
    On peut représenter {\mathcal{R}} en donnant la liste de tous les couples {(x,y)} de {E^2} tels que {x\mathcal{R} y}.
    Voici par exemple la description d’une relation sur {E=\{a,b,c,d,e,f\}} :
    {\begin{array}{|c|c|c|c|c|c|c|}&a&b&c&d&e&f\cr a&\star&&&&&\cr b&\star&&&&&\star\cr c&&&\star&&&\cr d&&\star&&\star&\star&\star\cr e&\star&&&&\star&\cr f&&&&\star&&\end{array}\text{\ ou encore :\ }\left\{\begin{array}{llllll}a\mathcal{R} a\cr b\mathcal{R} a,&b\mathcal{R} f\cr c\mathcal{R} c\cr d\mathcal{R} b,&d\mathcal{R} d,&d\mathcal{R} e,&d\mathcal{R} f\cr e\mathcal{R} a,&e\mathcal{R} e\cr f\mathcal{R} d\end{array}\right.}
  • Restriction d’une relation :
    Si {\mathcal{R}} est une relation binaire sur {E}, et si {F} est une partie de {E}, alors on
    peut définir la restriction {{\mathcal S}} de {\mathcal{R}} à l’ensemble {F}.
    Le graphe de {{\mathcal S}} est l’intersection de {F\times F} et du graphe de {\mathcal{R}}.
    Par exemple, Si {P} est l’ensemble des entiers naturels premiers, la restriction à {P} de la relation de divisibilité n’est autre que la relation d’égalité sur {P}.

Propriétés éventuelles des relations binaires

Définition
Soit {\mathcal{R}} une relation binaire sur l’ensemble {E}.

  • {\mathcal{R}} est dite réflexive si : {\forall\, x \in E, x\mathcal{R} x}.
  • {\mathcal{R}} est dite symétrique si : {\forall\, (x,y) \in E^2, x\mathcal{R} y \Rightarrow y\mathcal{R} x}.
  • {\mathcal{R}} est dite transitive si : {\forall\, (x,y,z)\in E^3, (x\mathcal{R} y{\;\text{et}\;}y\mathcal{R} z)\Rightarrow x\mathcal{R} z}.
  • {\mathcal{R}} est dite antisymétrique si : {\forall\, (x,y) \in E^2, (x\mathcal{R} y{\;\text{et}\;}y\mathcal{R} x)\Rightarrow x = y}.

Remarques :

  • L’antisymétrie s’écrit aussi : {\forall\, (x,y) \in E^2, (x\mathcal{R} y\;et\;x \ne y)\Rightarrow non\,(y\mathcal{R} x)}
  • Si {\mathcal{R}} est symétrique, on dira de deux éléments {x,y} de {E} qu’ils sont ou qu’ils ne sont pas en relation ({x} et {y} ayant alors des rôles identiques).
  • L’antisymétrie n’est pas le contraire de la symétrie : la relation « égalité », par exemple, possède les deux propriétés, alors que la relation donnée en exemple sur {\{a,b,c,d,e,f\}} n’est ni symétrique ({e} est en relation avec {a} mais {a} n’est pas en relation avec {e}) ni antisymétrique (les éléments {d} et {f} sont en relation l’un avec l’autre, bien qu’ils soient distincts).
  • À titre d’exercice, on pourra vérifier que si une relation est à la fois sym{é}trique, antisymétrique, et réflexive, alors c’est la relation d’égalité.

Relations d’ordre

Définition
On dit qu’une relation {\mathcal{R}} sur un ensemble {E} est une relation d’ordre si {\mathcal{R}} est à la fois réflexive, antisymétrique et transitive. On note souvent {\le} une telle relation. On dit alors que {(E,\le)} est un ensemble ordonné.

Une relation d’ordre sur {E} est donc caractérisée par :

  • {\forall\, x \in E,\;x \le x}
  • {\forall\, x, y, z \in E,\;(x \le y{\;\text{et}\;}y \le z)\Rightarrow x \le z}
  • {\forall\, x, y\in E,\;(x\le y){\;\text{et}\;}(y\le x)\Rightarrow x = y}
Définition
Soit {\mathcal{R}} une relation d’ordre sur {E}.

  • Deux éléments {x} et {y} de {E} sont dits comparables (pour {\le}) si {x \le y} ou si {y \le x}.
  • Si deux éléments quelconques {x} et {y} sont toujours comparables, on dit que {\le} est une relation d’ordre total : l’ensemble {E} est dit totalement ordonné par {\le}.
  • Sinon (c’est-à-dire s’il existe au moins deux éléments non comparables {x} et {y}) on dit que {\le} est une relation d’ordre partiel (l’ensemble {E} est dit partiellement ordonné par {\le}).

Exemple et remarques

  • Sur les ensembles {\mathbb{N}}, {\mathbb{Z}}, {\mathbb{Q}}, {\mathbb{R}}, on dispose d’une relation d’ordre total, notée {\le}.
    Si {m} et {n} sont deux entiers relatifs, avec {m\le n}, on note souvent {[[ m, n]]=\{p\in\mathbb{Z},m\le p\le n\}}.
  • Relation d’ordre inverse
    Si {\le} est une relation d’ordre sur {E}, on définit encore une relation d’ordre sur {E}, notée {\ge}, en posant: {\forall\, (x,y) \in E^2, x \ge y \Leftrightarrow y \le x}.
  • Si on pose: {x \lt y\Leftrightarrow (x\le y){\;\text{et}\;}x\ne y}, on définit une nouvelle relation (appelée souvent ordre strict) qui en fait n’est pas une relation d’ordre (elle n’est pas réflexive).
  • Soit {(E,\le)} un ensemble ordonné. La négation de la proposition {x\le y} est: « ({x} et {y} ne sont pas comparables) ou {(y\lt x)} ». Bien sûr, si {E} est totalement ordonné, la négation de {x\le y} est {y\lt x}.
  • On définit une relation d’ordre sur {\mathcal{P}(E)} en posant : {A \le B\Leftrightarrow A\subset B}.
    Il s’agit d’un ordre partiel, sauf si {E} est vide ou se réduit à un élément.
    Par exemple, si {a} et {b} sont distincts dans {E}, {\{a\}} et {\{b\}} ne sont pas comparables.
  • Sur {\mathbb{R}^2}, on peut poser : {(x, y) \le (x', y')\Leftrightarrow (x\le x'){\;\text{et}\;}(y\le y')}.
    C’est un ordre partiel : les couples {(1,2)} et {(4,0)}, par exemple, ne sont pas comparables.

Relation de divisibilité dans {\mathbb{N}}

Définition
On dit que {n} divise {m} (ou que {m} est un multiple de {n}) si : {\exists\, q\in\mathbb{N}, m=nq}.
On note alors {n\mid m}. On définit ainsi une relation d’ordre partiel sur {\mathbb{N}}.
Pour cette relation, {1} est le minimum de {\mathbb{N}}.
Démonstration
  Pour voir ce contenu, vous devez : 

Remarque: la divisibilité ne définit pas une relation d’ordre sur {\mathbb{Z}} ; en effet si {m} est un entier relatif non nul, les entiers {m} et {-m} se divisent mutuellement (le quotient vaut {-1}) bien qu’ils soient distincts: la relation n’est donc pas antisymétrique.

Ordre lexicographique sur {\mathbb{R}^{2}}

Sur l’ensemble {\mathbb{R}^2}, on peut poser : {(x,y)\le(x',y'){\;\text{si}\;}\begin{cases}x\lt x'{\;\text{ou}\;}\cr(x=x'){\;\text{et}\;}(y\le y')\end{cases}}

On définit ainsi une relation d’ordre total sur {\mathbb{R}^2}.
Cette relation (dont le modèle se généralise facilement à {\mathbb{R}^n}) est appelée ordre lexicographique, en référence à la relation d’ordre total qui permet de classer les mots du dictionnaire.

Démonstration
  Pour voir ce contenu, vous devez : 

Relations d’équivalence, classes d’équivalence

Définition
On dit qu’une relation {\mathcal{R}} sur un ensemble {E} est une relation d’équivalence si {\mathcal{R}} est à la fois réflexive, symétrique et transitive. Pour tout {x} de {E}, l’ensemble des éléments en relation avec {x} est appelé la classe d’équivalence de {x}, et notée {\mathcal{C}(x)} (ou {\dot x}, ou {\overline x}): {\mathcal{C}(x)=\{y \in E, x\mathcal{R} y\}}.

Conséquences de la définition :

  • La relation {\mathcal{R}} étant réflexive, tout élément {x} de {E} appartient à sa propre classe d’équivalence.
    En particulier, aucune classe d’équivalence n’est vide.
  • Soit {x} et {y} dans {E} : si {x\mathcal{R} y}, alors {\mathcal{C}(x) = \mathcal{C}(y)}.
    Sinon {\mathcal{C}(x)\cap \mathcal{C}(y) =\emptyset}. Deux classes d’équivalence sont donc ou bien identiques ou bien disjointes.

    Démonstration
      Pour voir ce contenu, vous devez : 
  • Une classe d’équivalence {\mathcal{C}} est entièrement déterminée par la donnée de l’un quelconque de ses éléments {x} (on dira que {x} est un représentant de {\mathcal{C}}).

Proposition
Soit {E} un ensemble.

  • Soit {\mathcal{R}} une relation d’équivalence sur {E}.
    Soit {\Omega} un sous-ensemble de {E} obtenu en choisissant dans chaque classe d’équivalence {\mathcal{C}} un représentant {x} unique: la famille {(\mathcal{C}(x))_{x\in\Omega}} est une partition de l’ensemble {E}.
    Autrement dit, les différentes classes d’équivalence pour la relation {\mathcal{R}} définissent une partition de {E}.
  • Réciproquement, soit {(E_i)_{i\in I}} une partition de {E}.
    Soit {\mathcal{R}} la relation définie sur {E} par : {\forall\, (x,y)\in E^{\,2},\;x\mathcal{R} y\Leftrightarrow \exists\, i\in I,\;\{x,y\}\subset E_i}
    Alors {\mathcal{R}} est une relation d’équivalence sur {E}, et les sous-ensembles {E_i} sont les classes d’équivalence de {E} pour {\mathcal{R}}.

Démonstration
  Pour voir ce contenu, vous devez : 

Exemples de relations d’équivalence

  • Soit {f:E\to F} une application.
    On définit une relation d’équivalence sur {E} en posant : {x\mathcal{R} y\Leftrightarrow f(x)=f (y)}.
    La classe d’équivalence de {x} est l’image réciproque par {f} du singleton {\{f(x)\}}.
  • Par exemple, si {\Omega} est un point fixé du plan, on définit une relation sur ce plan en posant {M\mathcal{R} N \Leftrightarrow d(\Omega,M)= d(\Omega,N)}: l’ensemble des classes d’équivalence est l’ensemble des cercles de centre {\Omega}.
  • La relation définie sur l’ensemble {{\mathcal D}} des droites du plan par : {D\mathcal{R} \Delta\Leftrightarrow D//\Delta}.
    Les classes d’équivalence correspondent aux différentes “directions” de droites.

Congruence modulo un réel strictement positif

Définition
Soit {a} un réel strictement positif. Les réels {x} et {y} sont dits congrus modulo {a}, et on note {x\equiv y\;(a)}, s’il existe un entier relatif {q} tel que {x-y=qa}.

Remarques

  • La relation de congruence modulo {a} est une relation d’équivalence sur {\mathbb{R}}.
  • Chaque classe a un représentant unique dans {[0,a[} ou encore dans {\Bigl[-\dfrac a2,\dfrac a2\Bigr[}.
  • Pour tout réel {\lambda}, on a: {x\equiv y\;(a)\Leftrightarrow x+\lambda \equiv y+\lambda\;(a)}
  • Pour tout réel non nul {\lambda}, on a: {x\equiv y\;(a)\Leftrightarrow \lambda x\equiv\lambda y\;(\lambda a)}
  • On a les équivalences classiques suivantes : {\cos y=\cos x\Leftrightarrow\begin{cases}y=x~(2\pi)\\\text{ou}\;y=-x~(2\pi)\end{cases}\quad\sin y=\sin y\Leftrightarrow\begin{cases}y=x~(2\pi)\\\text{ou}\;y=\pi-x~(2\pi)\end{cases}}Par exemple: {\cos x=1\Leftrightarrow x\equiv0\;(2\pi)\qquad\sin(2x)=0\Leftrightarrow x=0\;(\pi/2)}

Division euclidienne et congruence modulo un entier

Définition
Soit {(a,b)} dans {\mathbb{Z}\times\mathbb{N}^*}.
Il existe un unique couple {(q,r)} de {\mathbb{Z}\times N} tel que: {(a=bq+r)\;\text{et}\; (r\le b-1)}.
Le passage du couple {(a,b)} au couple {(q,r)} s’appelle division euclidienne de {a} par {b}.
Dans cette division, {a} est le dividende, {b} le diviseur, {q} le quotient, et {r} le reste.
Démonstration
  Pour voir ce contenu, vous devez : 

Remarque (divisibilité et division euclidienne) : Soit {a} et {b} deux entiers relatifs. La proposition « {b} divise {a} » équivaut à dire que « {a=b=0} ou le reste dans la division de {a} par {|b|} est nul ».

Définition
Soit {n} un entier naturel strictement positif. Les entiers relatifs {a} et {b} sont dits congrus modulo {n}, et on note {a\equiv b\;(n)}, s’il existe un entier relatif {q} tel que {a-b=qn}.

Remarques

  • La relation de congruence modulo l’entier {n} est une relation d’équivalence sur {\mathbb{Z}}.
  • Dire que les deux entiers {a} et {b} sont congrus module {n}, c’est dire que {a} et {b} ont le même reste dans la division euclidienne par {n}.
  • Comme il y a {n} restes possibles dans la division par {n}, il y a exactement {n} classes d’équivalence.
    Les entiers {0,1,2,\ldots,n-1} constituent une famille de représentants de chaque classe.
    L’ensemble des différentes classes d’équivalence s’écrit donc : {\{\overline 0,\overline 1,\overline 2,\ldots,\overline{n-1}\}}.
  • On a les propriétés suivantes ({a,b,c} sont dans {\mathbb{Z}}, {m,n} sont dans {\mathbb{N}^{*}})
    {\begin{cases}a\equiv b\ (n)\Leftrightarrow a+c\equiv b+c\ (n)\\a\equiv b\ (n)\;\Rightarrow\; ma\equiv mb\ (mn)\;\Rightarrow\; ma\equiv mb\ (n)\\a\equiv b\ (n)\;\Rightarrow\; a^{m}\equiv b^{m}\ (n)\end{cases}}

Page précédente : injections, surjections, bijections
Retour au début : raisonner juste et bien