Constructive analysis

recursive analysis, computable analysis

A name covering several directions in the foundations of mathematics and mathematical analysis. In the development of constructive analysis either both or the second of the following two principal aims are investigated: 1) a non-traditional construction of some fragment of analysis on the basis of initial concepts that are clearer and take computational possibilities into account to a larger extent than the set-theoretical assumptions of ordinary analysis; and 2) the study of effectiveness in analysis; the introduction and study of computable objects in analysis, in particular, research into the question: From what initial data can one find effectively some computable object? In correspondence with these aims, studies in constructive analysis can be roughly divided into two types: Tending or not tending towards the achievement of 1). Investigations of the first type are characterized by the use of non-standard logic or by restrictions on the use of traditional logical or mathematical means, while in works of the second type, free use is made of traditional logic and mathematics. Foundational works (cf. –[4]) in which the modern concept of a computable real number were developed, relate to the second type (cf. also –[12]). Studies in intuitionistic analysis (cf. Intuitionism), which arose in relation to the intuitionistic program expounded by L.E.J. Brouwer for the constructivization of mathematics and which have had an essential influence on the formulation of problems and methods of constructive analysis, as well as R.L. Goodstein's recursive analysis (cf. [12]) and the original and far-reaching system of constructive analysis expounded by E. Bishop (cf. [13]), relate to the first type. (Bishop's constructive analysis occupies an intermediate place between intuitionism and systems using exact notions of an algorithm.) An original treatment of constructive analysis (in particular, of measure theory) was proposed in 1970 by P. Martin-Löf [14]. Starting from the 1950s with the work of A.A. Markov, N.A. Shanin and their pupils (cf. [15], [16], [19]), in the USSR a system of constructive analysis was intensively developed. It belongs to the first type and falls within the confines of the constructive trend in mathematics. Being part of constructive mathematics, this system (below the term "constructive analysis" is used for brevity) retains the characteristic features of constructive mathematics. In particular, consideration is restricted to constructive objects (cf. Constructive object) (most often words over some alphabet or objects having an explicit coding by words) and is carried out within the abstraction of potential realizability using a special constructive logic. This logic is developed by taking the feature of constructive objects as results of potentially-complete infinite constructions into account. Here the completeness excludes the use of the abstraction of actual infinity, and the intuitive concept of "effectiveness" is related to one of the exact notions of an algorithm (in the majority of papers related to the system of constructive analysis considered, the concept of a normal algorithm is used). A large number of results have been obtained within constructive analysis. These are interesting from the point of view of both problems 1) and 2). The possibility, in principle, of constructing by tools of constructive mathematics a number of theories, such as the theory of elementary functions, the theory of series, Riemann and Lebesgue integration, the theory of functions of a complex variable, the theory of generalized functions, etc., has been demonstrated. The constructive theories obtained are remarkably different from the corresponding traditional theories. These differences, moreover, manifest themselves not only in concrete problems related to applications of analysis, but also in theoretical concepts (e.g. the notion of compactness, etc.).

The fundamental concepts in constructive analysis are those of a constructive real number and of a constructive function of a real variable. Constructive real numbers may be introduced by various (not always equivalent) methods. We will describe one such method, following Cantor's construction of the classical continuum and leading to the most convincing and natural concept of a constructive (computable) real number. First one introduces the natural numbers as words of the form $ 0 , 01 , 011 \dots $ over the binary alphabet $ \{ 0 , 1 \} $. Analogously one defines rational numbers as words of a certain type over the alphabet $ \{ 0 , 1 , - , / \} $. One defines the relations of order and equality on rational numbers, as well as arithmetical operations over them. A constructive sequence of natural numbers is a normal algorithm mapping every natural number into a natural number. The notion of a constructive sequence of rational numbers is treated the same way. Schemes of normal algorithms can be uniquely coded by words over the alphabet $ \{ 0 , 1 \} $. The code of a given algorithm is called the description of the algorithm. A constructive sequence of natural numbers $ \alpha $ is called a fundamentality regulator (or modulus of convergence) of a constructive sequence of rational numbers $ \beta $ if for any natural numbers $ l , m , n $ such that $ l , m \geq \alpha ( n) $ one has $ | \beta ( l) - \beta ( m) | < 2 ^ {-n} $. A constructive sequence of rational numbers is called fundamental if one can construct a fundamentality regulator for it.

Constructive real numbers are either rational numbers or words over the alphabet $ \{ 0 , 1 , \square \} $ of the form $ U \square V $( here $ \square $ plays the role of separating sign), where $ U $ is the description of a constructive sequence of rational numbers and $ V $ is the description of a constructive sequence of natural numbers that is a fundamentality regulator for it. This concept of a constructive real number (introduced by N.A. Shanin, cf. [16], who called such numbers "FR-numberFR-numbers" or "duplex (constructive real number)duplices" ) is well compatible with the intuitive conception of computable real numbers as objects having an effective approximation by rational numbers that can be made as accurate as one pleases. For constructive real numbers one can define in a natural way the relations of order and equality, as well as the arithmetical operations (these are given by algorithms). The system of constructive real numbers with these order and equality relations and arithmetical operations turns out to be a field. Further, one may consider constructive sequences of constructive real numbers and subsequently define the same ideas as above, the concept of a fundamental constructive sequence of constructive real numbers and the concept of constructive convergence of a constructive sequence of constructive real numbers to a constructive real number. Relative to this concept of convergence, the system of constructive real numbers is complete: There is an algorithm that, starting from the description of any constructive sequence of constructive real numbers $ \gamma $ and the description of a fundamentality regulator for it, gives a constructive real number to which $ \gamma $ converges (constructively) (the completeness theorem for the system of constructive real numbers). By methods analogous to Cantor's method, one can also prove the constructive uncountability of the set of all constructive real numbers: There is an algorithm mapping the description of any sequence of constructive real numbers into a real number that is different (in the sense of equality of constructive real numbers) from all terms of this constructive sequence. The completeness theorem gives a remarkable similarity between the constructive and classical theories of limits. This similarity manifests itself especially clearly in questions on the convergence of some concrete sequences and series used in analysis. Along with this there are also considerable differences, manifesting themselves, e.g., in the following result of E. Specker (cf. [4]): It is possible to construct an increasing constructive sequence of constructive real numbers $ \beta $ such that $ 0 < \beta ( n) < 1 $ always, but such that $ \beta $ is not fundamental (hence, does not converge (constructively) to any constructive real number). Moreover, $ \beta $ does not contain any constructively convergent subsequence and the set of values of $ \beta $ does not attain its supremum in the constructive continuum. Another way of introducing the concept of a constructive real number is the constructivization of the notion of expansion in some base. More precisely, a constructive $ m $- ary fraction $ ( m > 1 ) $ is a (normal) algorithm $ \alpha $ such that $ \alpha ( 0) $ is an integer and $ \alpha ( i) $ for $ i > 0 $ is a natural number, where $ 0 \leq \alpha ( i) \leq m - 1 $( with the $ m $- ary fraction $ \alpha $ one associates the constructive sequence of constructive real numbers $ \alpha ( 0) + \sum _ {k=1}^ {n} m ^ {-k} \alpha ( k) $). Despite the simplicity of this concept of a constructive real number, it is not widely used since it has a number of essential drawbacks: e.g. the completeness theorem is not preserved, and there is no algorithm realizing the addition of any two $ m $- ary fractions.

The concept of a constructive function is a precise formulation of the intuitive notion of a pointwise-computable function over computable real numbers. A constructive function (of a real variable) is a (normal) algorithm $ F $ such that, for any two equal constructive real numbers $ x $ and $ y $, if $ F $ is applicable to $ x $ then it is applicable to $ y $ and $ F ( x) , F ( y) $ are equal constructive real numbers. The elementary functions (the exponential function, the trigonometric functions, etc.) can be introduced in terms of constructive functions, with preservation of the usual properties. Theories of differentiation, Riemann integration, etc., close to the traditional theories, can be developed for constructive real functions. Besides these, other functions not usual from the traditional point of view are possible: e.g. there has been constructed a constructive function that is everywhere defined and continuous on the unit interval but not bounded on it (cf. [17]). There is also no analogue in traditional analysis of the theorem stating that every constructive function is constructively continuous at every point at which it is defined (cf. [18]).

The system of concepts and methods of constructive analysis, having allowed one to make significant advances from the point of view of the aim 1), also turned out to be convenient for clarifying the computational relationships in analysis, since many theorems in constructive analysis are either statements on the realization of algorithms constructing objects from some initial data, or are assertions on the non-existence of such algorithms. By now (1987) the unsolvability of quite a lot of natural decidability problems in analysis has been established. Results of this type (which are completely absent in courses on traditional analysis) have a clear practical and theoretical value, since they extract potential computational features and help in giving a clear understanding of the limits of what is computable. Thus, the impossibility of the following algorithms (in the sense of some precise formulation of this concept) has been proved: 1) recognizing whether or not an arbitrary constructive real number equals zero; 2) finding for each convergent constructive sequence of rational numbers the constructive real number to which it converges; 3) finding a solution for any compatible system of linear equations (over the field of constructive real numbers); 4) finding a root of an arbitrary continuous piecewise-linear definite function; 5) finding the Riemann integral of an arbitrary continuous piecewise-linear function on the unit interval. The following theorem, which completely solves the problem on the possibility of an effective transition from one number system to another, also belongs to this circle of results. An algorithm that finds for each $ m $- ary constructive fraction the $ n $- ary constructive fraction equal to it exists if and only if the set of all prime divisors of $ n $ is contained in the set of all prime divisors of $ m $( cf. [6]). (In particular, there is an algorithm for going from the decimal system to the binary system, but there is no algorithm for going from the binary to the decimal system.) Theorems on the impossibility of algorithms often give rise to theorems on the existence of algorithms solving the problem considered with more complete initial data (cf. the completeness theorem for constructive real numbers and example 2)) or to an arbitrarily prescribed accuracy (e.g., it is possible to construct an algorithm that finds for each everywhere-defined definite constructive function $ f $ and each $ n $ a constructive real number $ x _ {f,n} $ such that $ | f ( x _ {f,n} ) | < 2 ^ {-n} $). Combining such results allows one to obtain in many situations a clear view on how to pose various algorithmic problems correctly.

References

[1a]	A.M. Turing, "On computable numbers, with an application to the Entscheidungsproblem" Proc. London Math. Soc. (2) , 42 (1937) pp. 230–265
[1b]	A.M. Turing, "On computable numbers with an application to the Entscheidungsproblem, a correction" Proc. London Math. Soc. (2) , 43 (1937) pp. 544–546
[2]	S. Banach, S. Mazur, Ann. Polon. Math. , 16 (1937) pp. 223
[3]	S. Mazur, "Computable analysis" , PWN (1963)
[4]	E. Specker, "Nicht konstruktiv beweisbare Sätze der Analysis" J. Symbol. Logic , 14 : 3 (1949) pp. 145–158
[5a]	A. Grzegorczyk, "Computable functionals" Fundam. Math. , 42 (1955) pp. 168–202
[5b]	A. Grzegorczyk, "On the definition of computable functionals" Fundam. Math. , 42 (1955) pp. 232–239
[5c]	A. Grzegorczyk, "On the definitions of computable real continuous functions" Fundam. Math. , 44 (1957) pp. 61–71
[6]	A. Mostowski, "On computable sequences" Fundam. Math. , 44 (1957) pp. 37–51
[7]	D. Klaua, "Konstruktive Analysis" , Deutsch. Verlag Wissenschaft. (1961)
[8]	G. Kreisel, D. Lacombe, J.R. Schoenfield, "Fonctionelles récursivement définissables et fonctionelles récursives" C.R. Acad. Sci. , 245 : 4 (1957) pp. 399–402
[9]	G. Kreisel, D. Lacombe, "Ensembles récursivement mésurables et ensembles récursivement ouverts ou fermés" C.R. Acad. Sci. , 245 : 14 (1957) pp. 1106–1109
[10a]	D. Lacombe, "Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables reélles I" C.R. Acad. Sci. , 240 : 26 (1955) pp. 2478–2480
[10b]	D. Lacombe, "Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables reélles II" C.R. Acad. Sci. , 241 : 1 (1955) pp. 13–14
[10c]	D. Lacombe, "Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables reélles III" C.R. Acad. Sci. , 241 : 2 (1955) pp. 151–153
[10d]	D. Lacombe, "Remarques sur les opérateurs récursifs et sur les fonctions récursives d'une variable reélle" C.R. Acad. Sci. , 241 : 19 (1955) pp. 1250–1252
[10e]	D. Lacombe, "Quelques propriétés d'analyse récursive" C.R. Acad. Sci. , 244 : 7 (1957) pp. 838–840
[10f]	D. Lacombe, "Quelques propriétés d'analyse récursive" C.R. Acad. Sci. , 244 : 86 (1957) pp. 996–997
[10g]	D. Lacombe, "Les ensembles récursivement ouverts ou fermés, et leurs applications à l'analyse récursive I" C.R. Acad. Sci. , 245 : 13 (1957) pp. 1040–1043
[10h]	D. Lacombe, "Les ensembles récursivement ouverts ou fermés, et leurs applications à l'analyse récursive II" C.R. Acad. Sci. , 246 : 1 (1958) pp. 28–31
[11]	V.A. Uspenskii, "Leçons sur les fonctions calculables" , Hermann (1966) (Translated from Russian)
[12]	R.L. Goodstein, "Recursive analysis" , North-Holland (1961) (Translated from Russian)
[13]	E.A. Bishop, "Foundations of constructive analysis" , McGraw-Hill (1967)
[14]	P. Martin-Löf, "Notes on constructive mathematics" , Almqvist & Wiksell (1970)
[15]	A.A. Markov, "Theory of algorithms" , Israel Program Sci. Transl. (1961) (Translated from Russian) (Also: Trudy Mat. Inst. Steklov. 42 (1954))
[16]	N.A. Shanin, "Constructive real numbers and constructive function spaces" , Transl. Math. Monogr. , 21 , Amer. Math. Soc. (1968) (Translated from Russian)
[17]	I.D. Zaslavskii, "Some properties of constructive real numbers and constructive functions" Trudy Mat. Inst. Steklov. , 67 (1962) pp. 385–457 (In Russian)
[18]	G.S. Tseitin, "Algorithmic operators in constructive metric spaces" Trudy Mat. Inst. Steklov. , 67 (1962) pp. 295–361 (In Russian)
[19]	B.A. Kushner, "Lectures on constructive mathematical analysis" , Amer. Math. Soc. (1984) (Translated from Russian)

Comments

Bishop-style constructive analysis can also be found in the revised version [a1] of [13]. For recursive analysis see, e.g., [a2]. More on Brouwer's program can be found in the article Intuitionism. An extensive discussion of various formal systems for constructive and intuitionistic analysis, as well as an extensive and useful bibliography is in [a3].

References

[a1]	E. Bishop, D.S. Bridges, "Constructive analysis" , Springer (1985)
[a2]	O. Alberth, "Computable analysis" , McGraw-Hill (1980)
[a3]	M.J. Beeson, "Foundations of constructive mathematics" , Springer (1985)