Transitivt forhold

I matematik er et transitivt forhold et binært forhold, for hvilket en række sammenhængende objekter resulterer i et forhold mellem det første og det sidste. Formelt er ejendommen til transitivitet skrevet for en relation defineret på et sæt : ${\ mathcal {R}}$ $E$

{\ displaystyle \ forall x, y, z \ i E \ quad (x {\ mathcal {R}} y \ land y {\ mathcal {R}} z) \ Rightarrow x {\ mathcal {R}} z.}

En ikke-transitiv binær relation er derfor en relation, for hvilken den universelle egenskab ovenfor er falsk, det vil sige, at der eksisterer et element i forhold til et sekund, som i sig selv er i forhold til et tredje, uden at det første er relateret til tredje: ${\ displaystyle \ findes x, y, z \ i E \ quad x {\ mathcal {R}} y \ land y {\ mathcal {R}} z \ land \ lnot (x {\ mathcal {R}} z) .}$ Dette er f.eks. Tilfældet med linjernes ortogonalitet .

Denne negation af transitivitet adskiller sig fra egenskaben antitransitivitet , som forbyder sammenkædning af relationer på alle tredobler af sættet: ${\ displaystyle \ forall x, y, z \ i E \ quad (x {\ mathcal {R}} y \ land y {\ mathcal {R}} z) \ Rightarrow \ lnot (x {\ mathcal {R}} z).}$ Dette er tilfældet for linjernes ortogonalitet i planet, men ikke i rummet, hvor der er tripletter af to-to-to ortogonale linjer. På den anden side er den binære relation mellem tom graf (som ikke forbinder noget) antitransitiv og transitiv på samme tid.

Eksempler

De ækvivalensrelationer , de relationer orden og streng ordre relationer er transitive (følg links til eksempler på sådanne relationer).
Forholdet ≠ er hverken transitivt eller antitransitivt. a ≠ b og b ≠ c tillader os ikke at angive, at a ≠ c , heller ikke at a = c .
Forholdet "er far til" er anti-transitivt: hvis (a er far til b) og (b er far til c), så (a er ikke far til c).
På sættet med par af reelle tal er forholdet ℛ defineret af “ $( x , y )$ ℛ $( x ' , y' )$ hvis og kun hvis $y < y '$ eller $x < x'$ ” ikke er transitivt eller antitransitivt.

Transitiv lukning

Givet en binær relation på et sæt, findes der en minimal transitiv relation, der indeholder den første relation og kaldes transitive lukning .

Reference

J. Rivaud, Algebra, Forberedende klasser og universitet, Øvelser med løsninger , tome 1, Vuibert, 1978, s. 47 .