From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU  Thu Apr 17 20:58:38 2008
Date:         Thu, 17 Apr 2008 20:58:21 -0400
From: "William J. Rapaport" <rapaport@cse.Buffalo.EDU>
Subject: 191-Transitivity
To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU

------------------------------------------------------------------------
Subject: 191-Transitivity
------------------------------------------------------------------------

A student asks:

> I had a question about transitivity.
> Is the following relation transitive?: R={(a,b) , (b,b)}
> Because here we can go from a to a and from b to b and hence we can go from a to
> b. ...

Yes, it is.  To be transitive, a relation has to satisfy:

(for all x,y,z)[R(x,y) ^ R(y,z) -> R(x,z)]

There are only 2 possibilities for the antecedent:

R(a,b) ^ R(b,b)

R(b,b) ^ R(a,b)

In the first case, the consequent would be R(a,b), which is true.
In the second case, the consequent would not even be defined.  However,
because the antecedent is **false**, the conditional is true!  

So, it's true that all x,y,z satisfy the conditional, and so the
relation is transitive.