[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