9
$\begingroup$

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!

$\endgroup$
3
  • 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, 2013 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, 2013 at 1:59
  • 3
    $\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, 2013 at 2:01

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ This is not true of a strict order relation like $(\mathbb Z, <)$. Strict total orders are by definition, irreflexive, and comparable to every element, in my example, every other element, in $\mathbb Z$. So the set of intergers under the strict total order of $<$, we have $-1\lt n \forall n \in \{0, 1, 2, \ldots\}$ and we have for every $m$, $m\in \{\ldots, -4, -3, -2\}$, $m\lt -1$. $\endgroup$
    – amWhy
    Apr 2, 2020 at 19:18
  • $\begingroup$ I meant it is not true of a strict total order. $\endgroup$
    – amWhy
    Apr 2, 2020 at 19:32
-6
$\begingroup$

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.

$\endgroup$
1
  • 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, 2015 at 22:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .