# Is there a name for this property on a binary relation?

Let $R$ be a binary relation. Consider the property:

$$a R b \wedge b R c \implies \neg(c R a)$$

This looks a lot like transitivity:

$$a R b \wedge b R c \implies a R c$$

In my head I've been calling it "weak transitivity", in that it restricts the existence of "loops" (i.e. $a R b \wedge b R c \wedge c R a$), but it allows more types of relations than transitivity.

I have figured that if the relation is also asymmetric, then this property and transitivity imply each other. But they are not equivalent in the general case. For example, let $P$ be the relation "is a parent of." $P$ satisfies the unnamed property, but is not transitive. if $a P b$ and $b P c$, then $c$ cannot be the parent of $a$, but also $a$ is not the parent of $c$ (they are an ancestor, but not a parent.)

So this property is not equivalent to transitivity. Does it have a name? Is it equivalent to the combination of other named properties?

• If a relation is regarded as a directed graph, then your property is the directed version of Triangle-tree graph. – Somos Jan 18 '18 at 2:24
• Huh, it looks like it. From that it occurs to me that this unnamed property doesn't rule out all loops like I thought, if you have four elements and the relation is only true for $a R b, b R c, c R d, d R a$ then the relation still satisfies the property, but contains a 4-cycle – Blackle Mori Jan 18 '18 at 2:45
• Ok, I've just realized you had already made this comment @BlackleMori. =S – Alejandro Nasif Salum Jan 18 '18 at 6:38
• I'd call this atranstive, in analogy with the property pairs symmetric-asymmetric and reflexive-irreflexive ;-) – Musa Al-hassy Jan 18 '18 at 14:03

I don't think that that particular property has a name, but antitransitivity is $\forall a\,\forall b\,\forall c~.~a\operatorname R b\wedge b\operatorname Rc\to\neg a\operatorname Rc$

• That's interesting, because if we take R to also be symmetric, then I think you can prove that antitransitivity and this unnamed property imply each other. It's like this property forms a "bridge" between transitivity and antitransitivity, depending on if the relation is asymmetric or symmetric! – Blackle Mori Jan 18 '18 at 2:18
• I would not advocate this usage of the prefix anti: It is likely to confuse the property antisymmetry with asymmetry. – Musa Al-hassy Jan 18 '18 at 14:05

You got me thinking about loops, and I came to realize that w.t. (let's call it that way, for weak transitivity) does not forbid every loop, only $\cdots aRbRcRa \cdots$ loops. You still can have w.t. and loops with more than $3$ elements.

For instance, let $R$ be the binary relation over $\mathbb Z$ given by $$aRb \quad \iff \quad b-a\equiv1\pmod 4.$$

Obviously $R$ is not w.t., since $aRb \wedge bRc$ if and only if $$b-a\equiv1 \pmod4 \wedge c-b\equiv1 \pmod4$$ and this implies $a-c\equiv2\not\equiv1 \pmod4$, that is $\neg cRa$. (Interestingly also $\neg aRc$ is valid; so both w.t. and antitransivity hold, but asymmetry too, in relation to your comments).

Nevertheless, coming back to loops, this relation does make larger loops, since $$aRb\wedge bRc \wedge cRd \quad \iff$$ $$\iff \quad b-a\equiv1 \pmod4 \wedge c-b\equiv1 \pmod4 \wedge d-c\equiv1 \pmod4 \quad \implies$$ $$\implies \quad a-d=(a-b)+(b-c)+(c-d) \equiv -3\equiv 1 \pmod4$$ so $dRa$.

Anyway, we still have $\neg aRd$.