3
$\begingroup$

I have the following definition of intransitivity:

R is intransitive iff
for all xyz: xRy & yRz -> ~xRz

Now, given the following: aRb bRc cRd

Can I conclude that ~aRd?

Intuitively, I would say yes*, but I'm having problems with the formal proof.
*For example, if R would be 'is a parent of', and incest is impossible, clearly a is not a parent of d. But how to prove that?

  • 0
    @Jonas: And in some sense, the same as Ross's (once you go to the quotient set modulo the equivalence relation encoded in the "modulo 2").2011-04-06

2 Answers 2

3

How about a set of naturals, with $aRb \Leftrightarrow a \neq b \pmod 2$?

  • 0
    So if I understand correctly, that relation would be intransitive, but it does not carry over to the next element. So this is a counterexample to my question.2011-04-06
4

The relation $\mathrm{R}$ on $\{1,2,3,4\}$ given by $\mathrm{R}=\{(1,2),(2,3),(3,4),(1,4)\}$ is intransitive.


Added:

$\{(1,2),(2,1)\}$ is also intransitive, and it gives a counterexample with $a=c=1$ and $b=d=2$. This would be the minimal counterexample in a sense, and although I wasn't thinking in those terms, in a way this is a reformulation of Ross's nice example.

  • 0
    So my conclusion is incorrect.. I think I get it now, thanks!2011-04-06