Concept
What is transitivity, and how can it be tested in an explicit relation?
Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk / Chapter 1
"A relation is transitive if whenever xRy and yRz, then it is guaranteed that xRz. The “isTallerThan” relation is transitive: if Bob is taller than Jane, and Jane is taller than Sue, then Bob must be taller than Sue. An example of a non-transitive relation would be “hasBeaten” with NFL teams. Just because the Patriots beat the Steelers this year, and the Steelers beat the Giants, that does not imply that the Patriots necessarily beat the Giants. The two teams might not even have played each other that year. Using the familiar Harry Potter set as A, consider the relation containing (Harry, Ron), (Ron, Hermione), (Ron, Ron), (Hermione, Ron), (Ron, Harry), and (Hermione, Hermione). This relation is not reflexive because it has (Ron, Ron) and (Hermione, Hermione) but is missing (Harry, Harry). It is symmetric because every ordered pair has its matching reverse pair: (Harry, Ron) matches (Ron, Harry), and (Hermione, Ron) matches (Ron, Hermione). It is not antisymmetric because both (Harry, Ron) and (Ron, Harry) are present. Finally, it is not transitive because (Harry, Ron) and (Ron, Hermione) would require (Harry, Hermione), which is missing. Consider another relation containing (Ron, Harry), (Ron, Ron), (Harry, Harry), (Hermione, Hermione), (Harry, Hermione), and (Hermione, Harry). This one is reflexive because all three wizards appear with themselves. It is not symmetric because (Ron, Harry) has no match, and it is not antisymmetric because (Harry, Hermione) does have a matching reverse pair. It is also not transitive because (Ron, Harry) and (Harry, Hermione) would require (Ron, Hermione), which does not appear. To meet any of these properties, they have to fully apply; “almost” only counts in horseshoes."
Related Ideas
- Is H transitive?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- What are the reflexive, symmetric, antisymmetric, and transitive properties of the endorelation T?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- What do reflexivity, symmetry, and antisymmetry mean for endorelations?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- What properties does the outranks relation have?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- What properties does the sameShirtColor relation have?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- Is H symmetric?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- Is H reflexive?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1
- Does a relation between a set and itself require the two elements of each pair to be the same?Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk · Chapter 1