Course contentsShow
← Computer Science
Lesson 71 of 2,8722. Discrete Mathematics for CSFree lesson

Properties of Relations: Transitivity

Define transitive relations; verify transitivity and understand its implications for relation structure.

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.