Transitive, And Related Notions

Transitive, and Related Notions: To define transitivity in terms of graphs, we need the notions of a broken journey and a short cut. There is a broken journey from dot x to dot z via dot y, if there is an arrow from x to y and an arrow from y to z. Note that dot x might be the same as dot y, and dot y might be the same as dot z. Therefore if a, a ∈ R and a, b ∈ R, there is a broken journey from a to b via a. Example: there is a broken journey from Utah to Nevada via Arizona. There is also a broken journey from Utah to Nevada via Utah.
There is a short cut just if there is an arrow direct from x to z. So if a, b ∈ R and b, c ∈ R and also a, c ∈ R, we have a broken journey from a to c via b, together with a short cut. Also if a, a ∈ R and a, b ∈ R, there is a broken journey from a to b via a, together with a short cut.
Example: There is a broken journey from Utah to Nevada via Arizona, and a short cut from Utah to Nevada.

R is transitive if for all x, y, z ∈ S, x, y ∈ R ∧ y, z ∈ R ⇒ x, z ∈ R. Equivalently,
There is no broken journey without a short cut.

R is intransitive if, for all x, y, z ∈ S, x, y ∈ R ∧ y, z ∈ R ⇒ x, z /∈ R. Equivalently,

There is no broken journey with a short cut.

R is non-transitive if and only if it is neither transitive nor intransitive. Equivalently, There is at least one broken journey with a short cut and at least one without.
Examples::

• Relations R1 and R2 above are transitive.
• R3 is non-transitive, since it is lacking the pair 1, 3.
• Another non-transitive relation is = over Nat, because from a = b and b = c, we cannot always conclude that a = c.
• R4 is irreflexive, transitive, and asymmetric.
• R5 is still irreflexive. It is not transitive, as there is no loop at 1. It is not intransitive because there is a broken journey (2 to 3 via 1) with a short cut (2 to 1). It is non-transitive because there is one broken journey without a short cut and one without.
• R5 is not symmetric because there are single arrows.
• R5 is not asymmetric because there are double arrows.
• From the above, it follows that R5 is non-symmetric.
• R5 is not antisymmetric because there is a double arrow that is not a loop.

Preorder (reflexive plus transitive): If R is reflexive and transitive, then it is known as a preorder. Continuing with the example of basketball players, let the BB relation for three members A, B, and C of the team be
{A,A, A,B, B,A, B,B, A,C, B,C, C,C}.
This relation is a preorder because it is reflexive and transitive. It helps compare three players A, B, and C, treating A and B to be equivalent in abilities, and C to be superior in abilities to both.
Partial order (preorder plus antisymmetric): If R is reflexive, antisymmetric, and transitive, then it is known as a partial order. As shown in Section 4.1.1 under the heading of antisymmetry, the subset or equals relation ⊆ is a partial order.

Total order, and related notions: A total order is a special case of a partial order. R is a total order if for all x, y ∈ S, either x, y ∈ R or y, x ∈ R. Here, x and y need not be distinct (this is consistent with the fact that total orders are reflexive). The ≤ relation on Nat is a total order. Note that ‘<’ is not a total order, because it is not reflexive.1 However, ‘<’ is transitive. Curiously, ‘<’ is antisymmetric.
A relation R is said to be total if for all x ∈ S, there exists y ∈ S such that x, y ∈ R. In other words, a “total” relation is one in which every element x is related to at least one other element y. If we consider y to be the image (mapping) of x under R, this definition is akin to the definition of a total function.
Note again that R being a total order is not the same as R being a partial order and a total relation. For example, consider the following relation R over set

S = {a, b, c, d}:
R = {a, a, b, b, c, c, d, d, a, b, c, d}
R is a partial order. R is also a total relation. However, R is not a total order, because there is no relationship between b and c (neither b, c nor c, b is in R).