7
$\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
  • 6
    $\begingroup$ A partial order is a preorder that is also antysymmetric. $\endgroup$
    – BrianO
    Oct 30, 2016 at 23:24

3 Answers 3

12
$\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$
8
  • $\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
  • 1
    $\begingroup$ @Rptx Yes, and that is satisfied by the relation in my answer. Again, the relation in my answer is the total relation on $\{a,b\}$, holding between every pair of elements; that's as transitive as it's possible to be! $\endgroup$ May 29, 2023 at 15:25
8
$\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$
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$

You must log in to answer this question.

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