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.
Feed/

What is transitivity, and how can it be tested in an explicit relation?

Channel

Brisk

1 page

"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."

Flowchart preview
Series cover
👍
0
0 comments0 shares

Sign in to view and post comments.