7
$\begingroup$

According to Wikipedia, strict partial orders and strict weak orders are transitive binary relations satisfying asymmetry, antisymmetry and irreflexivity. See screenshot below:

enter image description here

However, if strict partial orders and strict weak orders have different rows in the table, it must be because they are somehow different. Hence,

What is the difference between a strict partial order and a strict weak order?

Also, can you provide examples that illuminate the difference?

$\endgroup$

2 Answers 2

4
$\begingroup$

Without any qualifiers the term partial order typically means a relation on a set $X$ that is reflexive, antisymmetric, and transitive. An example is $\subseteq$ on the power set $2^S$ of a set $S$. The reflexive reduction of a partial order is called a strict partial order. The analogous example is $\subsetneq$ on $2^S$.

A partial order is a weak order if it contains no ${\mathbf 2}+{\mathbf 1}$, in other words, if no distinct elements both incomparable to any third distinct element are comparable to one another. An example is the has-lesser-cardinality-than-or-is relation $\preceq$ on the power set $2^S$ of a finite set $S$. Its reflexive reduction is a strict weak order. The analogous example is has-lesser-cardinality-than $\prec$ on $2^S$. We have $\{3,7\} \preceq \{1,2,4\}$ and $\{3,7\} \preceq \{3,7\}$, but $\{3,7\}$ and $\{10,20\}$ are incomparable. By contrast, under $\prec$, $\{3,7\}$ is incomparable to itself.

$\endgroup$
4
$\begingroup$

Wikipedia's weak ordering page contains this quote:

A strict partial order $<$ is a strict weak ordering if and only if incomparability with respect to $<$ is an equivalence relation.

So it seems that every strict weak order is a strict partial order, but not conversely. For example, consider the relation on the set $\{1,2,3,4,{\between}\}$ where $1<2<3<4$ and $1<{\between}<4$ but neither $2$ nor $3$ is comparable to $\between$. This is a strict partial order, but it's not a strict weak order: $2$ is not comparable to $\between$, and $\between$ is not comparable to $3$, but $2$ is comparable to $3$. (Actually $1$ and $4$ aren't even needed for a more minimal example.) If this order were changed so that $2$ and $3$ were not comparable, then it would be a strict weak order.

$\endgroup$
3
  • $\begingroup$ Thank you very much for your answer. How could one tweak your example for it to be a strict weak order? To be honest, I don’t quite understand the meaning of the Wikipedia quote you provided. $\endgroup$
    – EoDmnFOr3q
    Commented Jun 2 at 22:04
  • 1
    $\begingroup$ It sounds like a strict weak order is a disjoint union of total orders. $\endgroup$ Commented Jun 2 at 22:06
  • 1
    $\begingroup$ No, @RobertShore. See my answer to this question. $\endgroup$ Commented Jun 2 at 22:08

You must log in to answer this question.

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