What do the Guava JavaDocs mean by sets being based on different "equivalence relations"?

Question

The Guava JavaDocs for Sets.SetView.union() (as well as intersection(), difference(), and symmetricDifference()) mention "equivalence relations":

Results are undefined if set1 and set2 are sets based on different equivalence relations (as HashSet, TreeSet, and the Map.keySet() of an IdentityHashMap all are).

I struggle to understand the meaning of that sentence.

The glossary defines "equivalence relation" as reflexive ("a.relation(a) is always true"), symmetric (a1.relation(a2) == a2.relation(a1)) and transitive (a1.relation(a2) && a2.relation(a3) implies a1.relation(a3)) - and refers to Object.equals()' docs. (Unfortunately, the Guava wiki doesn't go into any detail...

But how are the different types of Set different in that respect (i.e. equivalence relations)? They all seem to inherit equals() from AbstractSet? It doesn't have to do with the type of object a set holds (e.g. Set<Cow> vs. Set<Chicken>), does it?

Answer 1

It sounds like they are referring to when a Set doesn't use equals and hashCode to compare elements for some reason. The most common example of this is a TreeSet with a custom Comparator. For example, we could have something like this:

Set<String> a = new TreeSet<>();
Set<String> b = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);

The union, intersection, etc. of a and b are undefined, because a and b have different equivalence relations defined between elements.

Java SE also makes mention of this kind of situation when it's talking about ordering which is inconsistent with equals (see TreeSet):

Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Set interface is defined in terms of the equals operation, but a TreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal. The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.