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é , a X platí, že pokud je v relaci s  a je v relaci s , je i v relaci s .

Formálně zapsáno:

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]