Transitive relation

A relation $R$ on a set $A$ is called transitive, if the following hold, for all elements $a,b,c\in A$: $$ \text{If both } (a, b) \in R \text{ and } (b, c) \in R \text{ then } (a, c) \in R $$

In the directed graph representing $R$, $R$ is transitive, if every two-step journey along arrows can be done in one step. For example:

• The following graphs are not transitive:

  digraph A {
  	x->y
    y->z
    z->w
    x->z
  }
   
  digraph B {
  	x->y
    y->z
    z->w
    x->z
    x->w
  }

• The following graph is transitive:

  digraph B {
  	x->y
    y->z
    z->w
    x->z
    x->w
    y->w
  }

• Transitive: $<$, $>$, $\le$, $\ge$ on $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, or $\mathbb{R}$ For example, if $a<b$ then $b<c$ and so on…

• Transitive: $R_1=\{(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)\}$ on $\{1,2,3,4\}$

  digraph B {
  	1->1
    1->2
    1->3
    2->2
    2->3
    3->3
  }

• Transitive: $R_2=\{(3,4)\}$ on $\{3,4\}$ We cannot show it’s not transitive, since we only have one one-step journey.

  digraph B {
    3->4
  }

• Not transitive: $R_3=\{(1,1),(1,2),(2,1)\}$ on $\{1,2\}$

  digraph B {
    1->1
    1->2
    2->1
  }