4
$\begingroup$

Given a set $\{a,b,c,d\}$, does the set of relations $\{a\leq b, b\leq c,c\leq d,d\leq a\}$ give rise to a preorder? If so, what does a preorder have to do with the notion of ordering if $a$ can be less than $b$, $b$ less than $a$, and $a\neq b$?

$\endgroup$
  • 1
    $\begingroup$ It's called a preorder because it's not quite good enough to be an order $\endgroup$ – Alessandro Codenotti Nov 26 '20 at 8:13
  • $\begingroup$ ...but it still retains some resemblence of partial orders. $\endgroup$ – Alex S Nov 26 '20 at 8:28
3
$\begingroup$

The “pre-” here is to suggest that this concept is somewhat order-ish, but is missing some of the properties that one would want an order to satisfy. It's more order-like than a relation, but not as order-like as a total order, or even a partial order.

What properties would one like a relation to satisfy to be considered an order? The prototypical example is numeric $<$:

  1. Given any two elements $a$ and $b$, exactly one of $a<b$, $a=b$, and $b<a$ is true.
  2. If $a<b$ and $b<c$, then $a<c$.

When this happens we have a "total order".

But sometimes it's useful to consider a more general idea, a "partial order". In a partial order, we still have property (2), but property (1) becomes weaker:

  1. Given any two elements $a$ and $b$, at most one of $a<b$, $a=b$, and $b<a$ is true.

There is less that you can say about partial orders, but there are more examples. One typical example: suppose you have a set of tasks. Some tasks are prerequisites for others. Write $a<b$ if task $a$ must be finished before task $b$ is begun. It might happen that $a$ and $b$ are independent: they can be done in either order, or at the same time. Then none of $a<b$, $a=b$, $a>b$ is true.

Sometimes it's useful to consider a "preorder", which is even more general. Property (1) disappears completely. But we still have property (2). Again, there is less that you can say about preorders, but there are more examples. One typical example is a communications network with one-way communications links. Write $a<b$ if entity $b$ can send messages to entity $a$. We might have both $a<b$ and $b<a$, or neither. But if $a<b$ and $b<c$ then $a<c$ because $c$ can ask $b$ to relay a message to $a$.

If we have both $a<b$ and $b<a$ then that simply means that $a$ and $b$ have two-way communication.

$\endgroup$
3
$\begingroup$

A preorder is like a mix of a partial order and an equivalence relation. The transitive closure of your relations is a preorder in which every pair of objects is equivalent (equivalent means $a \le b$ and $b \le a$ - you can check that this is always an equivalence relation for any preorder), so they're all "the same" as far as the preorder is concerned. In other words, a preorder allows "ties."

The sense in which a preorder is "pre" a partial order is that every preorder gives rise canonically to a partial order obtained by identifying equivalent objects. Formally this is the left adjoint of the inclusion of partial orders into preorders.

It's a lot like considering topological spaces that are not $T_0$, and in fact the two can be related precisely using the notion of the specialization preorder of a topological space, which gives an equivalence between finite topological spaces and finite preorders restricting to an equivalence between finite $T_0$ spaces and finite partial orders.

$\endgroup$
  • $\begingroup$ I changed accepted answers because I thought the other answer was more clear. You did mention some interesting ideas though (which I do not completely understand). $\endgroup$ – Alex S Nov 26 '20 at 8:53

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.