Let $R$ be a reflexive binary relation and $R^*$ be its reflexive transitive closure. The question is what is the equivalent condition in terms of $R$ to $R^*$ being a partial order.

Intuitively, a reflexive transitive closure adds reflexivity and transitivity to the original relation. But just because $R$ is antisymmetric doesn't mean $R^*$ is a partial order.

  • 1
    $\begingroup$ $R$ (not counting the loops) must not have any directed cycles. $\endgroup$ – Srivatsan Dec 13 '11 at 10:10
  • $\begingroup$ Does it have a special name? $\endgroup$ – Pteromys Dec 14 '11 at 11:52

Directed acyclic graph (often abbreviated to DAG).


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.