Tranzitivní relace

binární relace R s vlastností, že xRy a yRz implikuje xRz
(přesměrováno z Transitivní relace)

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.

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

ReferenceEditovat

  1. Paper wasps capable of behavior that resembles logical reasoning. phys.org [online]. 2019-05-07 [cit. 2022-01-19]. Dostupné online. (anglicky) 

Související článkyEditovat