Relation binaire

Un article de Wikipédia, l'encyclopédie libre.

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.

Sommaire

1 Approche expérimentale
2 Définition formelle
3 Composition et inversion
- 3.1 Composition
- 3.2 Inversion
4 Relation fonctionnelle
5 Relation sur (ou dans) un ensemble
6 Exemples
7 Nombre de relations binaires sur des ensembles finis
8 Voir aussi

[modifier] Approche expérimentale

De manière informelle, une relation entre deux ensembles est une proposition qui lie certains éléments du premier ensemble 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, on peut alors tenter de représenter la relation par un diagramme: 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 de F×G.

[modifier] Définition formelle

Une relation binaire $\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 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 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).

[modifier] Composition et inversion

[modifier] 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.

[modifier] Inversion

Si $\mathcal{R}$ est une relation de E sur F, on peut définir une relation de F sur E dite relation inverse ou réciproque, 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.

[modifier] Relation fonctionnelle

Lorsque, pour tout é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, 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 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 « Id_E ».

[modifier] Relation sur (ou dans) un ensemble

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

[modifier] Propriétés liées à la réflexivité

[modifier] Relation réflexive

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 de » est réflexive : tout nombre est son propre diviseur;
dans un ensemble de personnes, la relation « est de la même famille que » est réflexive...

La clôture 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 \,$

[modifier] 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.

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...

[modifier] Relation aréflexive

La relation $\mathcal{R}$ sur E est aréflexive ssi elle n’est ni réflexive, ni irréflexive.

L’intersection de son graphe avec la diagonale de E est donc une partie propre de cette diagonale.

Exemple :

parmi les entiers naturels, la relation « forme un produit pair avec » est aréflexive, puisque 2 est en relation avec lui-même (4 est pair) et 3 ne l’est pas (9 est impair).

Remarque : les seules relations à la fois réflexives et irréflexives sont les relations vides. En conséquence, une relation non-vide est :

soit réflexive
soit irréflexive
soit aréflexive

[modifier] Propriétés liées à la symétrie

[modifier] 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 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!).

[modifier] 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

[modifier] Relation asymétrique

La relation $\mathcal{R}$ sur E est asymétrique ou fortement antisymétrique 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 \,$ .

Exemple :

la relation « est strictement plus grand que » est une relation asymétrique dans l’ensemble des réels.
dans l’univers des ensembles, la relation « est une partie propre de » est asymétrique;
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...

Une relation est fortement antisymétrique ssi elle est faiblement antisymétrique et irréflexive (en d’autres termes, l’asymétrie est un cas particulier d’antisymétrie).

Les seules relations symétriques et fortement antisymétriques sont les relations vides.

[modifier] Relation isolante

La relation $\mathcal{R}$ sur E est isolante ssi tout élément de E ne peut être en relation qu’avec lui-même, c’est-à-dire si :

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

Une relation est donc isolante ssi son graphe est inclus dans la diagonale de E, c’est-à-dire si :

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

Une relation est isolante ssi elle est symétrique et faiblement antisymétrique.

Exemples :

les relations vides sont isolantes;
l’égalité est une relation isolante...

[modifier] Relation dissymétrique

La relation $\mathcal{R}$ sur E est dissymétrique ssi elle n’est ni symétrique, ni antisymétrique.

L’intersection de son graphe avec celui de sa réciproque est donc une partie propre de son graphe non contenue dans la diagonale de E.

Exemple :

la relation « divise » dans l’ensemble des entiers relatifs est dissymétrique.

[modifier] Propriétés liées à la transitivité

[modifier] Relation transitive

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}$ ».

[modifier] Relation circulaire

La relation $\mathcal{R}$ sur E est circulaire 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, ce troisième élément est aussi en relation avec le premier, c’est-à-dire si :

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

Une relation $\mathcal{R}$ est donc circulaire ssi le graphe de sa réciproque 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}^{-1}} \,$

[modifier] Relation antitransitive

La relation $\mathcal{R}$ sur E est antitransitive 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 n'est pas 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 \not \!\,\mathcal{R} z ) \,$

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

$\mathcal{G}_{\mathcal{R} \circ \mathcal{R}} \cap \mathcal{G}_{\mathcal{R}} = \empty \,$

[modifier] Relation anticirculaire

La relation $\mathcal{R}$ sur E est anticirculaire 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, ce troisième élément n'est pas en relation avec le premier, c'est-à-dire si :

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

Une relation $\mathcal{R}$ est donc anticirculaire ssi le graphe de sa réciproque est disjoint de celui de sa composée avec elle-même, c'est-à-dire si :

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

[modifier] Autres propriétés

[modifier] Relation connexe

La relation $\mathcal{R}$ sur E est connexe ssi pour toute paire d'éléments distincts 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 ) \vee ( x = y ) \,$

La relation est donc connexe ssi l'union de son graphe, de celui de sa réciproque et de la diagonale de E est égale au carré cartésien de E, c'est-à-dire si :

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

[modifier] Relation totale

La relation $\mathcal{R}$ sur E est totale ssi pour toute paire 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é 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.

[modifier] Relation d'équivalence

Une relation d'équivalence est une relation réflexive, transitive et symétrique.

C'est une erreur fréquente que de penser que la réflexivité est inutile : une relation transitive et symétrique semble être réflexive. En effet, pour tous x et y , si $x\mathcal{R}y$ alors $y\mathcal{R}x$ (par symétrie) et donc $x\mathcal{R}x$ (par transitivité). Mais la première assertion, $x\mathcal{R}y$ , n'est pas forcément toujours vraie ! Donc la propriété de réflexivité n'est pas une conséquence des deux autres.

Le plus parfait exemple de relation d'équivalence, celui qui motive cette définition, est l'égalité.

On appelle clôture équivalente de $\mathcal{R}$ , la relation dont le graphe est :

$\Delta_E\cup(\mathcal{G}_{\mathcal{R}}\cup \mathcal{G}_{\mathcal{R}^{-1}})^{trans}$

elle est universelle parmi les relations d’équivalences qui contiennent $\mathcal{R}$ .

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

[modifier] Relation d’ordre

Une relation d’ordre est une relation réflexive, transitive et antisymétrique. Ces relations servent à généraliser la notion de « plus grand que ».

Tous les éléments ne sont pas forcément comparables par une relation d’ordre; par exemple, dans le plan, si on utilise la relation « loin de l’origine », tous les points sur un même cercle centré sur l’origine sont incomparables. Si la relation est totale alors on dit que l’ordre est total. C’est le cas de la relation « plus grand que » sur les entiers naturels.

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

[modifier] 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)

[modifier] 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.

[modifier] Voir aussi

Portail des mathématiques – Accédez aux articles de Wikipédia concernant les mathématiques.

Récupérée de « http://fr.wikipedia.org../../../r/e/l/Relation_binaire.html »

Catégorie : Théorie des ensembles

Relation binaire

Un article de Wikipédia, l'encyclopédie libre.

Sommaire

[modifier] Approche expérimentale

[modifier] Définition formelle

[modifier] Composition et inversion

[modifier] Composition

[modifier] Inversion

[modifier] Relation fonctionnelle

[modifier] Relation sur (ou dans) un ensemble

[modifier] Propriétés liées à la réflexivité

[modifier] Relation réflexive

[modifier] Relation irréflexive

[modifier] Relation aréflexive

[modifier] Propriétés liées à la symétrie

[modifier] Relation symétrique

[modifier] Relation antisymétrique

[modifier] Relation asymétrique

[modifier] Relation isolante

[modifier] Relation dissymétrique

[modifier] Propriétés liées à la transitivité

[modifier] Relation transitive

[modifier] Relation circulaire

[modifier] Relation antitransitive

[modifier] Relation anticirculaire

[modifier] Autres propriétés

[modifier] Relation connexe

[modifier] Relation totale

[modifier] Relation d'équivalence

[modifier] Relation d’ordre

[modifier] Exemples

[modifier] Nombre de relations binaires sur des ensembles finis

[modifier] Voir aussi

Views

Navigation

Contribuer

Rechercher

Autres langues