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.

What we seem to need here is the two-sided continuous-variable analog of lexicographic (dictionary) order.  It is known that "the number" of functions from R to R is the same as "the number" of subsets of R.  So if we succeed in ordering the real functions, we have also in effect ordered the set of all subsets of real numbers.  It is known that there are "more" subsets of real numbers than there are real numbers (the power set of an infinite set has a strictly larger cardinal number than that of the set).  We appear to be in very deep waters here, but perhaps JLo will eventually be able to make these waters shallow for us with the official solution.  Or maybe somebody here will manage to invent an appropriate analog of dictionary order.

Posted by Richard on 2006-08-23 17:00:17