Relacja przechodnia (tranzytywna) – relacja, która jeśli zachodzi dla pary ${\displaystyle (x,y)}$ oraz pary ${\displaystyle (y,z)}$, to zachodzi też dla pary ${\displaystyle (x,z)}$.

Relację dwuczłonową ${\displaystyle \varrho \subset X\times X}$ nazywa się przechodnią, gdy:

${\displaystyle \forall _{x,y,z\in X}\;(x\;\varrho \;y\land y\;\varrho \;z)\Rightarrow x\;\varrho \;z.}$

Równoważnie, ${\displaystyle \varrho }$ jest przechodnia dokładnie wtedy, gdy ${\displaystyle \varrho \circ \varrho \subseteq \varrho ,}$ gdzie „${\displaystyle \circ }$” oznacza działanie składania relacji binarnych.

Przechodniość jest jedną z definiujących cech praporządków, w tym relacji równoważności i porządków częściowych (skierowań).

Przykłady

Relacje przechodnie:

• każda relacja równoważności, np. równość,
• relacje częściowego porządku (skierowania) jak:
  • niewiększość (⩽) i niemniejszość (⩾), np. liczb,
  • zawieranie zbiorów (⊆, ⊇),
  • podzielność (|) w zbiorze liczb naturalnych ${\displaystyle \mathbb {N} ,}$
• porządki ostre (ścisłe jak):
  • relacje mniejszości (<) i większości (>),
  • bycie przodkiem (wstępnym),
• braterstwo rodzone (ścisłe).

Przeciwprzechodniość

Wśród relacji nieprzechodnich szczególną klasą są przeciwprzechodnie, in. atranzytywne – zachodzenie ich dla par (x,y) i (y,z) gwarantuje, że nie zachodzą dla (x,z). Przykłady:

• prostopadłość prostych na płaszczyźnie,
• zwycięstwo jednego gestu nad innym w grze w papier, kamień, nożyce.

Relacje, które nie są ani przechodnie, ani przeciwprzechodnie:

• relacja różności „${\displaystyle \neq }$”: ${\displaystyle 1\neq 2}$ i ${\displaystyle 2\neq 1,}$ ale ${\displaystyle 1=1,}$
• przecinanie się zbiorów,
• względna pierwszość liczb,
• prostopadłość prostych w trójwymiarze,
• liniowa niezależność dwóch wektorów,
• przemienność komutacja funkcji w danym zbiorze (działań jednoargumentowych) lub macierzy kwadratowych,
• współpłaszczyznowość (komplanarność) dwóch prostych, półprostych, odcinków lub wektorów,
• podgrupa normalna,
• rodzicielstwo – dziadkowie na ogół nie są rodzicami swoich wnuków, ale są wyjątki przez kazirodztwo.

Przypisy