1. Welcome! Please take a few seconds to create your free account to post threads, make some friends, remove a few ads while surfing and much more. ClutchFans has been bringing fans together to talk Houston Sports since 1996. Join us!

[Math] Discrete Structures problem

Discussion in 'BBS Hangout' started by Xerobull, Apr 25, 2012.

  1. Xerobull

    Xerobull ...and I'm all out of bubblegum

    Joined:
    Jun 18, 2003
    Messages:
    37,174
    Likes Received:
    36,129
    If any of you math gurus could help, I would appreciate it. Reps for all answers.

    I think I have this, but something tells me that I may be off.

    R= {(a,a),(b,a),(b,b),(c,b),(c,c)}​

    Is this Transitive? I think no, since you need (a,b),(b,c) and (a,c). In this case, the (a,b) is (c,b) and the (b,c) is (b,a), but there is no (a,c).

    However, in reading some other problems like this, you don't always need (a,b),(b,c) and (a,c)....for example:

    R= {(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)}​

    According to my answer key, this IS Transitive, since (1,2) and (2,1) AND (1,1) and (2,2) are in the relation.

    So this confuses me and makes the answer to my original question not so cut-and-dry.

    So am I over thinking the original question? Thanks.
     
    #1 Xerobull, Apr 25, 2012
    Last edited: Apr 25, 2012
  2. jEXCLUSIVE

    jEXCLUSIVE Member

    Joined:
    Jan 27, 2009
    Messages:
    351
    Likes Received:
    24
    The answer is 11.
     
    1 person likes this.
  3. Xerobull

    Xerobull ...and I'm all out of bubblegum

    Joined:
    Jun 18, 2003
    Messages:
    37,174
    Likes Received:
    36,129
    Funnee. Still, repped.

    I stumped 3 tutors with this one, so no shame in not knowing it. :)
     
  4. moonsh0t

    moonsh0t Member

    Joined:
    Oct 11, 2007
    Messages:
    1,530
    Likes Received:
    317
    I am smarter than you thread in disguise.

    [​IMG]
     
    1 person likes this.
  5. fadeaway

    fadeaway Member

    Joined:
    Apr 25, 2000
    Messages:
    14,706
    Likes Received:
    1,193
    A discrete question deserves a discreet answer, so I will refrain from offering my controversial opinion on this problem, and simply suggest that both of your ideas have merit.

    However, since this problem might potentially involve a transitive element, it certainly deserves a tranny type of answer, so I will suggest that the answer in this case could go both ways, and may not be what it seems.

    I hope you find my input valuable.
     
    1 person likes this.
  6. RedRedemption

    RedRedemption Member

    Joined:
    Jul 21, 2009
    Messages:
    32,542
    Likes Received:
    7,752
    What level of math is this? :eek:
     
  7. hairyme

    hairyme Member

    Joined:
    Jan 22, 2011
    Messages:
    691
    Likes Received:
    93
    ^^ Level 12, Wizard.

    I've done math through grad school, but I don't like this recent trend of math-threads... I don't come here to think! Now, I could have answered the Riemann zeta question a couple years ago, but this one, ehhh, I'm not sure I ever knew the answer.

    Good luck.
     
    1 person likes this.
  8. Xerobull

    Xerobull ...and I'm all out of bubblegum

    Joined:
    Jun 18, 2003
    Messages:
    37,174
    Likes Received:
    36,129
    Discrete Math is....it's a requirement for a Computer Science degree. I guess you could call it programming math, or math that's good for designing networks. They suggest that you take it in your senior year of college, after all of the other math requirements are done.

    I don't pretend to be good at it, but it's kind of fun, like doing puzzles.
     
  9. pirc1

    pirc1 Member

    Joined:
    Dec 9, 2002
    Messages:
    14,138
    Likes Received:
    1,882
    Have touched this stuff for well over a decade, so I cannot help. :grin:
     
    1 person likes this.
  10. tamericus

    tamericus Member

    Joined:
    Oct 30, 2008
    Messages:
    3,247
    Likes Received:
    894
    For transitivity, (a must be related to b) and (b must be related to a) for all a,b in the set.

    In your example that showed transitivity, you can see it holds true for all of the equal relations. (1 is related to 1) and (1 is related to 1)[transitivity!] (2 is relat....) etc.
    You also see the remaining relations (1 is related to 2), and (2 is related to 1) are also transitive so you can conclude transitivity.

    In your initial example (a,a),(b,a),(b,b),(c,b),(c,c) you see that (b is related to a) but you don't have (a is related to b). The same goes for (c,b) but you need only one not hold for it not to be transitive. Hopefully I helped a little bit.
     
  11. tamericus

    tamericus Member

    Joined:
    Oct 30, 2008
    Messages:
    3,247
    Likes Received:
    894
    Please someone let me know if this is incorrect btw, I haven't touched discrete math in a long time!
     
  12. tamericus

    tamericus Member

    Joined:
    Oct 30, 2008
    Messages:
    3,247
    Likes Received:
    894
    And my coworker just politely informed me I just described a symmetric relation. Don't listen to me! I'll let him try to explain it.

    Transitivity is similar to symmetry, however aRb and bRc -> aRc.

    (1,1), (1,1) -> (1,1) :contained in the set.
    (1,2), (2,1) -> (1,1) :contained in the set.
    (2,1), (1,2) -> (2,2) :contained in the set.

    Therefore, transitive.

    Similarly,

    (a,a), (a,a) -> (a,a)
    (a,a), (b,a) -> (a,a)
    (b,a), (a,a) -> (b,a)
    (b,a), (b,a) -> (b,a)

    (c,c), (c,c) -> (c,c)
    (c,c), (c,b) -> (c,b)
    (c,b), (c,c) -> (c,c)
    (c,b), (c,b) -> (c,b)

    All are contained in the set, therefore also transitive.
     
    1 person likes this.
  13. Xerobull

    Xerobull ...and I'm all out of bubblegum

    Joined:
    Jun 18, 2003
    Messages:
    37,174
    Likes Received:
    36,129
    Awesome...ok, ok. Are you saying that R= {(a,a),(b,a),(b,b),(c,b),(c,c)} is transitive due to this? Just double checking....I've been trying to find this for about 8 hours.

    (I've also proved that it's reflexive and antisymmetric. If it's also transitive, then it's a partially ordered set)
     
  14. tamericus

    tamericus Member

    Joined:
    Oct 30, 2008
    Messages:
    3,247
    Likes Received:
    894
    He missed one piece! (c,b) and (b,a) => (c,a) not in the set so NOT transitive.
    Final answer! Took a group of programmers to come up with that, that's pretty sad.
     
  15. Xerobull

    Xerobull ...and I'm all out of bubblegum

    Joined:
    Jun 18, 2003
    Messages:
    37,174
    Likes Received:
    36,129
    Ok I thought as much. Thanks for reinforcing what I worked! If you look at the second example in my first post, there is no a,c...not sure how that works.
     
  16. tamericus

    tamericus Member

    Joined:
    Oct 30, 2008
    Messages:
    3,247
    Likes Received:
    894
    Why do you say there is no (a,c)?

    (a,b), (b,c) -> (a,c)
    (1,1), (1,1) -> (1,1) :contained in the set.
    (1,2), (2,1) -> (1,1) :contained in the set.
    (2,1), (1,2) -> (2,2) :contained in the set.
     
  17. wreck

    wreck Member

    Joined:
    Jul 18, 2006
    Messages:
    3,551
    Likes Received:
    47
    Single biggest reason why I didnt pursue Computer science.
     
    1 person likes this.
  18. Xerobull

    Xerobull ...and I'm all out of bubblegum

    Joined:
    Jun 18, 2003
    Messages:
    37,174
    Likes Received:
    36,129
    I guess I don't understand this part, then. Why would 11 or 22 be AC?
     
  19. Qball

    Qball Member

    Joined:
    Nov 9, 2001
    Messages:
    4,151
    Likes Received:
    210
    Because.....seven ate nine!!
     
    1 person likes this.
  20. tallanvor

    tallanvor Member

    Joined:
    Oct 9, 2007
    Messages:
    18,766
    Likes Received:
    11,925
    as tamericus already explained, not transtitive

    R= {(a,a),(b,a),(b,b),(c,b),(c,c)}

    you have (c,b) and (b,a) therefore you would need (c,a) to be transitive.
     

Share This Page