Does irreflexivity guarantee acyclicity?

442 Views Asked by At

Assume $R$ to be an irreflexive, transitive relation over a set $X$. Let $G=(X,E)$ be its directed graph where $(x,\hat{x})\in E$ if $xR\hat{x}$ is true.

I know irreflexivity means $xRx$ cannot happen for any $x\in X$. Does this guarantee that $G$ is a directed acyclic graph or $DAG$? .

Another question maybe off-topic: if I have two relations $R,\hat{R}$ where both are irreflexive, does it guarantee that $R^*=R\cup\hat{R}$ is also irreflexive for any product strategy $\cup$?

1

There are 1 best solutions below

0
On BEST ANSWER

A Strict Partial Order can be characterized directly by a DAG. It requires irreflexivity, transitivity, and asymmetry. However the asymmetry is implied by the previous two conditions. Since every irreflexive, transitive relation is a strict partial order, then they are all characterized by DAGs.