Is it not the case that this fixed-point theorem has a fairly easy constructive proof? You search for the fixed point using a conventional binary subdivision algorithm, maintaining a shrinking interval that has f(x) > x on the left and f(x) < x on the right. In the process, you produce a convergent sequence that halves the maximum distance to the fixed point at each step. This is a Cauchy sequence, which in some sense *is* a real number than satisfies f(x) = x. This is pretty much as constructive as it is possible to get for a general real result. And this proof doesn't seem much harder to me than the classic non-constructive one. On Sun, Nov 13, 2011 at 4:36 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Not sure if this is exactly on point, but:
It's an easy theorem in topology that any continuous function
f: [0,1] -> [0,1]
has a fixed point. But this says nothing about how to find it.
If, however, it's known that there is a number c with 0 < c < 1 such that for all x,y in [0,1] we have
|f(x) - f(y)| <= c |x - y|,
then it's easy to show that for any x in [0,1] the sequence
x, f(x), f(f(x)), . . .
must converge to a fixed point.
--Dan
Marc wrote: << Could anyone supply me with elementary examples that illustrate the idea of a non-constructive proof, for those with a "Martin Gardner reader" level of mathematical sophistication that also has a not-too-trivial but reasonably easily-verified case?
Even though kleptomaniacs can't help themselves, they do.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun