# Does irreflexivity guarantee acyclicity?

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

-
Not necessarily. Two counter-examples: $R$ is $x\ne y$ for some set $X$, and $R$ being $y = x+1 \pmod{n}$ for $x,y\in Zn$ – Foo Barrigno Jan 17 '14 at 18:11
@FooBarrigno Thanks But isn't $R$ is also asymmetric since its irreflexive and transitive ? – seteropere Jan 17 '14 at 18:23
I take back my examples - they are not transitive relations. I somehow missed that part of the question. – Foo Barrigno Jan 17 '14 at 18:39
@FooBarrigno so if $R$ is irreflexive,transitive $G_R$ is guaranteed to be DAG, right? – seteropere Jan 17 '14 at 18:40
yes, because it is a strict partial order. – Foo Barrigno Jan 17 '14 at 18:44

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.

-