Tranzitivní relace

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

Je menší nebo rovno je tranzitivní relace

Formálně zapsáno:

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

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