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?

  • 1
    $\begingroup$ If a relation is regarded as a directed graph, then your property is the directed version of Triangle-tree graph. $\endgroup$ – Somos Jan 18 '18 at 2:24
  • $\begingroup$ 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 $\endgroup$ – Blackle Mori Jan 18 '18 at 2:45
  • $\begingroup$ Ok, I've just realized you had already made this comment @BlackleMori. =S $\endgroup$ – Alejandro Nasif Salum Jan 18 '18 at 6:38
  • $\begingroup$ I'd call this atranstive, in analogy with the property pairs symmetric-asymmetric and reflexive-irreflexive ;-) $\endgroup$ – 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$

  • $\begingroup$ 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! $\endgroup$ – Blackle Mori Jan 18 '18 at 2:18
  • $\begingroup$ I would not advocate this usage of the prefix anti: It is likely to confuse the property antisymmetry with asymmetry. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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