Properties of Relations: Transitivity
What you'll learn: You'll understand what makes a relation transitive and how to verify this important structural property.
What is Transitivity?
A relation R on a set is transitive if whenever element a is related to b, and b is related to c, then a must also be related to c.
In formal notation: For all a, b, c in the set, if (a,b) ∈ R and (b,c) ∈ R, then (a,c) ∈ R.
The Chain Analogy
Think of transitivity like a chain of connections: if Alice knows Bob, and Bob knows Carol, then in a transitive "knows" relation, Alice must also know Carol. The relation forms a continuous chain without broken links.
Checking Transitivity
To verify transitivity, examine every pair of ordered pairs where the second element of one matches the first element of another:
Example 1: R = {(1,2), (2,3), (1,3)} on set {1,2,3}
- (1,2) and (2,3) are in R → check if (1,3) is in R ✓
- This relation is transitive
Example 2: R = {(1,2), (2,3)} on set {1,2,3}
- (1,2) and (2,3) are in R → but (1,3) is missing ✗
- This relation is not transitive
Example 3: R = {(1,1), (2,2), (3,3)} (reflexive relation)
- No chains to check where different elements connect
- This relation is transitive (vacuously true)
Why It Matters
Transitivity appears in many CS contexts: "less than" (<), "is ancestor of," file system hierarchies, and network reachability all exhibit transitive behavior. When modeling systems, knowing whether a relation is transitive helps predict indirect connections.
Key Takeaway: A relation is transitive when every indirect connection through an intermediate element implies a direct connection—forming consistent chains without gaps.