0
$\begingroup$

enter image description here

Preparing for exams, and came across this past year question. Any ideas?

I know that for partial order, it must be reflexive, transitive and anti-symmetric, but how exactly do i show this?

$\endgroup$
9
  • 2
    $\begingroup$ Next step is to recall what those terms actually mean. Can you show at least some of them? (one of them should be completely trivial). $\endgroup$ Oct 26, 2015 at 11:37
  • $\begingroup$ reflexive means a<=a so in this case, since x=y, we can say that the relation is reflexive, coz x=y is effectively saying a<=a $\endgroup$
    – Azza
    Oct 26, 2015 at 11:38
  • 2
    $\begingroup$ Great (though you would probably want to phrase it a bit more precisely on a test). What about the other two? $\endgroup$ Oct 26, 2015 at 11:40
  • $\begingroup$ is it antisymmetric for the same reason. So anti-symm means, if a<=b and b<=a, then a=b. So if x<=y, and y<=x, x=y (which is what we were told) $\endgroup$
    – Azza
    Oct 26, 2015 at 11:42
  • 2
    $\begingroup$ Not quite. $x\leq y$ might be because $x=y$ but it could also be because $3x\leq y$, so you need to account for this. $\endgroup$ Oct 26, 2015 at 11:43

1 Answer 1

2
$\begingroup$
  • reflexive: You've done it.

  • anti-symmetric: let's see what happens if $x \preceq y$, $y \preceq x$, but $x\neq y$ : we have $3x \le y$ and $3y \le x$, so $9x \le x$, so $x=y=0$, impossible

  • transitive: if $x \preceq y$ and $y \preceq z$, and x!=y and y!=z (otherwise the relation is trivial), then $3x \le y$ and $3y \le z$ so $(3x \le) 9x \le z$ , $3x \le z$ so $x \preceq z$

$\endgroup$
2
  • $\begingroup$ Hey @Baconaro thanks heaps! Just a bit confused as to how you got the x=y=0 bit for anti-sym $\endgroup$
    – Azza
    Oct 26, 2015 at 12:22
  • $\begingroup$ @Azza you have $9x \le x$ so $x=0$ and $3y \le x$ $\endgroup$
    – Baconaro
    Oct 26, 2015 at 12:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .