Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
How about a universe with just two things in it and $R$ the relation "is different from"? – Arturo Magidin Apr 5 '11 at 21:31
@Arturo: That is a nice verbal description of my second example. – Jonas Meyer Apr 5 '11 at 21:34
@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"). – Arturo Magidin Apr 6 '11 at 0:06
up vote 3 down vote accepted

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

share|cite|improve this answer
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. – JackStoneS Apr 6 '11 at 6:45

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


$\{(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.

share|cite|improve this answer
So my conclusion is incorrect.. I think I get it now, thanks! – JackStoneS Apr 6 '11 at 6:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.