Worldlex Wiki mathématiques , une relation binaire ensemble ordre partiel et toute relation d'équivalence sont transitifs. Par exemple, les relations « inférieur à » et « égal » entre nombres réels sont toutes deux transitives : si Toutes les définitions exigent tacitement que la relation homogène soit transitive : pour tout si et alors La définition d'un terme peut exiger des propriétés supplémentaires qui ne sont pas répertoriées dans ce tableau.relations binaires transitives Symétrique Antisymétrique Connecté Bien fondé A des joints A rencontré Réfléchi Irréflexif Asymétrique Total, Semiconnecté Anti- réflexif relation d'équivalence 
Y✗ ✗ ✗ ✗ ✗ Y✗ ✗ Précommande (Quasicommande) ✗ ✗ ✗ ✗ ✗ ✗ Y✗ ✗ Commande partielle ✗ Y✗ ✗ ✗ ✗ Y✗ ✗ Précommande totale ✗ ✗ Y✗ ✗ ✗ Y✗ ✗ Commande totale ✗ YY✗ ✗ ✗ Y✗ ✗ Précommande ✗ ✗ YY✗ ✗ Y✗ ✗ Bien quasi-commander ✗ ✗ ✗ Y✗ ✗ Y✗ ✗ Bien ordonné ✗ YYY✗ ✗ Y✗ ✗ Treillis ✗ Y✗ ✗ YYY✗ ✗ Jointure-semi-treillis ✗ Y✗ ✗ Y✗ Y✗ ✗ Rencontre-semi-treillis ✗ Y✗ ✗ ✗ YY✗ ✗ Ordre partiel strict ✗ Y✗ ✗ ✗ ✗ ✗ YYordre faible strict ✗ Y✗ ✗ ✗ ✗ ✗ YYCommande totale stricte ✗ YY✗ ✗ ✗ ✗ YYSymétrique Antisymétrique Connecté Bien fondé A des joints A rencontré Réfléchi Irréflexif Asymétrique Définitions, pour tous et YLe symbole « + » indique que la propriété de la colonne est toujours vraie pour le terme de la ligne (à l'extrême gauche), tandis que le symbole « ✗ » indique que la propriété n'est pas garantie en général (elle peut être vraie ou fausse). Par exemple, le fait que toute relation d'équivalence soit symétrique, mais pas nécessairement antisymétrique, est indiqué par « + » dans la colonne « Symétrique » et par « ✗ » dans la colonne « Antisymétrique ». Y
Une relation homogène logique du premier ordre :
où notation infixe pour antitransitive : Alice ne peut jamais être la mère biologique de Claire.
Les relations non transitives et non antitransitives incluent les calendriers sportifs (programmes éliminatoires), « sait » et « parle à ».
Les exemples « est supérieur à », « est au moins aussi grand que » et « est égal à » ( égalité ) sont des relations transitives sur différents ensembles. De même que l'ensemble des nombres réels ou l'ensemble des nombres naturels.
- Si x > y et y > z , alors x > z également.
- Si x ≥ y et y ≥ z , alors x ≥ z également.
- chaque fois que x = y et y = z , alors aussi x = z .
Autres exemples de relations transitives :
- "est un sous-ensemble de" (inclusion d'ensembles, une relation sur les ensembles)
- « divise » ( divisibilité , une relation sur les nombres naturels)
- "implique" ( implication , symbolisée par "⇒", une relation sur les propositions )
Exemples de relations non transitives :
- "est le successeur de" (une relation sur les nombres naturels)
- "est un membre de l'ensemble" (symbolisé par "∈")
- "est perpendiculaire à" (une relation sur les droites en géométrie euclidienne )
La relation vide sur un ensemble quelconque est transitive car il n'existe aucun élément tel que et , et la condition de transitivité est donc trivialement vraie . Une relation paire ordonnée est également transitive : si la paire ordonnée est de la forme pour un certain , les seuls éléments tels sont , et dans ce cas , , tandis que si la paire ordonnée n'est pas de la forme , il n'existe aucun élément tel et la relation est donc trivialement transitive.
La transitivité vide est la transitivité lorsqu'il n'y a pas de paires ordonnées de la forme ( a , b ) et ( b , c ).
Propriétés
Propriétés de fermeture
- La réciproque d'une relation transitive est toujours transitive. Par exemple, sachant que « est un sous-ensemble de » est transitif et que « est un sur-ensemble de » est sa réciproque, on peut en conclure que cette dernière l'est également.
- L'intersection de deux relations transitives est toujours transitive. Par exemple, sachant que « est né avant » et « a le même prénom que » sont transitives, on peut conclure que « est né avant et a aussi le même prénom que » est également transitive.
- L'union de deux relations transitives n'implique pas nécessairement la transitivité. Par exemple, « est né avant ou porte le même prénom que » n'est pas une relation transitive, car Herbert Hoover est apparenté à Franklin D. Roosevelt , qui est lui-même apparenté à Franklin Pierce , tandis que Hoover n'est pas apparenté à Franklin Pierce.
- Le complément d'une relation transitive n'est pas nécessairement transitif. Par exemple, alors que « égal à » est transitif, « différent de » ne l'est que sur les ensembles ayant au plus un élément.
Autres propriétés
Une relation transitive est asymétrique si et seulement si elle est irréflexive .
Une relation transitive n'est pas nécessairement réflexive . Lorsqu'elle l'est, on parle de préordre . Par exemple, sur l'ensemble X = {1,2,3} :
- R = {
Extensions transitives et fermeture transitive
Dénombrement des relations transitives
Il n'existe pas de formule générale permettant de compter le nombre de relations transitives sur un ensemble fini A006905 dans l' OEIS ) . Cependant, il existe une formule pour trouver le nombre de relations simultanément réflexives, symétriques et transitives – autrement dit, les relations d'équivalence – A000110 dans l' OEIS ) , celles qui sont symétriques et transitives, celles qui sont symétriques, transitives et antisymétriques, et celles qui sont totales, transitives et antisymétriques. Pfeiffer a réalisé des progrès dans ce domaine, en exprimant les relations possédant des combinaisons de ces propriétés les unes en fonction des autres, mais le calcul de chacune d'elles reste complexe. Voir également Brinkmann et McKay (2005) et Mala (2022).
Puisque la réflexivisation de toute relation transitive est un préordre , le nombre de relations transitives an sur un ensemble à n éléments est au plus 2 n fois supérieur au nombre de préordres, il est donc asymptotiquement par les résultats de Kleitman et Rothschild.
| Transitif | Réfléchi | Symétrique | Précommande | Commande partielle | Précommande totale | Commande totale | relation d'équivalence | ||
|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 2 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
| 2 | 16 | 13 | 4 | 8 | 4 | 3 | 3 | 2 | 2 |
| 3 | 512 | 171 | 64 | 64 | 29 | 19 | 13 | 6 | 5 |
| 4 | 65 536 | 3 994 | 4 096 | 1 024 | 355 | 219 | 75 | 24 | 15 |
| n | 2 n 2 | 2 n ( n −1 ) | 2 n ( n +1)/2 | ∑n k =0k ! S ( n , k ) | n ! | ∑n k =0S ( n , k ) | |||
| OEIS | A002416 | A006905 | A053763 | A006125 | A000798 | A001035 | A000670 | A000142 | A000110 |
Notez que S ( n , k ) fait référence aux nombres de Stirling de seconde espèce .
Propriétés connexes
Une relation R est dite intransitive si elle n'est pas transitive, c'est-à-dire si xRy et yRz , mais pas xRz , pour certains x , y , z . À l'inverse, une relation R est dite antitransitive si xRy et yRz impliquent toujours que xRz est faux. Par exemple, la relation définie par xRy si xy est pair est intransitive mais pas antitransitive . La relation définie par xRy si x est pair et y impair est à la fois transitive et antitransitive ] La relation définie par xRy si x est le successeur de y est à la fois intransitive . Des exemples inattendus d'intransitivité apparaissent dans des situations telles que les questions politiques ou les préférences de groupe .
Généralisée aux versions stochastiques ( transitivité stochastique ), l'étude de la transitivité trouve des applications dans la théorie de la décision , la psychométrie et les modèles d'utilité .
Une relation quasi-transitive est une autre généralisation ; elle doit être transitive uniquement sur sa partie non symétrique. De telles relations sont utilisées en théorie du choix social ou en microéconomie .
Proposition : Si R est univalent , alors R;R T est transitif.
- Démonstration : Supposons que… Alors il existe a et b tels que… Puisque R est univalent, yRb et aR T y impliquent a = b . Par conséquent , x R a R T z , donc x R;R T z et R;R T est transitif.
Corollaire : Si R est univalent, alors R;R T est une relation d' équivalence sur le domaine de R.
- Démonstration : R ; R ⊆ T est symétrique et réflexive sur son domaine. L’univalence de R assure la transitivité nécessaire à l’équivalence.