Relative ranks of Lipschitz mappings on countable discrete metric spaces

Let X be a countable discrete metric space and let X-x denote the family of all functions on X. In this article, we consider the problem of finding the least cardinality of a subset A of X-x such that every element of X-x is a finite composition of elements of A and Lipschitz functions on X. It follows from a classical theorem of Sierpinski that such an A either has size at most 2 or is uncountable.

We show that if X contains a Cauchy sequence or a sufficiently separated, in some sense, subspace, then vertical bar A vertical bar <= 1. On the other hand, we give several results relating vertical bar A vertical bar to the cardinal 0; defined as the minimum cardinality of a dominating family for N-N. In particular, we give a condition on the metric of X under which vertical bar A vertical bar >= partial derivative holds and a further condition that implies vertical bar A vertical bar <= partial derivative. Examples satisfying both of these conditions include all subsets of N-k and the sequence of partial sums of the harmonic series with the usual euclidean metric.

To conclude, we show that if X is any countable discrete subset of the real numbers R with the usual euclidean metric, then vertical bar A vertical bar = 1 or almost always, in the sense of Baire category, vertical bar A vertical bar = partial derivative. (C) 2010 Elsevier B.V. All rights reserved.