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 \and \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í. Kvaziuspořádání, které je symetrické, je relace ekvivalence.

Související články

• Tranzitivní uzávěr