Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.