Results 1 to 8 of 8

Math Help - Partial orders - Question

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    34

    Partial orders - Question

    Good day to all,

    We have just started relations and I came across the following question in my textbook:

    Let X = {1, 2}. List all the partial orders that can be defined on X.

    My solution:

    I began by computing X x X (Cartesian product) which gave me:

    X x X ={(1,1), (1,2), (2,1), (2,2)}

    Since we are looking for partial orders, the relation has to be simultaneously reflexive, antisymmetric and transitive.

    If the relation R on X is reflexive then it must contain (1,1) and (2,2)

    The ordered pairs (1,2) and (2,1) cannot belong to R for if they did and R is also antisymmetric then that would imply 1=2, which is false.

    Therefore I concluded that the list of partial orders is the set:
    {(1,1), (2,2)}

    I was wondering if my logic is flawed and if so what errors have I committed?

    Finally, is it possible in this problem to determine the number of partial orders (cardinality)?

    Any advice would be greatly appreciated.

    Kindest regards
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Would \{(1,1),(1,2),(2,2)\} also work?
    Why or why not?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2009
    Posts
    34
    Thank you Plato for your quick response.

    I am not sure. The definition of antisymmetric states:

    for every a,b in X ((a,b) belongs to R and (b,a) belongs to R implies a=b)

    If (1,2) belongs to R and (2,1) does not belong to R (based on the set you listed) then the hypothesis of the implication is false which means that the implication is true. If this is a valid reasoning could we not say the same for the set: {(1,1), (2,1), (2,2)}

    Slightly confused!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    But (2,1)\notin\{(1,1),(1,2),(2,2)\}. Is it?
    Antisymmetric says that in both (a,b)\in R~\&~(b,a)\in R then it must be true that a=b.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2009
    Posts
    34
    There is something that I am obviously not understanding. (2,1) does not belong to the set you listed.

    I believe the set is antisymmetric, since for it not to be antisymmetric we would have to have: and a different than b. Therefore the set you provided is a partial order as well (reflexive, transitive and antisymmetric).

    I apologize as I realize this may be obvious to many.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by gate13 View Post
    I believe the set is antisymmetric, since for it not to be antisymmetric we would have to have: and a different than b. Therefore the set you provided is a partial order as well (reflexive, transitive and antisymmetric).
    That is correct. And there is one more p.o. on the set.
    What is it?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Oct 2009
    Posts
    34
    I believe the other partial order would be :

    {(1,1), (2,1), (2,2)} for the same reasons listed previously.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Oct 2009
    Posts
    34
    I just wanted to thank you Plato for your time and explanations. Many thanks.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Partial Orders
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 6th 2010, 09:33 AM
  2. Partial orders
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 6th 2010, 12:34 AM
  3. Partial Orders
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 15th 2009, 03:20 PM
  4. Partial Orders
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 2nd 2009, 08:28 PM
  5. Partial orders
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: January 19th 2009, 10:58 AM

Search Tags


/mathhelpforum @mathhelpforum