Relation binaire - Définition

Composition et réciproque

Composition

Si est une relation de E dans F et de F dans G, on peut définir une relation de E dans G par :

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

Réciproque

Si est une relation de E sur F, on peut définir une relation de F sur E dite relation inverse, ou réciproque, par :

.

Exemples :

« plus petit que » et « plus grand que » sont des relations réciproques l’une de l’autre ;

« aime » et « est aimé par » sont aussi réciporques l’une de l’autre.

La représentation d'une relation réciproque se déduit simplement de celle de la correspondance de départ :

• pour la représentation sagittale, en changeant le sens des liens (vu de la gauche vers la droite sur le schéma) ;
• pour une représentation matricielle, en échangeant lignes et colonnes et en prenant la matrice symétrique par rapport à la diagonale principale.

Définition formelle

Une relation binaire R d’un ensemble E vers un ensemble F est définie par une partie G de E×F.

Si (x,y) ∈ G on dit que x est en relation avec y et on note « x R y » (notation infixe), « R(x,y) », « R x y » ... (notations préfixes).

• Dans le cas particulier où E = F on dit que R est une relation binaire définie sur E ou dans E.

On remarquera qu’il est nécessaire, pour 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 G de E×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).

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é

Relation réflexive

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

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

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 «   », d’une relation sur un ensemble E est la relation sur E dont le graphe est l’union de celui de et de la diagonale de E :

Relation irréflexive

La relation sur E est irréflexive ou antiréflexive si aucun élément de E n'est en relation avec lui-même, c’est-à-dire si :

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

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 (une face a au moins 3 côtés en 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.

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

Relation symétrique

La relation sur E est symétrique si et seulement si 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 :

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

En d'autres termes, une relation symétrique est une relation qui se confond avec sa réciproque :

L'égalité entre graphes ci-dessus peut encore s'écrire :

.

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 «   », d’une relation sur un ensemble E est la relation sur E dont le graphe est l’union de celui de et de sa réciproque (ou inverse) :

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

Relation antisymétrique

La relation sur E est antisymétrique ou faiblement antisymétrique si et seulement si lorsque deux éléments de E sont en relation mutuelle, ils sont en fait confondus, c’est-à-dire si :

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

.

Exemples :

• la relation « plus grand que (ou égal à) » ainsi que la relation « plus petit que (ou égal à) » sur les entiers naturels ou sur les réels ;
• la relation « divise » dans l’ensemble des entiers naturels.

Quand une relation est à la fois antisymétrique et irréflexive, on dit parfois qu'elle est fortement antisymétrique (on lit asymétrique dans certains ouvrages). On peut alors simplifier la définition : la relation sur E est fortement antisymétrique si et seulement si 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, autrement dit :

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

.

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 on parle 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 sur E est transitive si 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 :

Une relation est donc transitive si et seulement si son graphe contient celui de sa composée avec elle-même, c'est-à-dire si :

Exemple :

• la relation sur les entiers naturels est transitive.

On appelle clôture transitive de la relation

elle est universelle parmi les relations transitives contenant . Elle est notée «   ».

Relation totale

La relation sur E est totale si 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 :

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

Exemple : la relation 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 la relation de congruence modulo 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. 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 sur N.

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

Relation bien fondée