Semitransitive relations

Question

By a digraph, let us mean an ordered pair $(X,r)$ with $r : X \times X \rightarrow B,$ where $X$ is a set and $B = \{\mathrm{False}, \mathrm{True}\}.$

Then supposing $\mathbb{X} =(X,r)$ is a digraph, we may ask: under what circumstances is $r$ the forgetful image of a homomorphism $\mathbb{X}^\mathrm{op} \times \mathbb{X} \rightarrow \mathbb{B},$ where $\mathbb{B} = \{\mathrm{False} \leq \mathrm{True}\}$ is the Boolean domain? Note that $\mathbb{B} = (B,\leq)$ is also a digraph.

Unpacking the definitions, we observe that $\mathbb{X} = (X,\rightarrow)$ has the above property iff it is semitransitive, by which I mean that for all $x,y,a,b \in X,$ we have the following, where the fraction line denotes entailment.

$$\dfrac{x \rightarrow a \rightarrow b \rightarrow y}{x \rightarrow y}$$

Now observe that transitivity implies semitransitivity, and that in the presence of reflexivity, these properties are equivalent. However, not every semitransitive digraph $\mathbb{X} = (X,\rightarrow)$ is transitive. For a minimal counterexample, consider the digraph $\mathbb{X} = \{x \rightarrow a \rightarrow y\}$ with three distinct elements and two arrows. $\mathbb{X}$ is vacuously semitransitive because there is no sequence of three arrows with respect to which the conclusion of the semitransitivity condition needs to be checked. However, $\mathbb{X}$ fails to be transitive because $x \rightarrow y$ is false.

Question. I'm looking for interesting or "natural" examples of semitransitive digraphs that fail to be transitive. Ideas, anyone?

Answer 1

One natural example would be the complete bipartite digraphs, which are all semi-transitive but (if nontrivial) are not transitive.

A complete bipartite digraph is a digraph whose vertices partition into disjoint nonempty sets $A\sqcup B$, such that every node in $A$ points at every node in $B$ and vice versa, but there are no edges within $A$ or within $B$. If $A$ and $B$ are not empty, then the edge relation is not transitive, since following two edges will bring you from a node in $A$ back to a node in $A$. But the relation is semitransitive, since if $x\to a\to b\to y$, then $x$ and $y$ must be on opposite sides of the partition, and so $x\to y$, by completeness.

More generally, if your digraph is tracking some information that flips to an opposite value whenever you follow an edge, then the relation will not generally be transitive, but semi-transitivity is less of an obstacle, since $x$ and $y$ will have opposite values for that information. So there will be many more natural examples like this.

For example, such a situation arose a few months ago in an example I was discussing with Hartry Field concerning the absoluteness of satisfiability, relating to the modal logic of forcing. Namely, consider the models of set theory, where $M\to N$ just in case $N$ is a forcing extension of $M$ with an opposite value to the continuum hypothesis. This relation is not transitive, for essentially the same reason as in the bipartite digraph case, since if you change the value of CH twice, then the models no longer disagree. But the relation is semitransitive, since if you have $M\to N\to U\to V$, then the CH value flipped three times from $M$ to $V$, and so $M\to V$.