Relation homogène

En mathématiques , une relation homogène (également appelée endorélation ) sur un ensemble X est une relation binaire entre X et lui-même, c'est-à-dire qu'elle est un sous-ensemble du produit cartésien X × X. [ Ceci est communément formulé comme « une relation sur X » ou « une relation (binaire) sur X ». Un exemple de relation homogène est la relation de parenté , où la relation est entre des personnes.

Les types courants d'endorélations comprennent les ordres , les graphes et les équivalences . Des études spécialisées sur la théorie des ordres et la théorie des graphes ont permis de mieux comprendre les endorélations. La terminologie propre à la théorie des graphes est utilisée pour la description, un graphe ordinaire (non orienté) étant supposé correspondre à une relation symétrique et une endorélation générale correspondant à un graphe orienté . Une endorélation R correspond à une matrice logique de 0 et de 1, où l'expression xRy correspond à une arête entre x et y dans le graphe et à un 1 dans la matrice carrée de R. Elle est appelée matrice d'adjacence dans la terminologie des graphes.

Relations homogènes particulières

Certaines relations homogènes particulières sur un ensemble X (avec des éléments arbitraires x ₁ , x ₂ ) sont :

Relation vide
E = ∅ ;
c'est-à-dire que x ₁Ex ₂ n'est jamais vrai ;
Relation universelle
U = X × X ;
c'est-à-dire que x ₁Ux ₂ est toujours vrai ;
Relation d'identité (voir aussi Fonction d'identité )
I = {( x , x ) | x ∈ X };
autrement dit, x ₁Ix ₂ est vrai si et seulement si x ₁ = x ₂ .

Exemple

Quinze grandes plaques tectoniques de la croûte terrestre sont en contact les unes avec les autres dans une relation homogène. La relation peut être exprimée sous la forme d'une matrice logique dans laquelle 1 indique un contact et 0 aucun contact. Cet exemple exprime une relation symétrique.

Propriétés

Certaines propriétés importantes qu'une relation homogène R sur un ensemble X peut avoir sont :

Réfléchi: pour tout x ∈ X , xRx . Par exemple, ≥ est une relation réflexive mais > ne l'est pas.
Irréflexif (ou strict ): pour tout x ∈ X , pas xRx . Par exemple, > est une relation irréflexive, mais ≥ ne l'est pas.
Coréflexif: pour tout x , y ∈ X , si xRy alors x = y . Par exemple, la relation sur les entiers dans laquelle chaque nombre impair est relié à lui-même est une relation coréflexive. La relation d'égalité est le seul exemple de relation à la fois réflexive et coréflexive, et toute relation coréflexive est un sous-ensemble de la relation d'identité.
Quasi-réflexif gauche: pour tout x , y ∈ X , si xRy alors xRx .
Quasi-réflexif droit: pour tout x , y ∈ X , si xRy alors yRy .
Quasi-réflexif: pour tout x , y ∈ X , si xRy alors xRx et yRy . Une relation est quasi-réflexive si, et seulement si, elle est quasi-réflexive à la fois à gauche et à droite.

Les 6 alternatives précédentes sont loin d'être exhaustives ; par exemple, la relation binaire xRy définie par y = x ² n'est ni irréflexive, ni coréflexive, ni réflexive, puisqu'elle contient respectivement la paire (0, 0) et (2, 4) mais pas (2, 2) . Ces deux derniers faits excluent également (tout type de) quasi-réflexivité.

Symétrique: pour tout x , y ∈ X , si xRy alors yRx . Par exemple, « est un parent par le sang de » est une relation symétrique, car x est un parent par le sang de y si et seulement si y est un parent par le sang de x .
Antisymétrique: pour tout x , y ∈ X , si xRy et yRx alors x = y . Par exemple, ≥ est une relation antisymétrique ; il en va de même pour >, mais de manière vide (la condition dans la définition est toujours fausse).
Asymétrique: pour tout x , y ∈ X , si xRy alors non yRx . Une relation est asymétrique si et seulement si elle est à la fois antisymétrique et irréflexive. Par exemple, > est une relation asymétrique, mais ≥ ne l'est pas.

Encore une fois, les 3 alternatives précédentes sont loin d'être exhaustives ; à titre d'exemple sur les entiers naturels, la relation xRy définie par x > 2 n'est ni symétrique ni antisymétrique, et encore moins asymétrique.

Transitif: pour tout x , y , z ∈ X , si xRy et yRz alors xRz . Une relation transitive est irréflexive si et seulement si elle est asymétrique. Par exemple, « est l'ancêtre de » est une relation transitive, tandis que « est le parent de » ne l'est pas.
Antitransitif: pour tout x , y , z ∈ X , si xRy et yRz alors jamais xRz .
Co-transitif: si le complément de R est transitif. C'est-à-dire, pour tout x , y , z ∈ X , si xRz , alors xRy ou yRz . Ceci est utilisé dans les pseudo-ordres en mathématiques constructives.
Quasitransitif: pour tout x , y , z ∈ X , si xRy et yRz mais ni yRx ni zRy , alors xRz mais pas zRx .
Transitivité de l'incomparabilité: pour tout x , y , z ∈ X , si x et y sont incomparables par rapport à R et si la même chose est vraie pour y et z , alors x et z sont également incomparables par rapport à R . Ceci est utilisé dans les ordres faibles .

Encore une fois, les 5 alternatives précédentes ne sont pas exhaustives. Par exemple, la relation xRy si ( y = 0 ou y = x +1 ) ne satisfait aucune de ces propriétés. En revanche, la relation vide les satisfait toutes de manière triviale.

Dense: pour tout x , y ∈ X tel que xRy , il existe un z ∈ X tel que xRz et zRy . Ceci est utilisé dans les ordres denses .
Connecté: pour tout x , y ∈ X , si x ≠ y alors xRy ou yRx . Cette propriété est parfois appelée « total », ce qui est différent des définitions de « total gauche/droite » données ci-dessous.
Fortement connecté: pour tout x , y ∈ X , xRy ou yRx . Cette propriété est aussi parfois , ce qui est différent des définitions de « total gauche/droite » données ci-dessous.
Trichotomique: pour tout x , y ∈ X , on a exactement l'une des relations xRy , yRx ou x = y . Par exemple, > est une relation trichotomique sur les nombres réels, alors que la relation « divise » sur les nombres naturels ne l'est pas.
Euclidienne droite (ou simplement euclidienne ): pour tout x , y , z ∈ X , si xRy et xRz alors yRz . Par exemple, = est une relation euclidienne car si x = y et x = z alors y = z .
Euclidienne gauche: pour tout x , y , z ∈ X , si yRx et zRx alors yRz .
Bien fondé: tout sous-ensemble non vide S de X contient un élément minimal par rapport à R . La bonne fondation implique la condition de chaîne descendante (c'est-à-dire qu'aucune chaîne infinie ... x _n R ... Rx ₃Rx ₂Rx ₁ ne peut exister). Si l'on suppose l' axiome du choix dépendant , les deux conditions sont équivalentes.

De plus, toutes les propriétés des relations binaires en général peuvent également s’appliquer aux relations homogènes :

En forme d'ensemble: pour tout x ∈ X , la classe de tout y tel que yRx soit un ensemble. (Cela n'a de sens que si les relations sur des classes propres sont autorisées.)
Gauche unique: pour tout x , z ∈ X et tout y ∈ Y , si xRy et zRy alors x = z .
Univalent: pour tout x ∈ X et tout y , z ∈ Y , si xRy et xRz alors y = z .
Total (également appelé total gauche): pour tout x ∈ X il existe un y ∈ Y tel que xRy . Cette propriété est différente de la définition de connexe (appelée aussi totale par certains auteurs).
Surjectif (également appelé droit-total): pour tout y ∈ Y , il existe un x ∈ X tel que xRy .

Un préordre est une relation à la fois réflexive et transitive. Un préordre total , également appelé préordre linéaire ou ordre faible , est une relation à la fois réflexive, transitive et connexe.

Un ordre partiel , également appelé ordre , est une relation qui est réflexive, antisymétrique et transitive. Un ordre partiel strict , également appelé ordre strict , est une relation qui est irréflexive, antisymétrique et transitive. Un ordre total , également appelé ordre linéaire , ordre simple ou chaîne , est une relation qui est réflexive, antisymétrique, transitive et connexe. Un ordre total strict , également appelé ordre linéaire strict , ordre simple strict ou chaîne stricte , est une relation qui est irréflexive, antisymétrique, transitive et connexe.

Une relation d'équivalence partielle est une relation symétrique et transitive. Une relation d'équivalence est une relation réflexive, symétrique et transitive. C'est aussi une relation symétrique, transitive et totale, puisque ces propriétés impliquent une réflexivité.

Opérations

Si R est une relation homogène sur un ensemble X alors chacune des relations suivantes est une relation homogène sur X :

Fermeture réflexive , R ⁼: Défini comme R ⁼ = {( x , x ) | x ∈ X } ∪ R ou la plus petite relation réflexive sur X contenant R . On peut prouver que cela est égal à l' intersection de toutes les relations réflexives contenant R .
Réduction réflexive , R ^≠: Défini comme R ^≠ = R \ {( x , x ) | x ∈ X } ou la plus grande relation irréflexive sur X contenue dans R .
Fermeture transitive , R ⁺: Défini comme la plus petite relation transitive sur X contenant R . On peut considérer que cela est égal à l'intersection de toutes les relations transitives contenant R .
Clôture transitive réflexive , R *: Défini comme R * = ( R ⁺ ) ⁼ , le plus petit préordre contenant R .
Fermeture symétrique transitive réflexive , R ^≡: Défini comme la plus petite relation d'équivalence sur X contenant R .

Toutes les opérations définies dans Relation binaire § Opérations s'appliquent également aux relations homogènes.

Énumération

L'ensemble de toutes les relations homogènes sur un ensemble X est l'ensemble 2 ^X^×^X , qui est une algèbre booléenne augmentée de l' involution de l'application d'une relation à sa relation inverse . Considérant la composition des relations comme une opération binaire sur , elle forme un monoïde avec involution où l'élément d'identité est la relation d'identité. ${\displaystyle {\mathcal {B}}(X) <semantics> <mrow> <mstyle> <mrow> <mrow> <mi>B</mi> </mrow> </mrow> <mo>(</mo> <mi>X</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle {\mathcal {B}}(X)}</annotation> </semantics> </math></span><img src=$ ${\displaystyle {\mathcal {B}}(X) <semantics> <mrow> <mstyle> <mrow> <mrow> <mi>B</mi> </mrow> </mrow> <mo>(</mo> <mi>X</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle {\mathcal {B}}(X)}</annotation> </semantics> </math></span><img src=$

Le nombre de relations homogènes distinctes sur un ensemble de n éléments est 2 ^{n ²} (séquence A002416 dans l' OEIS ) :

Notez que S ( n , k ) fait référence aux nombres de Stirling de deuxième espèce .

Remarques :

Le nombre de relations irréflexives est le même que celui des relations réflexives.
Le nombre d' ordres partiels stricts (relations transitives irréflexives) est le même que celui des ordres partiels.
Le nombre d’ordres faibles stricts est le même que celui des préordres totaux.
Les commandes totales sont les commandes partielles qui sont également des précommandes totales. Le nombre de précommandes qui ne sont ni une commande partielle ni une précommande totale est donc le nombre de précommandes, moins le nombre de commandes partielles, moins le nombre de précommandes totales, plus le nombre de commandes totales : 0, 0, 0, 3 et 85, respectivement.
Le nombre de relations d'équivalence est le nombre de partitions , qui est le nombre de Bell .

Les relations homogènes peuvent être groupées en couples (relation, complément ), sauf que pour n = 0 la relation est son propre complément. Les relations non symétriques peuvent être groupées en quadruples (relation, complément, inverse, complément inverse).

Exemples

Relations d’ordre , y compris les ordres stricts :
- Plus grand que
- Supérieur ou égal à
- Moins que
- Inférieur ou égal à
- Divise (égale)
- Sous-ensemble de
Relations d'équivalence :
- Égalité
- Parallèle à (pour les espaces affines )
- Équinomérosité ou « est en bijection avec »
- Isomorphe
- Segments de droite équipollents
Relation de tolérance , une relation réflexive et symétrique :
- Relation de dépendance , une relation de tolérance finie
- Relation d'indépendance , complément d'une relation de dépendance
Relations de parenté

Généralisations

Une relation binaire en général n'a pas besoin d'être homogène, elle est définie comme un sous-ensemble R ⊆ X × Y pour des ensembles arbitraires X et Y .
Une relation finitaire est un sous-ensemble R ⊆ X ₁ × ... × X _n pour un nombre naturel n et des ensembles arbitraires X ₁ , ..., X _n , elle est également appelée relation n -aire.