Relacja przechodnia

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

Relacje przechodnie można przedstawiać diagramami Hassego; tutaj przykład przedstawiający inkluzję (zawieranie) podzbiorów w zbiorze trójelementowym.

Relacja zwycięstwa między ruchami jest przeciwprzechodnia.

Na płaszczyźnie dwie proste prostopadłe do jednej nie mogą być prostopadłe ze sobą, bo są równoległe.

Prostopadłość prostych w trójwymiarze nie jest przeciwprzechodnia – trzy osie układu współrzędnych kartezjańskich są prostopadłe parami.

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

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

Równoważnie, $\varrho$ jest przechodnia dokładnie wtedy, gdy $\varrho \circ \varrho \subseteq \varrho ,$ gdzie „$\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 $\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 „$\neq$”: $1\neq 2$ i $2\neq 1,$ ale $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.