Prove: Let f be a nondecreasing, but not necessarily continuous, mapping of the closed interval [0,1] into itself. Then f has a fixed point, i.e., there is some x in [0,1] such that f(x)=x.

(Just to avoid any misunderstanding, [0,1] is the set of all real numbers between 0 and 1, with both 0 and 1 also included.)

(In reply to re(3): No Subject by Richard)

with f identically 1 S(0)=1, S(1)=1/2,

S(2)= S(1)+(1/2)^2 = 3/4 not 1

Essentially, what I am doing is a binary search for the fixed point.  At step n the lower limit is S(n) and the upper limit is S(n)+(1/2)^n

So, initally the fixed point could be anywhere in [0,1]
After one step it is either in [0,1/2] or [1/2,1]
Another way to look at it is that I am determining one bit of x at each step.

The choice made of which side to go with is such that at each step f maps [y,z] (y lower limit z upper limit] into [y,z]  Thus, there are in essense two sequences, one of ys and one of zs.

Both sequences converge to the same point x, all ys are <= x and all zs are >= x, and at all times y<=f(y)<=f(x)<=f(z)<=z

Suppose that the function is not continuous at the fixed point.  In that case one of y or z will get stuck there (for the f=1 case z gets stuck) and the other will get closer and closer to x.  In the original formulation S (the ys) will have a limit of x but no S will actually b x.  If the zs get closer and closer but the ys stay the same that is because S sits at the fixed point x and the limit is then x.

Posted by Joel on 2006-11-18 00:14:27