Equivalence relation and natural ordering on a class in Java

Question

I have very well understood the difference between Comparable and Comparator interfaces, and as such the ordering imposed by them.

Further, i am clear on why the compareTo must be consistent with equals method. From Oracle docs,

It is strongly recommended (though not required) that natural orderings be consistent with equals. This is so because sorted sets (and sorted maps) without explicit comparators behave "strangely" when they are used with elements (or keys) whose natural ordering is inconsistent with equals. In particular, such a sorted set (or sorted map) violates the general contract for set (or map), which is defined in terms of the equals method.

For example, if one adds two keys a and b such that (!a.equals(b) && a.compareTo(b) == 0) to a sorted set that does not use an explicit comparator, the second add operation returns false (and the size of the sorted set does not increase) because a and b are equivalent from the sorted set's perspective.

However, I am unable to clear myself on the paragraph(below),

For the mathematically inclined, the relation that defines the natural ordering on a given class C is:

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

The quotient for this total order is:

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

It follows immediately from the contract for compareTo that the quotient is an equivalence relation on C, and that the natural ordering is a total order on C. When we say that a class's natural ordering is consistent with equals, we mean that the quotient for the natural ordering is the equivalence relation defined by the class's equals(Object) method:

    {(x, y) such that x.equals(y)}.  

What is the author trying to suggest here?. Can someone explain with a simple example.

Answer 1

Basically it is saying that consistent with equals means that the set of (x, y) pairs for which x.compareTo(y) == 0 is true is identical to the set of (x, y) pairs for which x.equals(y) is true.

This isn't anything different from the common-sense understanding of consistent with equals used in the first paragraph. It is simply expressed the definition in a formal algebraic way. I'm sure that someone decided that it would be fun to add this to the docs, but I'm not sure it has any practical utility to programmers.

Answer 2

Let's say that you create this foolish class

public class A implements Comparable<A> {
  private int value;

  public A(int value){
    this.value = value }

  public boolean equals(Object obj){ 
     if (obj instanceof A)
        return this.value = ((A)obj).value;
     else return false;
  }

  public int compareTo(A another){
     return 0;
  }
}

Then you create two instances:

A a1 = new A(3);
A a2 = new A(4);
SortedSet<A> set = new TreeSet<A>();
set.add(a1);
set.add(a2);

The SortedSet accepts a1 but it doesn't accept a2 because a1.equals(a2) == false but a2.compareTo(a2) == 0; Remember that in a set for definition all elements are different to each other (it's like the mathemathic concept of set).

Answer 3

It's all math ! (x,y) means " x relates to y "

An equivalence relation is a relation on a collection of elements (in this case instances of the class C) that is reflective, symmetrical and transitional.

reflective means: that every element relates to itself symmetrical means: if a relates to b then b relates to a transitional means: if a relates to b and b relates to c than a relates to c.

so the quotient relation of x.compareTo(y) == 0 is thus an equivalence relation as for each instance c of C : c.compareTo(c) is supposed to be zero, for every instance c1, c2 from C: if c1.comparTo(c2)==0 then c2.compareTo(c1) should also be zero. And for all c1, c2, c3 where c1.compareTo(c2) is zero and c2.compareTo(c3) is zero then c1.compareTo(c3) should also be zero.

A total order is a relation which is transitive (see above), anti symmetrical (again see above but now inversed as it is anti) and total hence a compareTo should reflect a total order: if a.compareTo(b) is <= 0 and b.compareTo(c) <= 0 then a.compareTo(c) must be <= 0 if a.compareTo(b) is <= 0 then b.compareTo(a) must be >= 0

total means either a.compareTo(b) <= 0 or either b.compareTo(a) <= 0, the total refers to that any element can be compared to another element hence all elements can be ordered so the ordering is total

the quotient comes from a.compareTo(b) <=0 and b.compareTo(a) <= 0 hence a.compareTo(b) == 0

I hope this is a bit more explanatory than the original...