Transitive Relations

Meaning of transitive relations, the chain condition, and examples showing how links extend through a middle element.

1. What a Transitive Relation Means

A transitive relation allows connections to pass through a middle element. If a is related to b, and b is related to c, then a must also be related to c. This three-step chain is the essence of transitivity.

2. Formal Condition

A relation R on a set A is transitive if:

2.1. Definition

(a,b) \in R \text{ and } (b,c) \in R \; \Rightarrow \; (a,c) \in R

3. Understanding the Chain

The idea is simple: if the relation connects a → b and b → c, then it must also include a → c to be transitive. Missing this final connection breaks transitivity.

3.1. Illustration

a \to b \to c \; \Rightarrow \; a \to c

4. Examples of Transitive Relations

Here are some relations where the chain condition holds:

4.1. Example 1 (Simple)

Let A = \{1,2,3\}:

R = \{(1,2),(2,3),(1,3)\}

Since (1,3) appears when needed, the relation is transitive.

4.2. Example 2 (Full Self-Pairs)

R = \{(a,a),(b,b),(c,c)\}

This is transitive because no chain breaks the rule.

4.3. Example 3 (Inequality)

The relation “≤” on numbers is transitive:

a \le b \text{ and } b \le c \Rightarrow a \le c

5. How to Check Transitivity

To test if a relation is transitive, look for pairs of the form (a,b) and (b,c). For every such pair, the relation must also contain (a,c).

5.1. Illustration

Let A = \{x,y,z\} and:

R = \{(x,y),(y,z)\}

For transitivity, (x,z) must appear. If it is missing, the relation is not transitive.

6. Non-Examples (Not Transitive)

A relation fails to be transitive when the third link (a,c) is missing even though (a,b) and (b,c) are present.

6.1. Example

R = \{(1,2),(2,3)\}

Since (1,3) is missing, this relation is not transitive.

7. Where Transitive Relations Appear

Transitive relations appear naturally in ordering, classification, and logical reasoning. Examples include:

  • “is an ancestor of”
  • “is a subset of” (⊆)
  • “≤” and “≥”