Relacja przechodnia

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.

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

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

${\mathrm{\forall }}_{x,y,z\in X}(x\varrho y\wedge 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 binarnychSzablon:Fakt.

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 „$\ne$”: $1\ne 2$ i $2\ne 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.