Results 1 to 7 of 7

Math Help - Transitive Relation

  1. #1
    Member
    Joined
    Sep 2010
    Posts
    151
    Thanks
    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,378
    Thanks
    745

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2010
    Posts
    151
    Thanks
    1

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    Re: Transitive Relation

    Quote Originally Posted by Deveno View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    Re: Transitive Relation

    Quote Originally Posted by Aquameatwad View Post
    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
    (a,b)\in R and (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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,378
    Thanks
    745

    Re: Transitive Relation

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

    Quote Originally Posted by Aquameatwad View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Sep 2010
    Posts
    151
    Thanks
    1

    Re: Transitive Relation

    Thanks. Got it
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Determine whether the following relation is transitive
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 4th 2010, 10:25 AM
  2. [SOLVED] Transitive relation help please?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 23rd 2010, 12:39 AM
  3. Transitive relation help
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: December 3rd 2009, 03:40 PM
  4. Transitive closure relation.
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: March 8th 2009, 03:38 AM
  5. Transitive relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 19th 2009, 03:02 AM

Search Tags


/mathhelpforum @mathhelpforum