2
$\begingroup$

I am trying to understand directed preorders, a.k.a. directed sets. Are they analogous to connected DAGs?

$\endgroup$
  • $\begingroup$ One may visualize any preorder as follow. A preorder is a certain type of category. If the category is small, we may take it's nerve. One might also might be able to visualize this as a graph of some sort. $\endgroup$ – Baby Dragon May 22 '13 at 3:52
1
$\begingroup$

Not quite. A DAG cannot have edges $x\to y$ and $y\to x$, while a directed preorder can have $x\leq y$ and $y\leq x$.

In general, you can visualize a preorder as the reachability relation on the vertices of a directed graph. Then a directed preorder corresponds to a graph where any two vertices are reachable from some third vertex.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ So it is necessary that the directed graph be at least weakly connected. $\endgroup$ – ThomasMcLeod Aug 7 '13 at 22:14

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.