myth31
May 4th, 2010, 12:42 PM
Q) Determine whether the following relation is transitive
Relation R in the set N of natural numbers defined as
R = { (x,y) : y=x+5 and x<4}
The text book says that it is transitive. I dd not understand how it is transitive. Please help.
jemidiah
May 4th, 2010, 11:28 PM
That's a funny relation. I can see why it might trip you up. It's only technically transitive. Formally, the relation is transitive if ((xRy and yRz) implies xRz) is logically true. Suppose xRy; then x<4, and y=x+5, so y>4. Now suppose yRz; then y<4, which is a contradiction. Thus it can never be the case that xRy and yRz for some natural number y. Since the left hand side of the implication is always False, the implication is vacuously True, since the truth table for logical implication includes "False implies False" and "False implies True". Logical implication is defined this way since we don't want to restrict our conclusion whenever our premises were faulty in the first place; that is, we only really care if "A implies B" if A is actually True, regardless of the complete truth of A--since it may only be true in certain situations, represented by further assumptions.