Tranzitivní relace

V logice a matematice se binární relace R na množině X nazývá tranzitivní, pokud pro každé \alpha, \beta a \gamma z X platí, že pokud \alpha je v relaci s \beta a \beta je v relaci s \gamma, je i \alpha v relaci s \gamma.

Formálně zapsáno:

:\forall \alpha, \beta, \gamma \in X,\ \alpha R \beta \land \beta R \gamma \; \Rightarrow \alpha R \gamma

Například „je větší než“ a „je rovno“ jsou tranzitivní relace: pokud a = b a b = c, platí i a = c.

Na druhou stranu, „je matkou“ není tranzitivní relace, protože když Alice je matkou Břetislavy a Břetislava je matkou Cecílie, není Alice matkou Cecílie.

Dalšími příklady tranzitivních relací jsou: * „je podmnožinou“ * „je větší než“ * „je větší nebo rovno“ * „je menší nebo rovno“ * „dělí“ (dělitelnost)

Tranzitivní relace, která je zároveň reflexivní, se nazývá kvaziuspořádání. Kvaziuspořádání, které je slabě antisymetrické, se nazývá uspořádání. +more Kvaziuspořádání, které je symetrické, je relace ekvivalence.

Uvažování pomocí tranzitivní inference jsou schopny i pouhé vosy.

Reference

Související články

Tranzitivní inference * Tranzitivní uzávěr

Kategorie:Teorie množin Kategorie:Vlastnosti matematických relací