Transactions of the American Mathematical Society

Author(s): Philipp Gerhardy; Ulrich Kohlenbach
Journal: Trans. Amer. Math. Soc. 360 (2008), 2615-2660.
MSC (2000): Primary 03F10, 03F35, 47H09, 47H10
Posted: October 5, 2007
Retrieve article in: PDF DVI PostScript

Abstract: In this paper we prove general logical metatheorems which state that for large classes of theorems and proofs in (nonlinear) functional analysis it is possible to extract from the proofs effective bounds which depend only on very sparse local bounds on certain parameters. This means that the bounds are uniform for all parameters meeting these weak local boundedness conditions. The results vastly generalize related theorems due to the second author where the global boundedness of the underlying metric space (resp. a convex subset of a normed space) was assumed. Our results treat general classes of spaces such as metric, hyperbolic, CAT(0), normed, uniformly convex and inner product spaces and classes of functions such as nonexpansive, Hölder-Lipschitz, uniformly continuous, bounded and weakly quasi-nonexpansive ones. We give several applications in the area of metric fixed point theory. In particular, we show that the uniformities observed in a number of recently found effective bounds (by proof theoretic analysis) can be seen as instances of our general logical results.

1.: M. Bezem, Strongly majorizable functionals of finite type: a model of bar recursion containing discontinous functionals, J. of Symbolic Logic 50 (1985), 652-660. MR 805674 (87c:03139)
2.: J. M. Borwein, S. Reich, and I. Shafrir, Krasnoselski-Mann iterations in normed spaces, Canad. Math. Bull. 35 (1992), 21-28. MR 1157459 (93e:47072)
3.: M. R. Bridson and A. Haefliger, Metric spaces of non-positive curvature, Springer Verlag, Berlin, 1999. MR 1744486 (2000k:53038)
4.: F. Bruhat and J. Tits, Groupes réductifs sur un corps local. I. Données radicielles valuées, Inst. Hautes Études Sci. Publ. Math. 41 (1972), 5-251. MR 0327923 (48:6265)
5.: C. E. Chidume, On the approximation of fixed points of nonexpansive mappings, Houston Journal of Mathematics 7 (1981), 345-355. MR 640975 (83b:47063)
6.: W. G. Dotson, On the Mann iterative process, Trans. Amer. Math. Soc. 149 (1970), 65-73. MR 0257828 (41:2477)
7.: M. Edelstein and R.C. O'Brien, Nonexpansive mappings, asymptotic regularity and successive approximations, J. London Math. Soc. 17 (1978), 547-554. MR 500642 (80b:47074)
8.: J. Garcia-Falset, E. Llorens-Fuster, and S. Prus, The fixed point property for mappings admitting a center, Nonlinear Analysis 66 (2007), 1257-1274.
9.: P. Gerhardy and U. Kohlenbach, Strongly uniform bounds from semi-constructive proofs, Ann. Pure Appl. Logic 141 (2006), 89-107. MR 2229932
10.: K. Gödel, Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes, Dialectica 12 (1958), 280-287. MR 0102482 (21:1275)
11.: K. Goebel and W. A. Kirk, Iteration processes for nonexpansive mappings, Topological Methods in Nonlinear Functional Analysis (S.P. Singh, S. Thomeier, and B. Watson, eds.), Contemporary Mathematics, vol. 21, AMS, Providence, R.I., 1983, pp. 115-123. MR 729507 (85a:47059)
12.: W. A. Howard, Hereditarily majorizable functionals of finite type, Metamathematical investigation of intuitionistic arithmetic and analysis (A.S. Troelstra, ed.), Springer LNM, vol. 344, Springer-Verlag, Berlin, 1973, pp. 454-461. MR 0469712 (57:9493)
13.: S. Ishikawa, Fixed points and iterations of a nonexpansive mapping in a Banach space, Proc. Amer. Math. Soc. 59 (1976), 65-71. MR 0412909 (54:1030)
14.: W. A. Kirk, Krasnosel'skii iteration process in hyperbolic spaces, Numer. Funct. Anal. Optimiz. 4 (1982), 371-381. MR 673318 (84e:47067)
15.: -, Nonexpansive mappings and asymptotic regularity, Nonlinear Analysis 40 (2000), 323-332. MR 1768416 (2001m:47116)
16.: S.C. Kleene, Recursive functionals and quantifiers of finite types, I., Trans. Amer. Math. Soc. 91 (1959), 1-52. MR 0102480 (21:1273)
17.: U. Kohlenbach, A logical uniform boundedness principle for abstract metric and hyperbolic spaces, Electronic Notes in Theoretical Computer Science 165 (2006), 81-93. MR 2321765
18.: -, Effective uniform bounds from proofs in abstract functional analysis, CiE 2005. New Computational Paradigms: Changing Conceptions of What is Computable (B. Cooper, B. Loewe, and A. Sorbi, eds.), Springer Publisher, To appear.
19.: -, Effective moduli from ineffective uniqueness proofs. An unwinding of de La Vallee Poussin's proof for Chebycheff approximation, Ann. Pure Appl. Logic 64 (1993), 27-94. MR 1241250 (95b:03061)
20.: -, Arithmetizing proofs in analysis, Logic Colloquium '96 (J.M. Larrazabal, D. Lascar, and G. Mints, eds.), Springer Lecture Notes in Logic, vol. 12, Springer-Verlag, Berlin, 1998, pp. 115-158. MR 1674949 (2000j:03085)
21.: -, A quantitative version of a theorem due to Borwein-Reich-Shafrir, Numer. Funct. Anal. and Optimiz. 22 (2001), 641-656. MR 1849571 (2002i:47076)
22.: -, On the computational content of the Krasnoselski and Ishikawa fixed point theorems, Proc. of the Fourth Workshop on Computability and Complexity in Analysis (J. Blanck, V. Brattka, and P. Hertling, eds.), volume 2064 of Springer Lecture Notes in Computer Science, 2001, pp. 119-145. MR 1893075 (2003b:47090)
23.: -, Uniform asymptotic regularity for Mann iterates, J. Math. Anal. Appl. 279 (2003), 531-544. MR 1974043 (2004d:47098)
24.: -, Some computational aspects of metric fixed point theory, Nonlinear Analysis 61, no.5 (2005), 823-837. MR 2130066 (2005k:47119)
25.: -, Some logical metatheorems with applications in functional analysis, Trans. Amer. Math. Soc. 357 (2005), 89-128 (For some minor errata see the end of []). MR 2098088 (2005h:03110)
26.: U. Kohlenbach and B. Lambov, Bounds on iterations of asymptotically quasi-nonexpansive mappings, Proc. International Conference on Fixed Point Theory and Applications, Valencia 2003 (J.G. Falset, E.L. Fuster, and B. Sims, eds.), Yokohama Publishers, 2004, pp. 143-172. MR 2144170 (2006b:47102)
27.: U. Kohlenbach and L. Leu¸stean, The approximate fixed point property in product spaces, Nonlinear Analysis 66 (2007), 806-818.
28.: -, Mann iterates of directionally nonexpansive mappings in hyperbolic spaces, Abstract and Applied Analysis 8 (2003), 449-477. MR 1983075 (2004e:47092)
29.: U. Kohlenbach and P. Oliva, Proof mining: a systematic way of analyzing proofs in mathematics, Proc. Steklov Inst. Math 242 (2003), 136-164. MR 2054493 (2005a:03111)
30.: M.A. Krasnoselski, Two remarks on the method of successive approximation, Usp. Math. Nauk (N.S.) 10 (1955), 123-127 (Russian). MR 0068119 (16:833a)
31.: L. Leu¸stean, A quadratic rate of asympotic regularity for CAT(0)-spaces, J. Math. Anal. Appl. 325 (2007), 386-399. MR 2273533
32.: -, Proof mining in R-trees and hyperbolic spaces, Electronic Notes in Theoretical Computer Science 165 (2006), 95-106.
33.: H. Luckhardt, Extensional Gödel functional interpretation, Springer LNM, vol. 306, Springer-Verlag, Berlin, 1973. MR 0337512 (49:2281)
34.: H. V. Machado, A characterization of convex subsets of normed spaces, Kodai Math. Sem. Rep. 25 (1973), 307-320. MR 0326359 (48:4703)
35.: W. R. Mann, Mean value methods in iteration, Proc. Amer. Math. Soc. 4 (1953), 506-510. MR 0054846 (14:988f)
36.: A. G. O'Farrell, When uniformly-continuous implies bounded, Irish Math. Soc. Bulletin 53 (2004), 53-56. MR 2117500
37.: S. Reich and I. Shafrir, Nonexpansive iterations in hyperbolic spaces, Nonlinear Analysis, Theory, Methods and Applications 15 (1990), 537-558. MR 1072312 (91k:47135)
38.: I. Shafrir, The approximate fixed point property in Banach and hyperbolic spaces, Israel J. Math. 71 (1990), 211-223. MR 1088815 (92b:47096)
39.: B. Sims, Examples of fixed point free mappings, Handbook of Metric Fixed Point Theory (W.A. Kirk and B. Sims, eds.), Kluwer Academic Publishers, 2001, pp. 35-48. MR 1904273 (2003f:47099)
40.: C. Spector, Provably recursive functionals of analysis: a consistency proof of analysis by an extension of principles formulated in current intuitionistic mathematics, Proceedings of Symposia in Pure Mathematics (J.C.E. Dekker, ed.), vol. 5, AMS, Providence, R.I., 1962, pp. 1-27. MR 0154801 (27:4745)
41.: W. Takahashi, A convexity in metric space and nonexpansive mappings, I. Kodai Math. Sem. Rep. 22 (1970), 142-149. MR 0267565 (42:2467)

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 03F10, 03F35, 47H09, 47H10

Philipp Gerhardy
Affiliation: Department of Mathematics, University of Oslo, Blindern, N-0316 Oslo, Norway

Ulrich Kohlenbach
Affiliation: Department of Mathematics, Technische Universität Darmstadt, Schlossgartenstraß{}e 7, D-64289 Darmstadt, Germany

DOI: 10.1090/S0002-9947-07-04429-7
PII: S 0002-9947(07)04429-7
Received by editor(s): March 17, 2006
Posted: October 5, 2007
Copyright of article: Copyright 2007, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6850(e) ISSN 0002-9947(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS