transzivitás

Transzivitás a relációk egyik alapvető tulajdonsága. Egy reláció R egy halmazon X transzív, ha minden a, b, c ∈ X esetén, ha aRb és bRc, akkor aRc.

Példák: a természetes számok ≤ relációja transzív: ha a ≤ b és b ≤ c, akkor a ≤ c. Az egyenlőség = transzív: ha a=b és b=c, akkor a=c. Az osztási reláció ｜ is transzív: ha a|b és b|c, akkor a|c. A részhalmaz relációja ⊆ szintén transzív: ha A⊆B és B⊆C, akkor A⊆C. Logikában, ha P→Q és Q→R, akkor P→R is igaz.

Nem minden reláció transzív. Például a „szülője” viszony: ha A szülője B és B szülője C, A nem feltétlenül C szülője; gyakran csak nagyszülő vagy más rokoni kapcsolat áll fenn.

Transzivitás és lezárás: adott R-reláció esetén a transzív lezárás R+ a legkisebb olyan transzív reláció, amely tartalmazza R-t. Grafokban ez az elérhetőségi viszonyok meghatározását jelenti, és számítástechnikai alkalmazásokban Warshall- vagy más algoritmusokkal számítható.

Összefoglalva a transzivitás olyan tulajdonság, amely lehetővé teszi láncokból eredő közvetett kapcsolatok egyszerűbb kiértékelését, és fontos szerepet játszik például a részben rendezett halmazok és kapcsolatrendszerek leírásában.