1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Binary Relations-Transitivity

  1. Dec 5, 2006 #1
    Binary Relations--Transitivity

    Hello everyone i'm not sure if i'm hitting all the ordered pairs on this because i can't seem to find a good method to figure it out. I also think the relation to itself is confusing me.

    here is the question:
    S is a binary relation defined on A = {0,1,2,3}

    to speed up this message, i'm going to represent an ordered pair like 00 instead of (0,0).

    Let S = {00, 03, 10, 12, 20, 32}

    Find S^t, the transititve closure of S.
    note: ... 32 .. stands for (3,2), etc

    Okay i know for somthing to be transitive, if you have an arrow from point 0 to 0, then it has a relation to itself..
    If i had say a relation like (0,1) and (1,2) then I can make an ordered pair from (0,2).
    Thats what i'm doing in this problem

    So i got the following but i'm not sure if i'm right.
    S^t = S UNION { 11, 33, 22, 30, 01, 02 13, 31}

  2. jcsd
  3. Dec 5, 2006 #2


    User Avatar
    Science Advisor

    It's not a question of if you have "missed" any- you have far too many pairs in there. "Transitive" does NOT imply "reflexive"! If ab and bc are in S then ac would have to be in S^t in order for S^t to be a transitive extension of S. In order that it be the smallest such, we would have to have ac in S^t only if ab and bc are in S for some b. Okay, in order for 11 to be in S^t that would mean we must have 1b and b1 in S for some b. I see 10 but I see no "b1" for any b! Similarly, in order that 33 be in S^t, we must have 3a and a3 in S for some a. We have 32, but no 23, we have 03 but no 30. In order that 22 be in S^t, we must have 2a and a2 in S for some a. I see 12 but no 21 and I see 20 but no 02.

    Her's how I would do the problem. First, do you see that we can ignore "doubles" like 00? If we also have 0a, "transitivity" tells us we must also have 0a which is obviously in the set. Starting from the left, I see 03. The only pair of the form 3a is 32 so "transitivity" says we must also have 02. Next is 10. The only pair of the form 0a is is 00 so we must have 10 which is already in the set. Next is 12. The only pair of the form 2a is 20 so we must have 10 which is already in the set. Next is 20. The only pair of the form 0a is 00 so we must have 20 which is in the set (again, 00 is a "double"). Finally, we have 32. The only pair in the set of the form 2a is 20 so we must have 30. That is, the transitive closure of S is S union {02, 30}= {00, 03, 10, 12, 20, 32, 02, 30}.
  4. Dec 5, 2006 #3

    Thanks so much! that helps alot, I was drawing pictures and it was just very time consuming and confusing but this is alot easier.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Similar Threads for Binary Relations Transitivity Date
Can someone double-check this simple binary relation proof? Sep 7, 2011
Binary Relations Feb 20, 2011
Sets - Binary Relations Jan 31, 2011
Discrete Math: Binary Relations Dec 16, 2010
Binary relation question Sep 21, 2010