1. ## Transitive Relation

I feel dumb for asking, but i cant grasp the concept of transitivity for ordered pairs.

Like for example why is the relation R={(2,1),(2,3),(3,1)} transitive?

I get how if a=b and b=c then a=c but how do you apply this to ordered pairs?

2. ## Re: Transitive Relation

not "=", equivalent.

the idea is, we have to have a "witness" in the middle. if a~b, and b~c, then b is a witness to: a~c.

so, in your example, we need elements of {1,2,3} who do double-duty as a 1st coordinate, and 2nd coordinate.

1 doesn't qualify, 1 is never a "first coordinate".
2 doesn't qualify, 2 is never a "second coordinate."

so neither 1 nor 2 can be a witness to transitivity.

that just leaves 3. 3 acts as a witness for the pairs, (2,3) and (3,1), so if R is transitive, (2,1) needs to be in R.

(R "passes through 3" that is to say the relation "transits" or "travels" through the middle).

think of transitivity as being the rule: "you can always cut out the "middle man":

a~b~c means a~c.

(a,b) in R is the same thing as saying a~b.

3. ## Re: Transitive Relation

I see, that makes sense. Another example in my text says the relation S={(2,5),(5,6),(2,6),(7,7)} is also transitive. so i see how (2,5),(5,6) and (2,6) are transitive, but how does (7,7) come in to keep it transitive?

4. ## Re: Transitive Relation

Originally Posted by Deveno
not "=", equivalent.

a~b~c means a~c.

(a,b) in R is the same thing as saying a~b.
Not really equivalent -- just associated in this relation. R isn't an equivalence relation.

5. ## Re: Transitive Relation

I see, that makes sense. Another example in my text says the relation S={(2,5),(5,6),(2,6),(7,7)} is also transitive. so i see how (2,5),(5,6) and (2,6) are transitive, but how does (7,7) come in to keep it transitive?
The definition of a transitive relation is

For all a,b,c, elements of X, if (a,b) is an element of the relation and (b,c) is an element of the relation, then also (a,c) is an element of the relation.

Your relation is {(2,5),(5,6),(2,6),(7,7)}. Let's denote it R. We have to know whether the formula in the definition holds for every three elements a,b,c. Note first that only the cases when it is actually true that
$\displaystyle (a,b)\in R$ and $\displaystyle (b,c)\in R$
are interesting. In other cases, the formula is satisfied trivially. The interesting cases are a=2, b=5, c=6 and a=7, b= 7, c=7.

6. ## Re: Transitive Relation

Originally Posted by ymar
Not really equivalent -- just associated in this relation. R isn't an equivalence relation.
i stand corrected.

I see, that makes sense. Another example in my text says the relation S={(2,5),(5,6),(2,6),(7,7)} is also transitive. so i see how (2,5),(5,6) and (2,6) are transitive, but how does (7,7) come in to keep it transitive?
in this case, the only "witnesses" are 5 and 7.

for the relation to be transitive, we need (2,6) to be in R, and (7,7) to be in R. both of these are.

it's worth noting that (a,a) is a special case in transitive relations, it means that:

a~a~a implies a~a.

elements of the form (a,a) are called diagonal elements (imagine what the diagonal of the set of a relation on the unit interval [0,1] might look like (that would be pairs of real numbers (x,y) for which y=x, which you might recognize as a well-know function. all functions are actually relations, of a special sort.).).

the relation which consists of all diagonal elements and nothing else, is called "equality", and denoted by "=". this is a transitive relation.

7. ## Re: Transitive Relation

Thanks. Got it