5
$\begingroup$
  • A binary relation is a preorder if it is reflexive and transitive.
  • A binary relation is a partial order if it is reflexive, transitive and antisymmetric.

Does that mean that all binary relations that are a preorder are also automatically a partial order as well?

In other words is a binary relation a preorder if its only reflexive and transitive and nothing else?

Thanks for your help.

$\endgroup$
1
  • 3
    $\begingroup$ A partial order is a preorder that is also antysymmetric. $\endgroup$
    – BrianO
    Oct 30, 2016 at 23:24

3 Answers 3

7
$\begingroup$

You have it backwards - every partial order is a preorder, but there are preorders that are not partial orders (any non-antisymmetric preorder).

For example, the relation $\{(a,a), (a, b),(b,a), (b,b)\}$ is a preorder on $\{a, b\}$, but is not a partial order.

$\endgroup$
4
  • $\begingroup$ Ah yes, my bad! Thank you. Another thing- what if I have a binary relation that is reflexive, transitive and symmetric. Would this binary relation be considered a preorder? $\endgroup$
    – Jack O
    Oct 30, 2016 at 23:08
  • $\begingroup$ @MarkJ Yes, that would be a preorder. Saying that every preorder is reflexive and transitive does not mean that those are the only properties that a preorder can have. $\endgroup$ Oct 30, 2016 at 23:11
  • $\begingroup$ This is exactly what I was looking for. Thank you for your help! $\endgroup$
    – Jack O
    Oct 30, 2016 at 23:13
  • $\begingroup$ @MarkJ It seems you are satisfied with the answer and further comments. Then why didn't you accept the answer? It's just a click to acknowledge the time that Noah Schweber took to clarify your confusion :) $\endgroup$
    – amrsa
    Oct 31, 2016 at 9:55
3
$\begingroup$

order relations are subset of pre order relations. For instance a relation kind of "prefer or indiferent" is reflexive and transitive, but is not antisymetric, so this is an example of pre order but not order. A relation like "bigger or equal" is reflexive, transitive and also antisymetric, so this relation is pre order (since it is reflexive and transitive) but also order.

$\endgroup$
3
$\begingroup$

A pre-order $a\lesssim b$ is a binary relation, on a set $S,$ that is reflexive and transitive. That is $\lesssim $ satisfies (i) $\lesssim $ is reflexive, i.e., $a\lesssim a$ for all and (ii) $\lesssim $ is transitive, i.e., $a\lesssim b$ and $b\lesssim c$ implies $a\lesssim c,$ for all $% a,b,c\in S.$ (A pre-ordered set may have some other properties, but these are the main requirements.)

On the other hand a partial order $a\leq b$ is a binary relation on a set $S$ that demands $S$ to have three properties: (i) $\leq $ is reflexive, i.e., $% a\leq a$ for all $a\in S$, (ii) $\leq $ is transitive, i.e., $a\leq b$ and $% b\leq c$ implies $a\leq c,$ for all $a,b,c\in S$ and (iii) $\leq $ is antisymmetric, i.e., $a\leq b$ and $b\leq a$ implies $a=b$ for all $a,b\in S$% .

So, as the definitions go, a partial order is a pre-order with an extra condition. This extra condition is not cosmetic, it is a distinguishing property. To see this let's take a simple example. Let's note that $a$ divides $b$ (or $a|b)$ is a binary relation on the set $Z\backslash \{0\}$ of nonzero integers. Here, of course, $a|b$ $\Leftrightarrow $ there is a $% c\in Z$ such that $b=ac.$

Now let's check: (i) $a|a$ for all $a\in Z\backslash \{0\}$ and (ii) $a|b$ and $b|c$ we have $a|c.$ So $a|b$ is a pre-order on $Z\backslash \{0\},$ but it's not a partial order. For, in $Z\backslash \{0\},$ $a|b$ and $b|a$ can only give you the conclusion that $a=\pm b,$ which is obviously not the same as $a=b.$

The above example shows the problem with the pre-ordered set $<S$,$\lesssim >.$ It can allow $a\lesssim b$ and $b\lesssim a$ with a straight face, without giving you the equality. Now a pre-order cannot be made into a partial order on a set $<S$, $\lesssim >$ unless it is a partial order, but it can induce a partial order on a modified form of $S.$ Here's how. Take the bull by the horn and define a relation $\sim ,$ on $<S,\lesssim >$ by saying that $a\sim b$ $\Leftrightarrow a\lesssim b$ and $b\lesssim a$. It is easy to see that $\sim $ is an equivalence relation. Now splitting $S$ into the set of classes $\{[a]|$ $a\in S\}$ where $[a]=\{x\in S|$ $x\sim a\}.$ This modified form of $S$ is often represented by $S/\sim .$ Now of course $% [a]\leq \lbrack b]$ if $a\lesssim b$ but it is not the case that $b\lesssim a.$ Setting $[a]=[b]$ if $a\sim b$ (i.e. if $a\lesssim $ and $b\lesssim a).$

In the example of $Z\backslash \{0\}$ we have $Z\backslash \{0\}/\sim $ $% =\{|a|$ $|$ $a\in Z\backslash \{0\}\}.$

(Oh and as a parting note an equivalence relation is a pre-order too, with the extra requirement that $a\lesssim b$ implies $b\lesssim a.)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.