Relacja przechodnia

Relacja przechodnia (tranzytywna) to 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$ nazywamy przechodnią, gdy:

$\forall_{x,y,z \in X}\; ( x \;\varrho\; y \and y \;\varrho\; z ) \Rightarrow x \;\varrho\; z$.

Relacja $R$ jest przechodnia dokładnie wtedy, gdy $R\circ R\subseteq R,$ gdzie $\circ$ oznacza działanie składania relacji binarnych.

Przykłady

• Relacja równości,
• Relacje mniejszości, większości, niemniejszości, niewiększości,
• Relacja kolejności,
• Relacja podzielności w zbiorze liczb naturalnych $\mathbb N$ jest przechodnia,
• Relacja zawierania zbiorów jest przechodnia,
• Relacja różności „$\neq$” nie jest przechodnia,
• Relacja „jest rodzicem” nie jest przechodnia.
• Relacja „jest przodkiem” jest przechodnia.

Zobacz też

• relacja równoważności