Why is antisymmetry necessary for comparison sort?

Question

If you want to sort Objects in a list $C$ in Java, you use Collections.sort(myList) do it. This will apply the mergesort algorithm to any List of Objects. You only have to make sure that the compareTo(other) method is implemented for the objects you want to sort.

Now, if you read the JavaDoc of compareTo, it seems as if you would basically implement a relation "$\leq$" between objects in $C$. This relation has to be (according to my interpretation of the JavaDoc of compareTo):

• total: $\forall x, y \in C: x \leq y \lor y \leq x$
• antisymmetric: $\forall x,y \in C: x \leq y \land y \leq x \Rightarrow x = y$
• transitive: $\forall x,y,z \in C: x \leq y \land y \leq z \Rightarrow x \leq z$

It makes sense that the relation has to be total. A good example is $\mathbb{C}$ with the relation $\leq$ which should make clear, that totality is defenitely needed.

If you didn't have transitivity, you couldn't order the elements in a one-dimensional list. You also couldn't apply mergesort.

But why do you need antisymmetry?

Imagine a list $C$ of some humans and the relation "is at least as old as". This relation on $C$ is total, it is transitive, but if two people have the same age, they are not the same. But that isn't a problem for sorting, is it? So why do you need antisymmetry?

Answer 1

In mathematics, any two elements x and y of a set P that is partially ordered by a binary relation $\leq$ are comparable when either $x \leq y$ or $y \leq x$. If it is not the case that x and y are comparable, then they are called incomparable.

(Partial orders require reflexivity, antisymmetry, and transitivity, but not mutual comparability between every pair of elements.)

A totally ordered set is exactly a partially ordered set in which every pair of elements is comparable. A relation having the property of "totality" means that any pair of elements in the set of the relation are mutually comparable under the relation. Totality implies reflexivity, that is, $a \leq a$, thus a total order is also a partial order.

Mutual comparability between every pair of elements is required for "compareTo(other)" to be well-defined for every pair of elements.

---

Can you imagine a relation that is total, transitive but not antisymmetric? What would be the problem of that relation for sorting?

Then you could have $\,x\leq y,\;\,y\leq x,\,$ and $\,x \neq y.\,$ Then you would have distinct $x, y$ such that $\,x \lt y\,$ and $\,y\lt x,\,$ which is impossible. For one thing, it thus fails to be total, because $\lt$ is the implicit strict total order, and with a strict total order, trichotomy must hold:
$\forall x, y \in \,\text{set},\;\;x\lt y\; \lor \;y \lt x\; \lor\; x = y$.

Answer 2

Suppose that $\preceq$ is a reflexive and transitive total relation on a set $X$. For example, $X$ could (as in your question) be a set of people, with $x\preceq y$ iff $\operatorname{age}(x)\le\operatorname{age}(y)$. The problem with trying to sort on $\preceq$ is that if $x\preceq y\preceq x\ne y$ (e.g., if $x$ and $y$ are different individuals of the same age in the example), there is no way to decide whether to sort $x$ before $y$ or $y$ before $x$. Totality of $\preceq$ means that you have a kind of one-dimensional list, but it’s a list of ‘clumps’, not of individuals. In the example, for instance, you have a clump for each age.

You can use $\preceq$ to define an equivalence relation $\sim$ on $X$ by $x\sim y$ iff $x\preceq y\preceq x$. (It’s easy to check that this $\sim$ really is an equivalence relation.) Then $\preceq$ induces an actual linear order $\sqsubseteq$ on $X/\sim$, the set of $\sim$-equivalence classes, in a natural way: if $[x],[y]\in X/\sim$, then $[x]\sqsubseteq[y]$ iff $x\preceq y$. (You can easily check that $\sqsubseteq$ is well-defined and is a linear order of $X/\sim$.) In the example, for each person $x\in X$ the $\sim$-equivalence class $[x]$ is simply the set of all $y\in X$ who are the same age as $x$, and there is an obvious bijection between $X/\sim$ and $A=\{\operatorname{age}(x):x\in X\}$; indeed, the map

$$X/\sim\to A:[x]\mapsto\operatorname{age}(x)$$

is an order-isomorphism between $\langle X/\sim,\sqsubseteq\rangle$ and $\langle A,\le\rangle$. To put this back into the sorting context, you can sort the ages, but you can’t sort the individuals by age unless you allow persons of the same age to be ordered arbitrarily within their clump.