Atransitive relations?

Question

A relation is transitive if $$x\ R\ y\ \text{and}\ y\ R\ z \implies x\ R\ z$$ for all $x,y,z.$

Are there any relations which are atransitive, or in other words, $$x\ R\ y\ \text{and}\ y\ R\ z \implies \neg (x\ R\ z)$$ for all $x,y,z?$ It doesn't necessarily have to be a mathematical example, an example from ordinary life would suffice.

What about a relation which is "reverse-transitive?" I.e. $$x\ R\ y\ \text{and}\ y\ R\ z \implies z\ R\ x$$ Something which satisfies this property would be the rock-paper-scissors game. Rock beats scissors, and scissors beats paper, so paper beats rock. It doesn't seem like it is possible to have a set with more than three elements with a relation like this.

Edit to add: As pointed out in the comments, in the presence of symmetry there is no difference between transitive and reverse transitive. So I am looking for examples of "reverse-transitive" relations which are not symmetric.

Answer 1

Given a line in the euclidean plane, we say that $x R y$ if $x$ and $y$ are on both sides of the line. This is a relation on points of the plane that are not on the line, and it seems that this is an atransitive relation.

Edit: more generally, if $X$ is a set that is the disjoint union of two sets $X_1$ and $X_2$, we say that $x R y$ if $x$ and $y$ do not belong to the same set $X_1$ or $X_2$. This gives an atransitive relation.

Colloquially, the enemy of my enemy is my friend.

Answer 2

"Atransitive" relations appear very frequently. I'll give you two mathematical examples.

1. The immediate successor relation on natural numbers is atransitive: $x R y$ holds precisely if $x$ is one less than $y$. If $x$ is one less than $y$ and $y$ is one less than $z$, then $x$ cannot be one less than $z$.

2. On any bipartite graph, the edge relation is atransitive: if $x R y$ holds, then $x$ belongs to one part, and $y$ to the other part. If $y R z$, then $z$ belongs to the same part as $x$, so there cannot be an edge between them.

You can easily turn this into examples from ordinary life: consider e.g. $xRy$ that holds if $x$ is standing immediately behind $y$ in a queue; or the relation $xRy$ that holds if $x$ and $y$ are playing in opposite teams in a game of football.

---

We can also find some "reverse-transitive" relations on arbitrarily large sets. For example, the relation that never holds satisfies reverse-transitivity on any set. The relation that always holds also satisfies the condition, as does every symmetric, transitive relation.

Mandating asymmetry, by itself, is not sufficient to characterize rock-paper-scissors: you can have asymmetric, reverse-transitive relations on sets with more than three elements. Consider e.g. the "$x$ loses against $y$" relation of the game rock-paper-scissors-MathSEkarma, where rock, paper, scissors beat each other as usual, while MathSEkarma is completely inert: it doesn't beat and is not beaten by anything. Or rock-metal-paper-scissors, where rock, paper, scissors work as usual, and metal works exactly like rock, winning only against scissors but losing only against paper. These both satisfy reverse-transitivity.

To obtain a unique characterization of rock-paper-scissors, we need the relation $R$ to satisfy at least one more property beyond asymmetry. For example, the condition $xRy \vee yRx \vee x = y$ does the trick (exercise!).

If there are four or more elements,then we can find some $x$ that loses against (i.e. is related to) two different elements $y$,$z$. But then y cannot lose against z, as otherwise by reverse-transitivity we would have that $x$ does not lose against $z$. Similarly, $z$ cannot lose against $y$ either, which violates the condition above.

Answer 3

You can have reverse-transitive relations of any size. The empty relation is an example, or any joining-together of smaller reverse transitive relations. More interestingly, you can have reverse transitive relations where all the elements are joined to each other via other elements, so they're not just made by sticking together smaller relations.

An irreflexive relation is the same as a directed graph, and being reverse-transitive then means that if there's an arrow from $A$ to $B$ and $B$ to $C$, there must also be an arrow from $C$ to $A$ completing the cycle. Consider a triangular tesselation of the plane. Now consider arrows along all the edges, so that the arrows along upwards-facing triangles are going clockwise, and the arrows around downwards triangles are going anti-clockwise. The directed graph this forms is a reverse transitive relation.

What is true is that you can't have more than 3 elements that are all related to each other in a reverse transitive relation which is antisymmetric.

Proof: the only way this works for 3 elements is to have a cycle $aRbRcRa$. Consider adding a 4th element $d$, and we can assume wlog $dRa$. Then $dRaRb \implies bRd$ (filling in the $ABD$ cycle). But now $C$ and $D$ are both pointing into $A$, so there's no way to make a complete cycle out of $A, C, D$.

Answer 4

Example of "atransitive" (or antitransitive) relation: "is the mother of"

If $A$ is the mother of $B$ and $B$ is the mother of $C$, then $A$ is not the mother of $C.$