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!

Binary Relations

  1. Nov 8, 2009 #1
    1. The problem statement, all variables and given/known data
    T is a binary relation defined on A = {0, 1, 2, 3}.

    Let T = {(0,2), (1,0), (2,3), (3,1)}

    Find T^t, the transitive closure of T.


    3. The attempt at a solution
    I'm gonna skip using commas cause it takes to long

    02 23 = 03
    31 10 = 30
    23 31 = 21
    10 02 = 12
    12 23 = 13
    02 21 = 01
    23 30 = 20
    31 12 = 32

    So, T^t = {(0,2), (1,0), (2,3), (3,1), (0,3), (3,0), (2,1), (1,2), (1,3), (0,1), (2,0), (3,2)}

    Pretty sure this is right, if someone could let me know if I did anything wrong, I'd appreciate it.
     
  2. jcsd
  3. Nov 8, 2009 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi hansel13! :smile:

    (try using the X2 tag just above the Reply box :wink:)
    You've made it really long.

    Hint: how many pairs are there in A? And how many are there in Tt? :wink:
     
  4. Nov 8, 2009 #3
    4 pairs in A. So 8 in Tt? I still fail to follow...
     
  5. Nov 8, 2009 #4

    lanedance

    User Avatar
    Homework Helper

    i dont totally understand the question, but looking at your equivalence realtion, along with Tiny Tim's comments:

    first, there's more than 4 pairs that can be made from A, & more than 8 in T^t

    Let T = {(0,2), (1,0), (2,3), (3,1)}
    then the way i read it, following through T gives: 0~2~3~1, so everything is equivalant in the transitive closure (ie contains all binary pairs)...?
     
  6. Nov 9, 2009 #5

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    uhh? you found 12 in Tt.

    And A has 4 elements, so how many different pairs of elements are there (counting, for example, {0,3} and {3,0} as the same pair).

    (if you can't calculate it, then just list them :wink:)
     
  7. Nov 10, 2009 #6
    Sorry, meant 12 elements in Tt

    I still don't follow. Why would {0,3} and {3,0} be the same?

    OK By defintion:
    The transitive closure of T is the binary relation Tt on A that satisfies the following three properties:
    1. Tt is transitive.
    2. T is a subset of Tt.
    3. If S is any other transitive relation that contains T, then Tt is a subset of S.

    So doesn't T^t = {(0,2), (1,0), (2,3), (3,1), (0,3), (3,0), (2,1), (1,2), (1,3), (0,1), (2,0), (3,2)}?
     
  8. Nov 10, 2009 #7

    lanedance

    User Avatar
    Homework Helper

    if T is a symmetric binary relation then it satisfies
    a~b iff b~a
    so in that case (0,3) = (3,0)
     
  9. Nov 10, 2009 #8

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    What about (0,0), (1,1), (2,2) and (3,3)? :wink:

    (remember, a relation can be something like "=")
    Sorry, I shouldn't have added that …

    when you didn't answer my original question, I got confused and thought this was defined as a symmetric relation (which it wasn't).

    Let's start again …

    How many elements are there in Tt? And how many in A x A? :smile:
     
  10. Nov 10, 2009 #9
    Well I thought there are 12 elements in Tt. And 16 in A x A.

    But I guess if we add (0,0),(1,1),(2,2),(3,3) then Tt would have 16 elements as well?
     
  11. Nov 12, 2009 #10
    So there are 16 elements in Tt?
     
  12. Nov 12, 2009 #11

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Yup! :biggrin:

    So Tt is the whole of AxA …

    now can you see a way of proving that, quicker than just listing all the elements? :wink:
     
  13. Nov 13, 2009 #12
    I guess since there's 4 pairs in T^t and 4 pairs in A, we'd need 16 pairs to have full closure.

    thanks
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Binary Relations
  1. Binary Relations (Replies: 2)

Loading...