Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving R is a pertial order Set.

  1. Jan 10, 2010 #1
    Ok, here is my problem. i had this problem in my Logic test last week and i felt clueless. i dont know why but im still trying to figure it out.

    here it is.

    The relation R is defined on the set X= {0,1,2,..5} by the rule xRy if and only if x+2y is divisible by 3. Prove that R is a partial order relation.

    i did this sort of stuff in my first yr with my eyes closed but when this came up in this years class test i was dumb founded. I have had a look at my revision notes from year 1 but they didnt help.

    how would you guys prove this?
  2. jcsd
  3. Jan 10, 2010 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, X only has 6 elements -- and there are only 36 pairs. It seems that (what seems to me to be) most obvious, direct thing to do -- try and draw the partial ordering -- is feasible.
  4. Jan 10, 2010 #3
    well for 7 marks out 30 it wouldnt be so simple. i tried drawing a digraph but how would that help?
  5. Jan 10, 2010 #4
    What is a partial order? It's a binary relation that it's reflexive, antisymmetric and transitive, therefore you must prove that R has this properties.

    For example, why is it reflexive? To be reflexive, you must prove that [tex]\forall x \in X \left(xRx\right)[/tex], but:

    [tex] xRx \Leftrightarrow 3|x + 2x \Leftrightarrow 3|3x [/tex]

    Which is clearly true.

    For antisymmetry, you must prove that:

    [tex]\forall xy \left(xRy\wedge yRx \Rightarrow x = y\right) [/tex]

    But if 3|x + 2y and 3|y + 2x and this, I believe must be done by checking all pairs (x,y) such that [tex]x\neq y[/tex].

    I'll leave the transitivity to you.
  6. Jan 10, 2010 #5
    JESUS.. i cant believe i missed that... i must have had partial order mixed up with something else... thanks bud... will remember this for my end of semester exam...
    this shows you must always revise the basics before you can advance, thanks again.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook