Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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 at 18:11
    
@FooBarrigno Thanks But isn't $R$ is also asymmetric since its irreflexive and transitive ? –  seteropere Jan 17 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 at 18:39
    
@FooBarrigno so if $R$ is irreflexive,transitive $G_R$ is guaranteed to be DAG, right? –  seteropere Jan 17 at 18:40
1  
yes, because it is a strict partial order. –  Foo Barrigno Jan 17 at 18:44

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.