[FOM] counted sets
Vaughan Pratt
pratt at cs.stanford.edu
Mon Aug 24 19:01:07 EDT 2009
Timothy Y. Chow wrote:
> Along those lines, perhaps the set of discontinuities of a monotonic
> function from R to R is an example. Such a set is always countable, but
> depending on what the function is and how it is presented, it may not be
> immediately obvious how to count/list the discontinuities explicitly.
Any such function f: R --> R can be transformed to a monotonic function
aft: I --> I where I = (-1,1), t: I --> R is defined by t(x) =
tan(pi*x/2), and a: R --> I is the inverse of t. The discontinuities of
aft are in an order-preserving bijection with those of f. Unlike the
discontinuities of f however, only finitely many of those of aft can
exceed a given size.
Now enumerate the discontinuities in decreasing order of size. Break
ties (of which there can be only finitely many of a given size) by
enumerating the tied discontinuities in order of occurrence. This is a
definite enumeration independent of the presentation of f.
The point of the transformation is to simplify the enumeration to the
point where it raises no awkward questions. t isn't really needed since
the same procedure applied to af: R --> I yields the same sizes of
discontinuities and hence the same order of enumeration.
Vaughan Pratt
More information about the FOM
mailing list