Course contentsShow
← Mathematics
Lesson 2545 of 3,12151. Discrete Math — Sets, Relations, FunctionsFree lesson

Transitive Relations

Define transitivity and verify whether a relation is transitive by checking if relating through an intermediate element holds.

Transitive Relations

What You'll Learn

You'll learn what transitivity means for a relation and how to check whether a given relation satisfies this property.

The Core Idea

A relation R on a set is transitive if whenever one element relates to a second, and that second relates to a third, then the first must also relate directly to the third.

Formally: R is transitive if for all elements a, b, c in the set, whenever (a, b) ∈ R and (b, c) ∈ R, it must follow that (a, c) ∈ R.

Think of it like a chain of connections: if A connects to B, and B connects to C, then transitivity requires A to connect directly to C as well.

Testing for Transitivity

To verify transitivity:

  1. Examine all pairs (a, b) and (b, c) in R where the second element of one pair matches the first element of another
  2. Check if the "shortcut" pair (a, c) also appears in R
  3. If even one chain fails this test, R is not transitive

Example 1: Let R = {(1,2), (2,3), (1,3)} on {1,2,3}

  • We have (1,2) and (2,3) in R
  • We need (1,3) in R ✓ (it's there)
  • R is transitive

Example 2: Let R = {(1,2), (2,3)} on {1,2,3}

  • We have (1,2) and (2,3) in R
  • We need (1,3) in R ✗ (missing!)
  • R is not transitive

Common Transitive Relations

  • "Less than or equal to" (≤): if a ≤ b and b ≤ c, then a ≤ c
  • "Is an ancestor of": if A is ancestor of B, and B is ancestor of C, then A is ancestor of C
  • "Divides" on integers: if a|b and b|c, then a|c

Key Takeaway: A relation is transitive when relating through an intermediate element guarantees a direct relation between the endpoints—verify by checking every possible chain.