Thursday, June 3, 2010

[Math] Transitivity of relationships

Most of the relationships in the real world that we know are transitive. For example, if Bob is taller than Tom and Tom is taller than Alice, it naturally implies that Bob is taller than Alice. At the same time, there are many other relationships where the transitivity is not clear. Take for example, a triangular series among Sri Lanka, India and England. Let's say that India beat England and England beat Sri Lanka. Does that mean India will beat Sri Lanka (comprehensively)? Not necessarily - in fact, it has proven numerous times in the past that the transitive relationship does not hold (a tournament would be boring if it were the case). In other words, the relationship is probabilistic in nature.

Some more not necessarily transitive examples in the technology/science field:
(Social networks) Bob is a friend of Sam. Sam is a friend of Tom. It does not necessarily imply that "Bob is a friend of Tom".
(Trust relationships in security) Alice trusts Bob to keep a secret. Bob trusts Mary to keep a secret. It does not necessarily imply that "Alice trusts Mary to keep a secret" since Alice needs to trust on something else to make the transitivity working. That something is Bob's ability to judge Mary's trustworthiness to keep a secret.

I also find that some relationships can never be transitive. For example:
(Family relationships) Mary is mother of Alice; Alice is mother of Eve. It is incorrect to say "Mary is mother of Eve".

In computer science, we mostly deal with deterministic transitivity. Take for example, Lamport's clock; if an event A occurs before an event B and an event C occurs before the event A, we safely conclude that the event C occurs before the event B. And the transitivity always holds. But, what about probabilistic transitivity?

No comments: