Tranzitivní relace

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

V logice a matematice se binární relace R na množině X nazývá tranzitivní, pokud pro každé \alpha, \beta a \gammaX 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[editovat | editovat zdroj]