Proving R is a pertial order Set.

[raf1qu3]

Ok, here is my problem. i had this problem in my Logic test last week and i felt clueless. i don't know why but I am 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?

 

[Hurkyl]

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.

 

[raf1qu3]

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.

well for 7 marks out 30 it wouldn't be so simple. i tried drawing a digraph but how would that help?

 

[JSuarez]

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 $$\forall x \in X \left(xRx\right)$$, but:

$$xRx \Leftrightarrow 3|x + 2x \Leftrightarrow 3|3x$$

Which is clearly true.

For antisymmetry, you must prove that:

$$\forall xy \left(xRy\wedge yRx \Rightarrow x = y\right)$$

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

I'll leave the transitivity to you.

 

[raf1qu3]

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.

JESUS.. i can't 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.