Tranzitivní relace

Je menší nebo rovno je 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:

$\mathrm{\forall }\alpha ,\beta ,\gamma \in X,\alpha R\beta \wedge \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.

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

Související články

• Tranzitivní inference
• Tranzitivní uzávěr