Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Question on Relation

  1. Oct 3, 2004 #1
    My lecturer asked our class to construct all transitive relations on A={1,2,3}. Is there a brilliant way to do this? Because number of subsets is too big for us to list out one by one. Thanks.
  2. jcsd
  3. Oct 3, 2004 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    The number of subsets if {1,2,3} is 8. That is not too many to list.
  4. Oct 3, 2004 #3
    Yes, but the total number of relations on {1,2,3} is 64. Surely you find checking 64 relations a time-consuming task.
  5. Oct 3, 2004 #4
    sorry, should be the number of relations.
    Last edited: Oct 3, 2004
  6. Oct 3, 2004 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    since there are only three elements it is still doable since we only care about transitive ones, and we can exploit symmetry.

    suppose 1 is not related to any of 1,2,3, then we need only classify those trans relations on 2,3

    then suppose 1R2, and doesn't relate to 3.

    then suppose 1R2 and 1R3

    now i could have picked anything apart from 1, so acutally by symmetry you've got them all.
  7. Oct 3, 2004 #6


    User Avatar
    Science Advisor
    Homework Helper

    There's more than 64,. Relations are exactly the subsets of the cartesian cross product AXA, which has 9 members, so 2^9=512 subsets.

    Matt's suggestion of using symmetry is the way to go. It shouldn't be too time consuming wth only 3 elements.
  8. Oct 4, 2004 #7
    Thanks for the suggestion. I'm having problem understanding this transitive relation.

    Here are some examples in my lecture notes:

    Let A={1,2,3}. Let


    Given the above relations, then
    R is symmetric and transitive
    S is reflexive and transitive
    T is reflexive and symmetric

    I know how to see symmetric and reflexive. But I don't know how to figure out which one is transitive. Why T is not transitive? It has all the elements of R, but it is not transitive as R is. My lecturer told us that because (1,2),(2,1) in T are not transitive? Can somebody please explain it to me. I am new to this relation topic. Thanks a thousand.
  9. Oct 4, 2004 #8
    Well T is not transitive but i don't really understand ur lecturer's clarification ...

    Why is T not transitive?
    we have (1,2) in the set
    we also have (2,3) in the set
    but do we have (1,3) ??

    -- AI
  10. Oct 4, 2004 #9
    Thanks Tenali again.
  11. Oct 4, 2004 #10
    Here are the transitive relations I got:




    {(1,1),(2,2),(3,3)},{(1,2)},{(1,3)},{(2,1)},{(2,3)},{(3,1)},{(3,2)},{ }

    Altogether I found 35 transitive relations. Is there anymore? I heard the total number is 171, is it?
    Last edited: Oct 5, 2004
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook