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:
- Examine all pairs (a, b) and (b, c) in R where the second element of one pair matches the first element of another
- Check if the "shortcut" pair (a, c) also appears in R
- 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.