Given $X = \{ a , b , c \}$ and $R = \{ (a,a) , (b,b) , (c,c) , (a,b) , (a,c)\}$

Is $R$ a total order on $X$?

I know that total order requires the relation to be comparable on all elements, anti-symmetric, and transitive.

What I am confused about is that I was told this relation is NOT total order, but I do not see how the elements cannot be compared, because they surely are anti-symmetric and transitive.

Can't $a$ be compared to itself? Surely $(a,b)$ and $(a,c)$ pass the comparability test, so all that remains must be the reflexive examples.

Clarification is greatly appreciated, thank you for your time, patience and assistance!

  • 4
    $\begingroup$ I don't think you correctly grasp the concept of comparability. For instance $b$ and $c$ aren't comparable. Can you understand why? $\endgroup$ – Git Gud Dec 9 '13 at 1:55
  • $\begingroup$ Are b and c incomparable because there is no element in which they are relate-able such as (b,c) or (c,b)? And I am inferring then that every element must be comparable, in this case b and c, which make it not total order. Correct me if I'm wrong. $\endgroup$ – csharpener Dec 9 '13 at 1:59
  • 2
    $\begingroup$ The first part is correct, $b$ and $c$ are incomparable because neither $(b,c)$, nor $(c,b)$ are in $R$. The second part I don't really understand, but it seems you have the right idea. $\endgroup$ – Git Gud Dec 9 '13 at 2:01

A total order relation requires 4 things:

1)refxivity(it is reflexive in this case)
2)anti-symmetricity(it is anti-symmetric)
3)transitivity(it is transitive)

Now compatibility means that if you choose any two elements say a,b then either aRb or bRa
But in this case if we take for example b and c, neither bRc nor cRb so the relation is not compatible and hence is not a total order.


Is this relation transitive?. I don't think so. We have (a,b) and (a,c). To be transitive, (b,c) must be a part of relation too. So, this is not a total order relation because is not transitive.

  • 3
    $\begingroup$ That's not the definition of transitivity: That would be the case if $(b,a)$ and $(a,c)$ were in $R$. In fact, that relation is a partial order, hence transitive. $\endgroup$ – user228113 May 10 '15 at 22:04

Your Answer

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

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