an axiomatic framework for clustering by jon kleinberg may have a problem? In the paper An Impossibility Theorem for Clustering, Jon Kleinberg introduced an axiomatic framework for clustering and showed that his set of axioms are inconsistent. One of the axioms is the Richness Axiom: any partition of the input can be produced by some distance function. 

My question is:


  Isn't the richness axiom unnatural?


The axiom implies that both trivial partitions: the one which puts all elements in the same cluster, and the one in which each cluster is a singleton, are both considered as valid clusterings. However, this is counter-intuitive in real life situations. In many (i guess most) real life situations we wouldn't have both these clusterings considered as valid simultaneously. so i guess the richness axiom could be modified. do we truly need  all partitions to be considered as valid clusterings?
I do not want to attempt a general definition of "unnatural", but I find your argument about the inherent incompatibility of the scale-invariance axiom and the richness axiom as defined in Section 2 of Kleinberg's NIPS paper.

The impossibility result in Section 3 of his paper is stronger, however, and can directly address your concern.  


  Theorem 3.1 If a clustering function f satisfies Scale-Invariance and Consistency,
  then Range(f) is an antichain.


So you can consider weakening the richness axiom, e.g. by asking for all partitions with at least 2 parts, and as long as your set of partitions is rich enough to not be an anti-chain, the impossibility theorem goes through.

Hopcroft and Kannan have come up with a "natural" alternative to the richness axiom for which clustering is possible.  It is buried in their book Computer Science Theory for the Information Age, and described in a lovely teaser on the Gödel’s Lost Letter blog.