Bifalgorithm post · Brisk · Chapter 1
What is transitivity, and how can it be tested in an explicit relation?
What is transitivity, and how can it be tested in an explicit relation? (Brisk · Chapter 1) — "A relation is transitive if whenever xRy and yRz, then it is gua…
Ideas in this flowchart
- Properties of relations: reflexivity, symmetry, antisymmetry, and transitivity
- A relation is transitive when xRy and yRz guarantee xRz.
- The relation “isTallerThan” is transitive: if Bob is taller than Jane and Jane is taller than Sue, Bob is taller than Sue.
- The relation “hasBeaten” among NFL teams is not necessarily transitive.
- The first Harry Potter relation contains (Harry, Ron), (Ron, Hermione), (Ron, Ron), (Hermione, Ron), (Ron, Harry), and (Hermione, Hermione).
- It is not reflexive because (Harry, Harry) is missing.
- It is symmetric because every ordered pair has its matching reverse pair.
- It is not antisymmetric because both (Harry, Ron) and (Ron, Harry) are present.
- It is not transitive because (Harry, Ron) and (Ron, Hermione) would require the missing pair (Harry, Hermione).
- The second Harry Potter relation contains (Ron, Harry), (Ron, Ron), (Harry, Harry), (Hermione, Hermione), (Harry, Hermione), and (Hermione, Harry).
- It is reflexive because all three wizards appear with themselves.
- It is not symmetric because (Ron, Harry) has no matching reverse pair.
- It is not antisymmetric because (Harry, Hermione) and (Hermione, Harry) are both present.
- It is not transitive because (Ron, Harry) and (Harry, Hermione) would require the missing pair (Ron, Hermione).
- Each property must fully apply; being almost reflexive, symmetric, antisymmetric, or transitive does not count.
