Results 1 to 10 of 10

Math Help - Question about partially ordered sets

  1. #1
    Member
    Joined
    May 2008
    Posts
    87

    Question about partially ordered sets

    Is (S, R) a poset if S is the set of all people in the world and (a, b) \in R, where a and b are people if a = b or a is an ancestor of b?

    I know that I have to determine if this is reflexive, antisymmetric and transitive.

    So I start with reflexivity and imagine that I have two people, I can either pick two people who are identical (a = b) or I can pick a person a who is an ancestor of a person b.

    If I pick two who are identical then it is trivially reflexive, but if I choose a person a who is an ancestor of b, then it is not reflexive, as obviously a cannot be ancestor of him or herself.

    Thus it is not reflexive and is not a poset either.

    Yet, I see that in the solution for this problem that it is indeed reflexive, how is that possible?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by posix_memalign View Post
    Is (S, R) a poset if S is the set of all people in the world and (a, b) \in R, where a and b are people if a = b or a is an ancestor of b?
    Yet, I see that in the solution for this problem that it is indeed reflexive, how is that possible?
    Read the definition again.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2008
    Posts
    87
    Quote Originally Posted by Plato View Post
    Read the definition again.
    I did but I think I fail to understand something really fundamental; is it sufficient that only some of the people maintain the a = b property for R to be reflexive? If not, how does the definition ensure that they are all equal when the very same definition states that they might not be (i.e. because of the 'or')?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by posix_memalign View Post
    I did but I think I fail to understand something really fundamental; is it sufficient that only some of the people maintain the a = b property for R to be reflexive? If not, how does the definition ensure that they are all equal when the very same definition states that they might not be (i.e. because of the 'or')?
    Reflexive simply means that each element is the set is related to itself. For each a in the set the pair (a,a) is in the relation. That is laid in the very definition of this particular relation.

    Equality is the very basic and simple reflexive relation.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Let 'Rab' stand for '<a b> in R'.

    Let 'Cab' stand for 'a is an ancestor of b'.

    The problem, as you stated it, is a bit deceptive.

    Ordinarily, we would think we are given:

    (1) Rab if and only if (a=b or Cab)

    But the problem, as you stated it, actually gives only:

    (2) If a=b or Cab, then Rab.

    Now we have to check:

    Reflexive: Is it the case that, for any a, we have Raa?

    For (1) or (2) it's easy.

    Antisymmetric: Is it the case that, for any a and b, we have 'if Rab and Rba, then a=b'?

    With (1) it's easy. But with (2) we get a different answer.

    Transitive: Is it the case that, for any a, b, and c, we have 'Rab and Rbc, then Rac'?

    With (1) it's easy. But with (2) we get a different answer.
    Last edited by MoeBlee; April 6th 2011 at 12:33 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by Plato View Post
    Read the definition again.
    To be precise, as the problem is stated, no definition was given. A definition would be a biconditional, but the statement of the problem gives only a conditional. It is not clear that a biconditional was what was actually intended.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by MoeBlee View Post
    To be precise, as the problem is stated, no definition was given. A definition would be a biconditional, but the statement of the problem gives only a conditional. It is not clear that a biconditional was what was actually intended.
    I totally disagree with that.
    The relation was clearly defined in the OP.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    The wording given was:

    <a b> in R IF a=b or a is an ancestor of b.

    That is, (a=b or a is an ancestor of b) -> <a b> in R.

    The wording was not given as:

    <a b> in R if AND ONLY IF a=b or a is an ancestor of b.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    May 2008
    Posts
    87
    Quote Originally Posted by Plato View Post
    Reflexive simply means that each element is the set is related to itself. For each a in the set the pair (a,a) is in the relation. That is laid in the very definition of this particular relation.

    Equality is the very basic and simple reflexive relation.
    Ah, I see ... however, I thought I finally understood this but even when it means that a and b should only be related, I still don't see how this can be true.
    There are two cases, if a = a, then they are obviously related, no problem.
    But the case a = a does not necessarily hold for every element in the set? For at least some of them there is the possibility that a is the ancestor of b, and for this particular a, how does the reflexive property hold? Doesn't it have to hold for every element in the set?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by posix_memalign View Post
    But the case a = a does not necessarily hold for every element in the set? For at least some of them there is the possibility that a is the ancestor of b, and for this particular a, how does the reflexive property hold? Doesn't it have to hold for every element in the set?
    You're mixed up about the tests for the relation.

    Go back to the precise tests (here, a, b, and c are assumed to be people):

    Reflexive: Is it true that, for any a, we have Raa?

    That is, is every person either him(her)self or an ancestor of him(her)self?

    Antisymmetric: Is it true that, for any a and b, we have 'if Rab and Rba, then a=b'?

    That is, is it true that if either a and b are ancestors of each other or a and b are the same person, then a and b are the same person?

    Transitive: Is it the true that, for any a, b, and c, we have 'Rab and Rbc, then Rac'?

    That is, it true that if a, b, and c are the same person or a is an ancestor of b is an ancestor of c then either a and c are the same person or a is an ancestor of c?

    That's all there is to it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Q's on Partially Ordered Set
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 5th 2011, 01:17 AM
  2. Partially ordered set with no maximal element
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 9th 2010, 12:37 AM
  3. Replies: 7
    Last Post: February 25th 2010, 04:44 AM
  4. Partially Ordered Set, example from Wiki.
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: January 18th 2010, 07:58 PM
  5. Partially ordered set.
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: January 10th 2010, 08:42 AM

Search Tags


/mathhelpforum @mathhelpforum