Results 1 to 7 of 7

Math Help - Partial Order Relations

  1. #1
    Junior Member
    Joined
    Nov 2006
    Posts
    59

    Partial Order Relations

    Let R be a relation on  \bold{N}^2 defined by  (x,y)R(u,v) if and only if  x \leq u or  y \leq v . Is R a partial order? Prove your answer.

    This is what I came up with so far.

    So, just to be courteous to the people who read this, a relation on a set is called a partial ordering if the relation is reflexive, antisymmetric, and transitive.

    Therefore, I tried to prove that R is reflexive, antisymmetric, and transitive.

    Here's what I did.

    Claim: R is a partial order.

    Proof: For R to be a partial order, it must be reflexive, antisymmetric, and transitive.
    In order to show R is reflexive, let (x,y) \in \bold{N}^2 . Notice that  x \leq x . Therefore,  (x,y)R(x,y) , and hence, R is reflexive.
    In order to show R is antisymmetric, let (x,y) \in \bold{N}^2 and  (u,v) \in \bold{N}^2. Assume (x,y)R(u,v) and  (u,v)R(x,y) . Therefore,  x \leq u or  y \leq v , and  u \leq x or  v \leq y .

    After this point, I am not sure how to continue. I am thinking that I would have to break this into cases, but I'm not sure how to break it into cases because I have two different statements that both involve "or". It's looking like the transitive proof will also have cases, but I'm not sure how to attempt those either. If I can clear up the antisymmetric one, the transitive one can probably follow pretty easily. I will post a continuation after I get some hints on how to go about continuing. Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1
    Are both of these true?
    \left( {1,2} \right)R\left( {2,1} \right)\quad \& \quad \left( {2,1} \right)R\left( {1,2} \right)<br />
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2006
    Posts
    59
    Yes they are, because...

    In the first statement, the first elements in the ordered pairs work.  1 \leq 2 . In the second case, the second elements work.  1 \leq 2 . I guess I'm still not seeing how that's going to help me prove this :-(. (we just started relations, so i'm having trouble getting used to the idea right now).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1
    Is R antisymmetric?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2006
    Posts
    59
    Oh, let's see.

    I'll show you what i'm thinking. Critique it and/or confirm it.

    Here you go. (i'll put comments in blue.)

    So, your example was. Consider the ordered pairs  (x,y) = (1,2) and  (u,v) = (2,1) in  \bold{N}^2 .So for R to be antisymmetric, if x ~ y and y ~ x, then x = y. So, for a counterexample, we find x and y such that the hypothesis is true and the conclusion is false. Notice that x = 1 < 2 = u; therefore, (1,2)R(2,1). Also, notice that v = 1 \leq 2 = y ; therefore, (2,1)R(1,2). Since 1  \not= 2 and  2 \not= 1 ,  (1,2) \not= (2, 1) . Thus, R is not antisymmetric, and hence, R is not a partial order.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1
    By George, you have.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Nov 2006
    Posts
    59
    Ha, thanks a lot.

    Disproofs are so much easier than proofs most of the time.

    Thanks a lot man. I'll click the thanks button.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Second order recurrence relations
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 15th 2011, 04:01 AM
  2. Order Relations and Predecessors
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 14th 2010, 10:45 PM
  3. Order relations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 13th 2010, 02:00 PM
  4. Special Relations and Partial Orders help
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: January 7th 2009, 09:39 AM
  5. Equivalence Relations and Partial Orderings
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2007, 10:13 PM

Search Tags


/mathhelpforum @mathhelpforum