Sort the set of functions f:R→R, with R being the set of real numbers. This means you have to find an order "«" that lets you compare any two pairs of unequal functions f and g; unequal means, f(x)≠g(x) for at least one x.

More precisely, these are the requirements for the order "«" you are challenged to find:

1. If f≠g, either f«g or g«f.
2. If f«g and g«h then f«h

You might be tempted to declare f«g when f(x)<g(x) for all x but that would of course fail because e.g. f(x)=x and g(x)=-x would not be comparable with respect to your order.

For a much, much easier challenge, start by finding an order for all continuous functions.

Choose some small delta, d. Then sort all functions such that f(x)<<g(x) whenever the integral from 0 to d of f(x)dx is less than the integral of g(x)dx.  For cases where these integrals are equivalent, sort further by the integral from 0 to d/2, then 0 to d/4 etc.  If f(x)==g(x) in this interval we move on to the interval -d to 0, continually halving (-d/2,0), (-d/4,0) etc. if f(x)==g(x) over (-d,d) we move on to (d,2d), then (-2d,-d) until we find some discrepancy in the integrals.  Eventually we will locate the difference between the functions (because they are continuous).

Discontinuous functions don't seem so easy.

Posted by Eric on 2006-08-22 13:25:47