Results 1 to 6 of 6

Math Help - Discrete Math Problem - Relation

  1. #1
    Junior Member
    Joined
    Feb 2007
    Posts
    44

    Discrete Math Problem - Relation

    Hello,

    I am needing some assistance on the problem below. Thank you for your help in advance.


    Let R be a relation on the set N of natural numbers defined by

    R = {(a,b) (element symbol) N x N ׀ a divides b in N }

    Is R a partial order of N? Explain.

    Is N with the divisibility relation given above a totally ordered set? Explain.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by MathStudent1 View Post

    R = {(a,b) (element symbol) N x N ׀ a divides b in N }

    Is R a partial order of N? Explain.
    Yes.

    1)Reflexcise. Note that a|a is a true statement for any "a" in N.

    2)Anti-symmettric. Note if a|b and b|a then a<= b and b<= a. Thus, a=b.

    3)Transitive. Yes, if a|b and b|c then a|c. I leave that to thee to prove.

    Thus, "|" is an ordering relation on this set.
    Is N with the divisibility relation given above a totally ordered set? Explain.
    By definition, "total order" is that all elements are comparable, i.e. the full set is a chain.
    But that is note the case,
    (a,b) = (3,5) in R.
    But 3|5 is not true.
    Thus, it is not a totally ordered set.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2007
    Posts
    44
    Okay, thank you I have been working on the problem and understand it (I believe) except the antisymmetric part. Here is what I have, please tell me if I am right so far:

    Reflexive: so, a <= a always holds.

    For example, 2 <= 2
    3 <= 3
    ...etc.

    Antisymmetric: so, if a <= b and b <= a holds, then a = b

    Don't see this yet? What values to choose to show? Can a and b be the same value?

    Transitive: so, if a <= b and b <= c hold, then a <= c also holds.

    For Example, since 2 <= 3, and
    3 <= 6, then
    2 <= 6

    ** I need to know the antisymmetric part before I can tell if it holds and therefore is a poset.

    To be totally ordered every pair of elements a,b in the set is comparable (a <=b or b <= a). The set of natural numbers is not totally ordered since for example, 3 and 5 are not comparble, neither 3 <= 5 nor 5 <= 3 holds.

    Thank you!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    The relation is indeed antisymmetric.
    If a divides and b divides a then a is b.

    More formally: a|b implies b=ka; b|a implies a=jb.
    So b=ka=kjb or kj=1. But that means k=j=1, b=a.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Feb 2007
    Posts
    44
    So, can I say for example, since 2 ≤ 2 and 2 ≥ 2, it must be true that 2=2? Or, I am wrong with I am choosing a and b to be 2? I am needing an example. I am still stuck. Thanks.
    Last edited by MathStudent1; February 27th 2007 at 02:27 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Feb 2007
    Posts
    44
    I am still spinning my wheels on this one. After thinking about it, I don't think I can prove it by examples like I tried above? Thanks.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: December 10th 2010, 07:35 AM
  2. Discrete Math - Last Problem. Need Help!
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 31st 2009, 11:03 AM
  3. discrete math - equivalence relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 24th 2008, 11:26 AM
  4. Discrete Math Problem! HELP!!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 30th 2008, 11:48 AM
  5. discrete math:functions,recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 18th 2008, 02:49 AM

Search Tags


/mathhelpforum @mathhelpforum