The sets that you  propose are not only totally ordered sets
but rather totally pre-ordered  and I think that it is indeed important
for  many applications.  It is very often the case that you have
to deal with a set of complex objects  a part which is used for
the pre-order relation.
In that case, you will probably suggest to use a "map" but  "maps"
do not allow for multiple bindings.

 I have myself written a library for balanced trees and used it for
 several applications. I have found that, when dealing with equivalent
 elements, it is sometimes useful
     -  to allow equivalent elements to occur simultaneously in the tree.
    -  to  allow the user to precise, when using function "add" ,  the treatment
       he/she wants to be performed on equivalent elements (keeping both,
       keeping the old one, replacing the old one by the new one)

I am conscious that this goes beyond "set" operations but you get
these possibilities almost  for free when you have balanced trees
based on a pre-order relation.
Why not let us have access directly to your balanced trees package?

Also:
Rather than using type "int" for comparison, it would be clearer
to use an explicit type  comparison= Smaller | Equiv | Greater.