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: More Discrete Math's

  1. Oct 13, 2008 #1
    confused:Given the simple LTE (less then equal) relation on S= {1,2,3,4} defined by [less and equal ], we define a complex NTG (not grater then) relation on S x S by (w,x) NTG (y,z) if w[less and equal) y or x [less and equal z. (this or confusing me )
    Show that NTG is (R) reflexive, but not (T) transitive and not (AS) antisymmetric.

    After I list the pairs: (1,1) (1,2) (1,3) (1,4) (2,1) (2,2), (2,3) (2,4) (3,1) (3,2) (3,3) (3,4)
    (4,1) (4,2) (4,3) (4,4)

    Now I don't know how to start at all. Or may be...

    Reflexive property means that (x,x) is in the realation for any x in S.
    Antisymmetric (AS) (x,y) and (y,x) both in the relation implies that x=y, but I need to show not AS. Does that mean I have to show non-symetric?
    Transitive property means that if (x,y) and (y,z) are in the realation, then (x,z) is also.

    How about if I start with (1,1) NGT (2,1) b/c {1 is < and = to 2}

    I would appreciate any suggestions.
    Thank you again
  2. jcsd
  3. Oct 13, 2008 #2


    Staff: Mentor

    The notation is confusing to me. LTE must mean less than OR equal, because with any two numbers one of them can't be both less than the other AND equal to it.

    For example, 1 LTE 2 and 1 LTE 1, using elements of set S.

    The other relation, for "not greater than" ought to be NGT, not NTG, but that's a minor point.

    According to how NGT is defined above (w, x) NGT (y, z) iff w LTE y OR x LTE z.

    For example (1, 3) NGT (2, 3) since 1 LTE 2. It's also true that 3 LTE 3. You should confirm that GTE is defined with "or" not "and".
    For the reflexive property, you only need to consider (1, 1), (2, 2), (3, 3), and (4, 4), and show that (1, 1) GTE (1, 1) and so on with each of the other three pairs.
    For the antisymmetric property, I think you need to show that if (x, y) GTE (y, x) then it's not true that (y, x) GTE (x, y). Don't do this symbolically; pick values from S and try them out.
    For the transitive property, show that if (x, y) GTE (y, z) and if (y, z) GTE (z, w) then (x, y) GTE (z, w).
  4. Oct 13, 2008 #3


    User Avatar
    Science Advisor

    "LTE" (less than or equal) to is exactly the same as "NGT". (not greater than) (surely not "NTG"!) .
  5. Oct 13, 2008 #4


    Staff: Mentor

    Maybe NTG stands for "not that great"

    Well, you'd think that LTE is exactly the same as NGT, but the NGT relation is defined on pairs in the OP's problem.
  6. Oct 13, 2008 #5
    Thank you so much. I am sorry for the typo NTG instead NGT, but you figured out. The example for OR confusion was very helpful.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook