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

61 Views Asked by At

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?

2

There are 2 best solutions below

2
On

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$

0
On

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