Relation

Une relation entre deux ensembles et est une loi qui associe à chaque élément de zéro, un ou plusieurs éléments de . Dans ce sens, c’est une généralisation du concept de Fonction.

Définition et notation

Formellement, une relation entre deux ensembles et est un sous-ensemble du produit cartésien . Pour des ensembles finis, une relation peut être représentée à l’aide de diagrammes de Venn en reliant les éléments en relation, comme dans la figure.

Si est une relation et si et sont deux éléments, on écrit si et sont en relation, c’est à dire si .

Lorsque pour tout il existe au plus un tel que , la relation correspond au graphe d’une fonction partielle; lorsque pour tout il existe exactement un tel que , la relation correspond au graphe d’une fonction (totale). Dans ce cas on dit que est fonctionnelle ou simplement qu’elle est une fonction.

Réciproque

La réciproque (parfois appelée inverse) d’une relation est la relation

Lorsque est le graphe d’une fonction, sa réciproque est le graphe de la fonction inverse.

Relations sur un ensemble

Une relation est aussi appelée une relation sur . On classifie les relations sur un ensemble d’après leurs propriétés. Une relation est dite:

Réflexive
si pour tout on a ;
Symétrique
si pour tout on a ;
Transitive
si pour tout on a ;
Totale
si pour tout on a ;
Asymétrique
si pour tout on a ;
Antisymétrique
si pour tout on a .

Une relation qui est à la fois réflexive, symétrique et transitive est appelée une Équivalence.

Une relation qui est à la fois réflexive, antisymétrique et transitive est appelée un Ordre (partiel); lorsque elle est aussi totale elle est appelée un ordre total.

Une relation qui est à la fois transitive et asymétrique est appelée un ordre strict.

Excercice: montrer qu’une relation transitive et non réflexive est nécessairement asymétrique.

Exemples

Exercice: vérifier les propriétés susmentionnées.

Fork me on GitHub