3
$\begingroup$

A (non-strict) preorder is defined as a reflexive and transitive homogenous relation; a (non-strict) partial order is defined as a reflexive, antisymmetric, and transitive homogenous relation.

Clearly, every partial order is a preorder but not every preorder needs to be a partial order (cf. [1]). However, it seems to me that every preorder induces a partial order via the following construction:

  • Every preorder induces a strict preorder (an irreflexive, transitive relation). [2]

  • Every strict preorder is a strict partial order (an irreflexive, transitive, antisymmetric relation). [3]

  • Every strict partial order induces a (non-strict) partial order. [4]

Is that correct or where did I go wrong? I appreciate any help you can provide.


Sources:

[1] StackExchange: Preorders vs partial orders - Clarification

[2] Wikipedia: Strict preorder induced by a preorder

[3] Wikipedia on preorders: "A binary relation is a strict preorder if and only if it is a strict partial order."

[4] Wikipedia on partial orders: "Conversely, a strict partial order $<$ on $P$ may be converted to a non-strict partial order".

$\endgroup$

1 Answer 1

4
$\begingroup$

Here's an easy way to get a partial order:

Starting with a preorder $R$,

for each element $x$, put into the equivalence class of $x$ every element $y$ such that both $xRy$ and $yRx$.

You immediately have a partial order on the equivalence classes.


Now I refer to your steps.

Technically, every preorder induces a strict preorder unless all the elements are equivalent.

With that qualification, yes, your way works.

For illustration:

Suppose there are three elements in the preorder $a\equiv b$ and $a<c$.

The obvious way gives a partial order with two elements, $[a,b]$ being less than $[c]$.

Your way gives rise to a partial order with three elements, such that $a$ is less than $c$ and such that $b$ is less than $c$. The new partial order doesn't say anything that relates $a$ and $b$.

$\endgroup$
8
  • 1
    $\begingroup$ Thanks, that certainly seems like a more straightforward way to get there. I suppose the partial order on the set of equivalence classes then canonically induces a partial order on the original set via $x \preceq y \quad :\Leftrightarrow \quad [x] \preceq [y]$, right? $\endgroup$
    – Maxas
    Jun 16, 2023 at 8:50
  • $\begingroup$ @Maxas No it doesn't. The relation you retrieve that way is the same preorder you started with. $\endgroup$
    – amrsa
    Jun 16, 2023 at 9:08
  • $\begingroup$ @amrsa Yes, I just realized $\preceq$ defined that way on the original set would not be antisymmetric. That means that the procedure sketched by Chris doesn't produce a partial order on the set itself, unlike what I presumably outlined in my original post. Or am I overlooking something? $\endgroup$
    – Maxas
    Jun 16, 2023 at 9:17
  • 1
    $\begingroup$ @Maxas No, you are right. It's just a partial order on the quotient set. $\endgroup$
    – amrsa
    Jun 16, 2023 at 9:18
  • $\begingroup$ @amrsa Do you know if the one in the original post works? $\endgroup$
    – Maxas
    Jun 16, 2023 at 9:19

You must log in to answer this question.

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