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.

I'd like to post some more ideas in the hope that they inspire someone, or at least save you time searching the same dead end.

The solution for continuous functions works because the rational numbers are countable.  But that is actually not a requirement: It would be sufficient if there just was a "first" point at which functions which are not identical differ.  In the case of functions on the rationals, this point is the rational number which is the first in the order of the enumeration.

Generally speaking, this method of defining an order works for real-valued functions on any set which can be well-ordered.  A well-ordered set is a set each non-empty subset of which has a first element.  We can define f << g if and only if f(x) < g(x) at the first argument at which they differ, x.  (If f≠g, the set of arguments at which they differ is non-empty and therefore has a first element.)

So if only one could find a well-order for the real numbers, our problem would be solved.  Unfortunately, Wikipedia states that though it has been proven that the real numbers can be well-ordered, nobody has found out how to do it yet.  *Sigh*.  Well, at least this proves that there is a solution (no offence, JLo).

Another, rather more wooly, idea:  As Richard pointed out, we are trying to order a very "big" set, whose magnitude (called "cardinality") is larger than that of the real numbers.  The two smaller infinite cardinalities are that of the natural numbers (= that of the rational numbers; smallest) and that of the reals (next).  One can derive the order of the reals from that of the naturals: When written in decimal, a real number is larger than another if the most significant ("first") digit in which they differ is larger.  Similarly, a continuous function can be defined as larger than another if its value at the "first" rational argument at which they differ is larger (which is how I hit on the same solution as Steve).

However, deriving an order in this way is not without loss: Going from the naturals to the reals, one loses well-ordering.  Going from the reals to something still larger, what might one dispense with?  Both the ordering of the real numbers and our solution for the ordering of continuous real functions has a further property: x < y exactly if x+a < y+a for any a.  Somehow I don't believe this can be retained; maybe we should search for an ordering without this property, counterintuitive though that may seem.

Posted by vswitchs on 2006-08-25 15:35:34