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.
(In reply to
For continuous functions... by Eric)
So here's an example of the sort of continuous function that has me
worried, and that I will use it to test suggested approaches:
f(x) = 0 if x=0
xsin(1/x) if x <> 0
as compared to
g(x) = 0
f(x) is continuous but not (I think) differentiable at 0, and there are
infinitely many points at which the integral of f(x)dx from 0 to e is
zero. I wonder whether, given a countable number of predetermined
testing points, I couldn't always construct a function different from g
whose integral from 0 to the testing point was 0. If I could, then
Eric's scheme doesn't work.
In fact, here's a simpler counterexample. Eric is testing at multiples of some predetermined d. Define a function
h(x) = 0 except between d and 2d
= sine(2pi(x-d)/d) between d and 2d
The integral of h(x) is 0 for any region that includes all of or none
of [d,2d]. This function is indistinguishable from g(x) if
the integral is
evaluated between 0 and d, -d, d/2, 2d, -d/2, -2d, d/4, 4d, -d/4, -4d,
d/8, 8d, etc.
And we can't just wave away this counterexample by picking a different
d. The sorting algorithm needs to work for a determinable d,
unless it provides consistent results no matter what value of d is
chosen. It's not an algorithm if it gives one sort order for one
value of d, and a different sort order for a different value of d, and
the user can select any value of d he chooses at any time.
re: For continuous functions...
