Does every preorder induce a partial order?

110 Views Asked by At

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".

1

There are 1 best solutions below

8
On BEST ANSWER

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$.