The definition of total order in "Algorithms 4th Edition" by Robert Sedgewick & Kevin Wayne.

Question

I am reading "Algorithms 4th Edition" by Robert Sedgewick & Kevin Wayne.

In this book, there is the following definition of total order:

1. for all $v$, $v = v$.
2. for all $v$ and $w$, if $v < w$ then $w > v$ and if $v = w$ then $w = v$.
3. for all $v, w,$ and $x$, if $v \leq w$ and $w \leq x$ then $v \leq x$.

I think $v = v$ for all $v$ is trivially true.

Is this definition really right?

---

Let $S := \{0, 1\}$.
Let $E := \{(0, 0), (1, 1)\}$.
Let $G := \{(1, 0), (0, 1)\}$.
Let $L := \emptyset$.

For any $(a, b) \in S \times S$, we define $a = b$ iff $(a, b) \in E$.
For any $(a, b) \in S \times S$, we define $a > b$ iff $(a, b) \in G$.
For any $(a, b) \in S \times S$, we define $a < b$ iff $(a, b) \in L$.
For any $(a, b) \in S \times S$, we define $a \ge b$ iff $(a, b) \in E \cup G$.
For any $(a, b) \in S \times S$, we define $a \le b$ iff $(a, b) \in E \cup L$.

Then, the following statements hold:

1. for all $v \in S$, $v = v$.
2. for all $v \in S$ and $w \in S$, if $v < w$ then $w > v$ and if $v = w$ then $w = v$.
3. for all $v \in S, w \in S,$ and $x \in S$, if $v \leq w$ and $w \leq x$ then $v \leq x$.

But, $1 \leq 0$ doesn't hold and $0 \leq 1$ doesn't hold.

I think the above definition of total order by Sedgewick & Wayne is not right.

Answer 1

I'd hesitate to say that Sedgewick and Wayne's definition of "total order" is "not right", since you're normally entitled to define your terms in the way that you might think is best suited to their intended purpose, but it's certainly far from standard. Their use of the term "antisymmetric" is even more idiosyncratic. In my opinion, their use of terminology should be strongly deprecated.

The usual definition of a total order requires it to satisfy the law of comparability (or the corresponding law of trichotomy for strict orders), which Sedgewick and Wayne's definition does not do, as your example demonstrates.

The usual definition of antisymmetry for a relation $\ R\ $ is that $\ aRb\ \&\ bRa\implies a=b\ $. Sedgewick and Wayne's definition, on the other hand, includes what is usually called symmetry in the definition of equivalence relations (if $\ v=w\ $ then $\ w=v\ $) or partial orders, and the condition that the relation $\ <\ $ be a subrelation of the inverse of $\ >\ $ (if $\ w<v\ $ then $\ v>w\ $).

Answer 2

To amplify the answer @lonzaleggiera provided, as the term "total order" is conventionally used, the modifier total means precisely that every pair of elements is comparable. In other words, for all $v$ and $w$, either $v \leq w$ or $w \leq v$. By contrast, the three conditions that you quote utterly fail to ensure comparability.