Transzitív viszony

A matematikában a tranzitív reláció egy bináris reláció , amelyhez egymás után kapcsolt objektumok sora viszonyt eredményez az első és az utolsó között. Formálisan a tranzitivitás tulajdonságát írják fel egy halmazon definiált relációra : ${\ mathcal {R}}$ $E$

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

A nem tranzitív bináris reláció tehát egy olyan reláció, amelyre nézve a fenti univerzális tulajdonság hamis, vagyis a másodikhoz viszonyítva létezik egy olyan elem, amely maga egy harmadikhoz viszonyul, anélkül, hogy az első a harmadik: ${\ displaystyle \ létezik x, y, z \ E \ quad x {\ mathcal {R}} y \ land y {\ mathcal {R}} z \ land \ lnot (x {\ mathcal {R}} z) .}$ Ez a helyzet például a vonalak ortogonalitásával .

A transzitivitás ezen negációja különbözik az antitransitivitás tulajdonságától , amely megtiltja a kapcsolatok összefűzését a halmaz minden hármasán: ${\ displaystyle \ forall x, y, z \ in E \ quad (x {\ mathcal {R}} y \ land y {\ mathcal {R}} z) \ Rightarrow \ lnot (x {\ mathcal {R}} z).}$ Ez a helyzet a vonalak ortogonalitásával a síkban, de nem az űrben, ahol kettő-kettő merőleges vonal hármasai vannak. Másrészt az üres gráf bináris relációja (amely nem köt össze semmit) egyszerre antitranzitív és tranzitív.

Példák

Az egyenértékűségi viszonyok , a rend és a szigorú rendi viszonyok tranzitívak (kövesse az ilyen kapcsolatok példáira mutató linkeket).
A relation összefüggés nem transzitív és nem antitranzitív. a ≠ b és b ≠ c nem engedik kijelenteni, hogy a ≠ c , és hogy az a = c .
Az "az apja" reláció antitranszitív: ha (a a b apja) és (b a c apja), akkor (a nem c apja).
A készlet párok a valós számok , a kapcsolat ℛ által meghatározott „ $( x , y )$ ℛ $( x ' y' )$ akkor és csak akkor, ha $y < y '$ vagy $x < x'$ ” nem tranzitív, sem antitransitive.

Transzitív bezárás

Adott egy halmaz bináris relációja létezik egy minimális transzitív reláció, amely tartalmazza az első relációt, és amelyet transzitív bezárásnak nevezünk .

Referencia

J. Rivaud, algebra, előkészítő osztályokat és az egyetemi, gyakorlatok oldatokkal , Tome 1, Vuibert, 1978, p. 47 .