Relation binaire
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Une relation binaire est un concept mathématique qui systématise des notions comme " ... est supérieur ou égal à ... " en arithmétique, ou " ... est élément de l’ensemble ... " en théorie des ensembles. C’est un cas particulier de relation générale ou correspondance. On retrouve aussi ce concept en théorie des graphes (Le terme de graphe désigne en mathématiques une opération d'application. Il possède deux acceptions :).

Introduction

De manière informelle, une relation entre deux ensembles est une proposition qui lie certains éléments du premier ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un tout »,...) avec d’autres éléments du second ensemble.

Sur un ensemble F constitué de filles et un ensemble G constitué de garçons, par exemple, on pourrait définir une relation " Alice aime Bernard ", ou une autre relation " Béatrice connaît Paul "... On peut donc voir la relation comme étant des fils reliant des éléments de deux ensembles.

Dans le cas d’un ensemble fini (En mathématiques, un ensemble E est dit fini si et seulement si E est vide ou s'il existe un entier n et une bijection de E dans l'ensemble des n premiers entiers naturels.), on peut alors tenter de représenter la relation par un diagramme (Un diagramme est une représentation visuelle simplifiée et structurée des concepts, des idées, des constructions, des relations, des données statistiques, de l'anatomie etc. employé dans tous les aspects...): si F = {Lucie, Béatrice, Delphine, Alice} et si G = {Bernard, Antoine, Paul, Charles}, la relation aime peut être schématisée par le diagramme suivant :

On pourra déplorer le fait que Delphine n’aime personne, que Lucie ait un cœur généreux et que Charles puisse se sentir seul.

On peut aussi tenter de faire la liste des couples ainsi en relation. (pour plus de commodité, on ne conservera que les deux premières lettres du prénom)

Gr = {(Lu,Be) , (Lu, An) , (Lu, Pa) , (Bé, An) , (Al, Pa) , (Al, Be)}

En mathématique, un " couple " est formé de deux éléments mis entre parenthèses dans un ordre particulier. La relation est définie en première approche comme un ensemble de couples, c’est-à-dire que si deux éléments sont reliés entre eux, alors le couple est un élément de l’ensemble relation. Si l’on appelle F l’ensemble des filles, et G l’ensemble des garçons, alors l’ensemble de tous les couples possibles est appelé " produit cartésien de F par G " et est noté F×G et la relation aime est alors définie par l’ensemble F, l’ensemble G et un sous-ensemble (En mathématiques, un ensemble A est un sous-ensemble ou une partie d’un ensemble B, ou encore B est sur-ensemble de A, si tout élément du sous-ensemble A est aussi élément du sur-ensemble B. Il peut par...) de F×G.

Définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.) formelle

Une relation binaire (Une relation binaire est un concept mathématique qui systématise des notions comme « ... est supérieur ou égal à ... » en arithmétique, ou « ... est élément de l’ensemble...) \mathcal{R} d’un ensemble E vers un ensemble F est définie par une partie \mathcal{G} de E×F.

Si (x,y) \in \mathcal{G} on dit que x est en relation avec y et on le note " x\mathcal{R}y ".

  • Dans le cas particulier où E = F on dit que \mathcal{R} est une relation binaire définie sur E ou dans E.
  • Dans le cas où E = F×F, on parlera de relation ternaire interne (Une relation ternaire interne dans un ensemble associe des éléments de cet ensemble à des couples formés d’éléments de ce même ensemble.) sur F.
  • Plus généralement, si E = F n - 1, on parlera de relation n-aire sur F.

On remarquera qu’il est nécessaire, dans une relation binaire, de préciser l’ensemble E (appelé ensemble de départ), l’ensemble F (appelé ensemble d’arrivée) ET la partie \mathcal{G} de E \times F appelée le graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) de la relation.

Une relation binaire peut être considérée comme une fonction de E×F à valeur dans l’ensemble { Vrai , Faux } , et qui à un couple ( x , y ) associe Vrai si x est en relation avec y et Faux sinon (indiquant si le couple ( x , y ) est un élément du graphe de la relation ou non).

Composition et inversion

Composition

Si \mathcal{R} est une relation de E dans F et \mathcal{S} de F dans G, on peut définir une relation \mathcal{S}\circ \mathcal{R} de E dans G par :

\mathcal{G}_{\mathcal{S} \circ \mathcal{R}} = \left\{ ( x , y ) \in E \times G \, | \, \exists z \in F /\, ( x , z ) \in R \and ( z , y ) \in S \right\} \,

Notation: si \mathcal{R} est une relation sur un ensemble E et n un entier naturel, on note \mathcal{R}^n la composition de \mathcal{R} avec elle-même n fois, avec la convention que \mathcal{R}^0 dénote la relation d’égalité sur E.

Inversion

Si \mathcal{R} est une relation de E sur F, on peut définir une relation de F sur E dite relation inverse (En mathématiques, l'inverse d'un élément x d'un ensemble muni d'une loi de composition interne · notée multiplicativement, est un élément y tel que x·y...) ou réciproque (La réciproque est une relation d'implication.), par :

\mathcal{G}_{\mathcal{R}^{-1}} = \left\{ ( x , y ) \in F \times E \, | \, ( y , x ) \in \mathcal{G}_{\mathcal{R}} \right\} \,.

Exemples:

" plus petit que " et " plus grand que " sont des relations inverses l’une de l’autre.
" aime " et " est aimé par " sont aussi inverses l’une de l’autre.

Relation fonctionnelle (En mathématiques, le terme fonctionnelle se réfère à certaines fonctions. Initialement, le terme désignait les fonctions qui en prennent d'autres en argument. Aujourd'hui, le terme a été...)

Lorsque, pour tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) élément x de E, x n’est en relation qu’avec 0 ou 1 élément y de F, on dit que la relation est fonctionnelle. C’est un cas particulier de fonction. En langage formel (Dans de nombreux contextes (scientifique, légal, etc.) l'on désigne par langage formel un mode d'expression plus formalisé et plus précis (les deux n'allant pas...), la propriété précédente s’écrit :

\forall x \in E, \forall y \in F, \forall z \in F , [ ( x , y ) \in \mathcal{G}_{\mathcal{R}} \and ( x , z ) \in \mathcal{G}_{\mathcal{R}} ] \Rightarrow  ( y = z )  \,

Pour plus de précisions, voir l'article " Fonction mathématique ".

Exemple important :

La diagonale (On appelle diagonale d'un polygone tout segment reliant deux sommets non consécutifs (non reliés par un côté). Un polygone à n côtés possède diagonales.) de E est définie par :
\Delta_E = \left\{ ( x , x ) \, | \, x \in E \right\} \,.
C’est le graphe de la relation d’égalité sur E, notée " =E ", ou " = " en l’absence d’ambiguïté sur l’ensemble concerné.
Cette relation est aussi une fonction, l’identité de E, notée " IdE ".

Relation sur (ou dans) un ensemble

Si E = F, on parlera de relation sur (ou dans) E.

Propriétés liées à la réflexivité (La réflexivité est la propriété d'une relation binaire qui met en relation tout élément avec lui-même.)

Relation réflexive (En théorie des ensembles, une relation binaire peut avoir, entre autres deux propriétés, la réflexivité et l'irréflexivité.)

La relation \mathcal{R} sur E est réflexive si tout élément de E est en relation avec lui-même, c’est-à-dire si :

\forall x \in E , x \mathcal{R} x \,

Une relation est donc réflexive ssi son graphe contient la diagonale de E, c’est-à-dire si :

\Delta_E \subseteq \mathcal{G}_{\mathcal{R}} \,

En d’autres termes, l’intersection du graphe de la relation avec la diagonale de E est égale à cette diagonale.

Exemples:

  • la relation d’inclusion entre ensembles est réflexive : tout ensemble est inclus dans lui-même;
  • dans un ensemble de nombres, la relation " est un diviseur (En mathématiques, un nombre entier d est un diviseur d'un entier n lorsque la division euclidienne de n par d donne un reste égal à zéro....) de " est réflexive : tout nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) est son propre diviseur;
  • dans un ensemble de personnes, la relation " est de la même famille que " est réflexive...

La clôture (Une clôture désigne tout obstacle naturel ou fait de la main de l'homme (barrière) et suivant tout ou partie du pourtour d'un terrain afin de matérialiser ses limites ou d'empêcher des personnes ou des animaux d'y entrer ou d'en...) réflexive, notée " \mathcal{R}^{refl} \, ", d’une relation \mathcal{R} sur un ensemble E est la relation sur E dont le graphe est l’union de celui de \mathcal{R} et de la diagonale de E :

\mathcal{G}_{\mathcal{R}^{refl}} = \mathcal{G}_{\mathcal{R}} \cup \Delta_E \,

Relation irréflexive

La relation \mathcal{R} sur E est irréflexive ssi tout élément de E n’est pas en relation avec lui-même, c’est-à-dire si :

\forall x \in E , x \not \!\,\mathcal{R} x \,

Une relation est donc irréflexive ssi son graphe est disjoint de la diagonale de E, c’est-à-dire si :

\Delta_E \cap \mathcal{G}_{\mathcal{R}} = \empty \,

L’intersection du graphe de la relation avec la diagonale de E se réduit donc à l’ensemble vide (Le vide est ordinairement défini comme l'absence de matière dans une zone spatiale.).

Exemples :

  • l’inégalité stricte sur les entiers est un exemple de relation irréflexive : aucun entier n’est strictement inférieur à lui-même;
  • dans un ensemble de personnes, la relation " est enfant de " est irréflexive : personne n’est son propre enfant;
  • dans un polyèdre, la relation " a un et un seul côté commun avec " est une relation irréflexive entre ses faces : aucune face n’a qu’un seul côté commun avec elle-même...

Une relation sur un ensemble d'au moins deux éléments peut bien entendu n'être ni réflexive, ni irréflexive, il suffit qu'un élément soit en relation avec lui même et l'autre non.

Les seules relations à la fois réflexives et irréflexives sont les relations dont le graphe est vide.

Propriétés liées à la symétrie

Relation symétrique

La relation \mathcal{R} sur E est symétrique ssi lorsqu’un premier élément de E est en relation avec un second élément de E, le second élément est lui aussi en relation avec le premier, c’est-à-dire si :

\forall ( x , y ) \in E^2 , ( x \mathcal{R} y ) \Rightarrow ( y \mathcal{R} x ) \,

Une relation est donc symétrique ssi son graphe se confond avec celui de sa relation inverse, c’est-à-dire si :

\mathcal{G}_{\mathcal{R}} = \mathcal{G}_{\mathcal{R}^{-1}} \,

ou encore :

\mathcal{G}_{\mathcal{R}} \cap \mathcal{G}_{\mathcal{R}^{-1}} = \mathcal{G}_{\mathcal{R}} \,.

Exemples :

  • dans un ensemble de personnes, la relation " est de la même famille que " est symétrique;
  • dans un polyèdre, la relation " a un et un seul côté commun avec " est une relation symétrique entre ses faces : si une face a un côté commun avec une autre face, cette dernière a le même côté commun avec la première face;
  • parmi les entiers naturels, la relation " forme un produit pair avec " est symétrique, car la multiplication (La multiplication est l'une des quatre opérations de l'arithmétique élémentaire avec l'addition, la soustraction et la division .) des entiers est commutative.

La clôture symétrique, notée " \mathcal{R}^{sym} \, ", d’une relation \mathcal{R} sur un ensemble E est la relation sur E dont le graphe est l’union de celui de \mathcal{R} et de sa réciproque (ou inverse) :

\mathcal{G}_{\mathcal{R}^{sym}} = \mathcal{G}_{\mathcal{R}} \cup \mathcal{G}_{\mathcal{R}^{-1}} \,

Cette clôture symétrique est d’ailleurs universelle parmi les relations symétriques contenant \mathcal{R} (ce qui ici, sans entrer dans des considérations catégoriques, signifie que c’est la plus petite!).

Relation antisymétrique

La relation \mathcal{R} sur E est antisymétrique ou faiblement antisymétrique ssi lorsque deux éléments de E sont en relation mutuelle, ils sont en fait confondus, c’est-à-dire si :

\forall ( x , y ) \in E^2 , [ ( x \mathcal{R} y ) \wedge ( y \mathcal{R} x ) ] \Rightarrow ( x = y ) \,

Une relation est donc faiblement antisymétrique ssi l'intersection de son graphe avec celui de sa réciproque est incluse dans la diagonale de E, c'est-à-dire si :

\mathcal{G}_{\mathcal{R}} \cap \mathcal{G}_{\mathcal{R}^{-1}} \subseteq \Delta_E \,.

Exemples:

  • les relations " plus grand que " et " plus petit que " sur les entiers naturels ou sur les réels.
  • la relation " divise " dans l’ensemble des entiers naturels

Quand une relation est à la fois anti-symétrique et irréflexive, on dit parfois qu'elle est fortement antisymétrique. On peut alors simplifier la définition.

La relation \mathcal{R} sur E est fortement antisymétrique, c'est à dire antisymétrique et irréflexive, ssi lorsqu’un premier élément de E est en relation avec un second élément de E, le second élément n’est pas en relation avec le premier, c’est-à-dire si :

\forall ( x , y ) \in E^2 , ( x \mathcal{R} y ) \Rightarrow ( y \not \!\,\mathcal{R} x ) \,

Une relation est donc fortement antisymétrique ssi l’intersection de son graphe avec celui de sa réciproque est vide, c’est-à-dire si :

\mathcal{G}_{\mathcal{R}} \cap \mathcal{G}_{\mathcal{R}^{-1}} = \empty \,.

Exemples :

  • les relations d'ordre strict, comme la relation " est strictement plus grand que " sur les entiers ou les réels, ou la relation d'inclusion stricte sont fortement antisymétriques.
  • dans un ensemble de personnes, la relation " est enfant de " est asymétrique : personne n’est son propre enfant, ni a fortiori l’enfant de ses enfants...

Pour une relation dont on sait par ailleurs qu'elle est irréflexive, l'antisymétrie forte et l'antisymétrie sont équivalentes, et donc la plupart du temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) onparle simplement d'antisymétrie.

Les seules relations symétriques et fortement antisymétriques sont les relations vides. Par contre l'égalité sur n'importe quel ensemble est une relation à la fois symétrique et antisymétrique.

Une relation peut n'être ni symétrique ni antisymétrique, comme par exemple la relation de divisibilité sur les entiers relatifs.

Transitivité

La relation \mathcal{R} sur E est transitive ssi lorsqu’un premier élément de E est en relation avec un deuxième élément lui-même en relation avec un troisième, le premier élément est aussi en relation avec le troisième, c’est-à-dire si :

\forall ( x , y , z ) \in E^3 , [ ( x \mathcal{R} y ) \wedge ( y \mathcal{R} z ) ] \Rightarrow ( x \mathcal{R} z ) \,

Une relation \mathcal{R} est donc transitive ssi son graphe contient celui de sa composée avec elle-même, c'est-à-dire si :

\mathcal{G}_{\mathcal{R} \circ \mathcal{R}} \subseteq \mathcal{G}_{\mathcal{R}} \,

Exemple :

  • la relation \leq sur les entiers naturels est transitive.

On appelle clôture transitive de \mathcal{R} la relation

\bigcup_{n\geq 1}\mathcal{R}^n

elle est universelle parmi les relations transitives contenant \mathcal{R}. Elle est notée " \mathcal{R}^{trans} ".

Relation totale

La relation \mathcal{R} sur E est totale ssi pour toute paire (On dit qu'un ensemble E est une paire lorsqu'il est formé de deux éléments distincts a et b, et il s'écrit alors :) d'éléments de E, elle institue au moins un lien entre les deux éléments considérés, c'est-à-dire si :

\forall ( x , y ) \in E^2 , ( x \mathcal{R} y ) \vee ( y \mathcal{R} x ) \,

La relation est donc totale ssi l'union de son graphe avec celui de sa réciproque est égale au carré (Un carré est un polygone régulier à quatre côtés. Cela signifie que ses quatre côtés ont la même longueur et ses quatre angles la même...) cartésien de E, c'est-à-dire si :

\mathcal{G}_{\mathcal{R}} \cup \mathcal{G}_{\mathcal{R}^{-1}} = E^2 \,

Exemple : la relation \leq sur l'ensemble des réels est une relation totale.

Contre-exemple : la relation " divise " sur l'ensemble des entiers naturels n'est pas totale.

Relation d'équivalence

Une relation d'équivalence est une relation réflexive, transitive et symétrique. L'exemple le plus simple de relation d'équivalence est l'égalité. En arithmétique (L'arithmétique est une branche des mathématiques qui comprend la partie de la théorie des nombres qui utilise des méthodes de la géométrie algébrique et de la théorie des groupes....) la relation de congruence modulo ( En arithmétique modulaire, on parle de nombres congrus modulo n Le terme modulo peut aussi être associé à d'autres formes de congruence En informatique, le modulo (informatique) est une fonction qui au couple...) un entier donné est une relation d'équivalence.

Pour plus d’information voir l’article " Relation d'équivalence ".

Relation d’ordre

Une relation d’ordre est une relation réflexive, transitive et antisymétrique.

Si la relation est totale alors on dit que l’ordre est total ( Total est la qualité de ce qui est complet, sans exception. D'un point de vue comptable, un total est le résultat d'une addition, c'est-à-dire une somme. Exemple : "Le total des...). C’est le cas de la relation " plus grand que " sur les entiers naturels. Tous les éléments ne sont pas forcément comparables par une relation d’ordre ; par exemple deux entiers naturels ne sont pas forcément comparables par divisibilité. On dit alors que la divisibilité est un ordre partiel (Le mot partiel peut être employé comme :) sur N.

Plus de détails dans l’article " Relation d'ordre ".

Relation bien fondée (Soit E un ensemble non vide. On dit qu'une relation R sur E est bien fondée ou plus rarement nœthérienne (alors que l'on devrait dire en toute rigueur artinienne ce qui se dit plus rarement encore) si et seulement...)

Voir relation bien fondée.

Exemples

  • La relation d’appartenance sur E \times \mathcal{P}(E)
  • La relation d’inclusion sur \mathcal{P}(E) (relation d’ordre)
  • La relation inférieur ou supérieur sur \mathbb{R} (relations d’ordres)
  • la relation divise sur \mathbb{N} (relation d’ordre)
  • La relation d’égalité (congruencielle ou non) sur E (relation d’équivalence)

Nombre de relations binaires sur des ensembles finis

Considérons un ensemble E fini de cardinal n et un ensemble F fini de cardinal p. Nous pouvons facilement démontrer qu’il y a autant de relations binaires de E sur F que d’applications de E×F dans { 0 , 1 } , ce qui donne 2 np relations.

En particulier, si E = F , on trouve 2^{n^2} \, relations binaires sur E, dont

  • 2^{n(n - 1)} \, relations réflexives
  • 2^{n(n + 1)/2} \, relations symétriques
  • Pour le nombre de relations transitives, il n’y a toujours pas actuellement de formule " fermée "

Le nombre de relations d’équivalence est égal au nombre de partitions d’un ensemble, c’est-à-dire le nombre de Bell (Les nombres de Bell, qui portent le nom de Eric Temple Bell, se rencontrent souvent en combinatoire. Ces nombres forment une suite d'entiers qui commence ainsi:).

Page générée en 0.082 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique