I'm trying to come up with an example of a relation that is quasi-transitive but not transitive. The relation $ x R y $ is a subset of the cartesian product $XxX$, and the asymmetric relation is $xPy \iff xRy $ and $\neg (yRx) $.

The example I'm trying to create is a quasi-transitive relation that is not transitive.

For any $x,y, z \in X$, a binary relation R is

transitive: if $xRy, yRz $ then $xRz$

quasi-transitive: if $xPy, yPz $ then $xPz$

So, in $R^2$ I define the following relation:

$$xRy \iff x\text{ is not larger than } y.$$

If we have $$x=(3,1), y=(0,2) \text{ and } z=(1,1)$$, then $xRy$ and $yRz$, but $ \neg(xRz)$ i.e. $R$ is not transitive.

On the other hand, I also need to show that $R$ is quasi-transitive i.e: $$xPy, yRz \text{ then }xPz$$ and here is where I have problems as I'm failing to arrive to an example where $xPy$ and $yRz$ are also true.


Here are the same definitions but with different notations Relations:


Transitivity quasi-transitivity:


  • 1
    $\begingroup$ What is "quasi-transitive"? As you've defined it, somewhat vaguely, it's the same thing as transitive, assuming you mean both "definitions" to be prefixed with $\forall x,y,z$ whose scope is the whole formula). $\endgroup$ – BrianO Apr 13 '16 at 3:23
  • $\begingroup$ Right thanks, corrected @BrianO $\endgroup$ – user3889486 Apr 13 '16 at 3:25
  • 2
    $\begingroup$ Still not corrected: they both say the same thing, only about different relations ($R$, $P$ respectively). It seems the distinction involves quantifiers; if so, use them! $\endgroup$ – BrianO Apr 13 '16 at 3:31
  • $\begingroup$ changed @BrianO $\endgroup$ – user3889486 Apr 13 '16 at 3:52
  • $\begingroup$ It's still botched. You changed things by adding "for all x,y,z, a binary relation $R$ is" before your passage, but "quasi-transitive" involves not $R$ but $P$, and still we don't know what "quasi-transitive" means. Can you please write out that defintion, self-contained, separately? $\endgroup$ – BrianO Apr 13 '16 at 5:01

Your Answer

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

Browse other questions tagged or ask your own question.