Why doesn't SingletonSet implement SortedSet

This is an interesting point, which seems to illustrate a small hole in the collections API.

The fact is that Collections.singleton() is specified to return a Set, not a SortedSet, and in fact the implementation doesn't support that interface. I don't think it would be helpful for Collections.singleton() to change its behavior and return an instance of a SortedSet. This would encourage implementations to perform instanceof checks and downcasting. (And similar for the corresponding Map methods and interfaces.)

It's a small consolation for this use case, but in Java SE 8 new methods Collections.emptyNavigableMap and emptyNavigableSet were introduced. This is helpful for use cases that want empty navigable collections, but if you really want a navigable with a single element or mapping, you're out of luck. There's an enhancement request JDK-6201174 that covers a similar area; I've updated and refocused it around providing APIs for a singleton navigable set and map.

But wait! As you pointed out, there is a bit of additional state that rides along with sorted/navigable collections, which is the comparator. (Or in the absence of a comparator, implicitly one that provides natural ordering.) Any new singleton APIs would have a provide for that as well. And this points out the fact that the empty* methods I mentioned above don't talk about the Comparator. That seems like another bug: JDK-8181754.

Unfortunately I don't have a really good workaround for you other than to buckle down and implement a one-element, possibly immutable SortedSet or NavigableSet. You could start off with Collections.UnmodifiableNavigableSet. This helps a little, but not much. In fact, the empty navigable set is one of these wrapped around an empty TreeSet! This is quite unhelpful, since you want to avoid TreeSet instances.

I'd probably start from AbstractSet and then add the minimal set of methods from SortedSet. There are rather fewer methods than in NavigableSet, so if you don't need all of its bells and whistles, it'd be a smaller task to stick to SortedSet.

The SortedSet interface defines methods that require a Comparator for the set elements. Thus elements maintained by a SortedSet have to be comparable. If the singleton returned by Collections.singleton() would implement SortedSet, then Collections.singleton() could accept Comparables only (which is not what we want).