# Total Order Relation

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!

• I don't think you correctly grasp the concept of comparability. For instance $b$ and $c$ aren't comparable. Can you understand why? – Git Gud Dec 9 '13 at 1:55
• 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. – csharpener Dec 9 '13 at 1:59
• 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. – Git Gud Dec 9 '13 at 2:01

## 2 Answers

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)
4)comparibility

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.

• 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. – user228113 May 10 '15 at 22:04