Java comparator documentation: confused about the terminology "total order."

Question

I was recently reading the documentation for the Comparator type in the Java programming language. This type is used to let the programmer define custom ordering relations on objects of their choosing.

At its core, a Comparator is an object that exposes a method called

int compare(Argument one, Argument two)

such that calling compare(a, b) returns -1 if a should come before b, 0 if a and b compare equal, and 1 if a should come after b.

Toward the end of the documentation is this section talking about the mathematical properties of the relation given by the comparator:

For the mathematically inclined, the relation that defines the imposed ordering that a given comparator c imposes on a given set of objects S is:

  {(x, y) such that c.compare(x, y) <= 0}.

The quotient for this total order is:

  {(x, y) such that c.compare(x, y) == 0}.

It follows immediately from the contract for compare that the quotient is an equivalence relation on S, and that the imposed ordering is a total order on S.

I'm confused about the language here. By my understanding, a total order is a binary relation $R$ over a set $S$ that is total, antisymmetric, and transitive. Antisymmetry requires that if $xRy$ and $yRx$, then $x = y$. As a result, if the relation defined above is a total order, then the quotient defined by the relation should be the trivial quotient - the equivalence classes defined this way should have at most one element in them. In that case, defining the quotient seems unnecessary.

It seems like the type of relation that the authors are describing is more accurately a total preorder, a relation that's transitive and total. A total preorder $R$ naturally induces an equivalence relation defined where both $xRy$ and $yRx$ are true and a partial order relation over those equivalence classes. In that case, the discussion in the documentation seems more accurate.

I'm pretty sure that at least one of the following is true, but I'm not sure which is the case:

1. I have the wrong definition of a total order.
2. The authors have the wrong definition of a total order.
3. I'm reading too much into the definition given in the documentation.
4. Something in the reasoning I've given above is incorrect.

Can someone help me understand which of the above are true and why?

Answer 1

There are several reasons why, in computer science, it is common look at order relations that are only pre-orders. These may be called "total orders" in the jargon of the field.

Similarly, in the context of mathematical logic it is not too rare to see someone call a reflexive, transitive relation a "partial order", even though partial are often required to be antisymmetric in other contexts. In other words, they use "partial order" instead of "preorder". This kind of terminology variation is something you become accustomed to when you work in a particular field. It happens to be particularly common with order relations.

One important reason that preorders are so common in computing contexts is that it is common to have distinct objects that compare as "equal" even though they are not the same. For example, in Java, the == operator tests whether two objects are literally the same reference. But, if we are sorting string objects, we may have two different objects that both contain the same string. In that case, the natural comparator will return 0, even though the objects are not the same.

So, when the documentation says that two objects "compare equal", that does not mean that the objects are actually equal, which is why the quotient mentioned in the documentation is not necessarily trivial.

Answer 2

Sadly, the documentation is as confused as you think it is. There's even more wrong than you've described, since the quotient is not, as they say, the equivalence relation that turns the preorder into an order, but the set of its equivalence classes (on which the order is defined).

Answer 3

It's certainly 2. - the authors didn't get the definition right.

You could say that it's a total order on the quotient {Argument}/{(x,y) | c.compare(x,y) == 0}. Also note that this is the quotient and not {(x,y) | c.compare(x,y) == 0}. The latter is an equivalence relation.

Good catch!