Constructive mathematics

constructive trend in mathematics

Mathematics built up in connection with a certain constructive mathematical view on the world that usually seeks to relate statements on the existence of mathematical objects with the possibility of their construction, rejecting thereby a number of standpoints of traditional set-theoretic mathematics and leading to the appearance of pure existence theorems (in particular, the abstraction of actual infinity and the rejection of the universal nature of the law of the excluded middle). The constructive trend in mathematics has emerged in some form or other throughout its history, although it appears to be C.F. Gauss who first stated explicitly the difference, being the principal one in constructive mathematics, between potential infinity and the actual mathematical infinity; he objected to the use of the latter. Subsequent critical steps in this direction were taken by L. Kronecker, H. Poincaré and especially L.E.J. Brouwer. Brouwer's criticism, written at the time of the crisis in the foundations of mathematics at the beginning of the 20th century, vigorously renounced both the belief in the existential character of infinite sets and the conviction in the admissibility of unrestricted extrapolation of classical logical principles, especially of the law of the excluded middle. As an alternative set-theoretic approach, Brouwer, and subsequently his followers, developed an original program for constructing mathematics, known nowadays under the name of intuitionism. Brouwer's intuitionistic mathematics can be regarded as the first systematic attempt at building up mathematics on a constructive basis. In parallel with the success of the intuitionists there appeared in proof theory (created by D. Hilbert with the aim of justifying set-theoretic mathematics) a number of original ideals that served as a starting point for constructive trends differing from intuitionism. A significant number of papers on this topic (and here a fairly broad spectrum of interpretations of terms like "constructive" , "effective" , etc., by various researchers can be found) have depended on the success achieved in the study of the mathematical concept of algorithm (again, under the influence of the ideas of Hilbert). One of the most generally followed and definitive approaches to the development of constructive mathematics on this basis was provided by A.A. Markov of the Soviet school of constructive mathematics, the formation of the fundamental concepts of which go back to the 1950's. The term "constructive mathematics" itself (the constructive trend in mathematics) is often applied in a more general sense of the word, referring to this Soviet approach to constructive mathematics. In what follows this term will be used in this latter sense.

Constructive mathematics can be briefly characterized by the following basic features: 1) the objects of study are constructive processes and the constructive objects that arise as a result of carrying out these processes (cf. Constructive object); 2) the examination of the constructive processes and objects is carried out within the framework of the abstraction of potential realizability with total exclusion of the idea of an actual infinity; 3) the intuitive concept of effectiveness is connected with a precise notion of algorithm; and 4) a special constructive logic is used that takes into account the specifics of the constructive processes and objects.

The notions of constructive process and constructive object are primitive; the ideas concerning them have practical material human activity as their basis. Examples of constructive processes are assembling watches on a conveyor belt, the complete or partial dismantling of them in the repair shop, the typesetting of texts (with corrections) in printing works, the formation and decomposition of railway trains, etc. The characteristic feature of constructive processes is an operation passing through separate stages in the context of certain clearly indicated rules with elementary objects that are clearly distinguishable from one another and that are considered as indecomposable in the course of these processes. The resulting configuration, composed of the original elementary objects, are regarded as constructive objects. Constructive mathematics does not have the need to delve into the general notion of a constructive process or object since one special form of the constructive objects proves to be entirely adequate for its needs, namely a word over some alphabet or other.

The examination of words (this concept is also supposed to be primitive) takes place as follows.

To begin with, a certain alphabet is fixed, that is, a list of indecomposable, demonstrably different elementary signs (letters). Each letter of the alphabet can be copied; linear strings or symbols arising from sequences of acts of such copying are regarded as words over the original alphabet. It is convenient to add to the words over the given alphabet the empty word, that is, a string containing no symbol. For example, the string 5): "abbbccd" , and 6): "book" , are words over the English alphabet. In its handling of words, constructive mathematics — and here its abstract nature becomes apparent — uses abstraction by identification and potential realization. The first of these enables one, by abstracting from different copies and the original, to speak about different copies of a given letter as well as about it being one and the same letter. For example, in the word 5) the letter "b" of the English alphabet occurs three times, whereas in reality, three distinct copies of the original letter were reproduced in writing the word down. This agreement naturally extends to words that are identically written (but graphically distinct). For example, one speaks of the two concrete words, the word "book" and the word 6), as one and the same word. On the assumption of abstraction by identification there emerges the primitive ability of the human being to "scan" words, that is, to be able repeatedly and consistently to recognize strings of symbols as being the same or different. Hilbert pointed out this ability as a minimal premise for any scientific activity. Abstraction of potential realizability enables one to ignore in discussions concerning the description of words the real-life constraints of space, time and material. In this way one can begin to argue about imagined very long words as though they really existed, in particular, it is regarded as possible to write on the right (or left) of a given word any other word. This implies the possibility of considering arbitrary large natural numbers as well as adding any two natural numbers, since natural numbers can be regarded, for example, as words of the form $ 0 , 0 \mid , 0 \mid \mid $, etc. over the alphabet $ 0 \mid $. Apart from this, the abstraction of potential realizability does not enable one to regard "infinite" words and the collection of "all" words over a given alphabet as complete in their own right (in particular, the natural series is not regarded as a complete object). Considerations of this sort require drawing upon a stronger abstraction — the abstraction of actual infinity, which constructive mathematics rejects.

The acceptance of the abstraction of potential realizability leads to the fact that not only elementary, completely visible constructive processes are considered (for example the writing down of short words), but also conceptual constructive processes which are not subject to actual reproduction. Such processes are defined by their instructions; these instructions themselves then become an object of study. The instruction giving the constructive process (for simplicity, one is dealing with processes operating on words) has to be understood by all and must perfectly uniquely determine from stage to stage the sequential construction of words; furthermore, the stages must be elementary, that is, they presuppose nothing other than the ability of the reader to read, write (or erase) words. These stages thus reduce to the writing down and graphical comparison of certain words, as well as to the substitution of occurrences of single words into other alternative words (cf. Imbedded word). The termination of the process is defined by the instruction itself and may depend on results obtained at stages prior to the final one; here the acceptance of a decision concerning the conclusive nature of a given stage must also bear the elementary character just described. It is possible that no stage proves to be conclusive, that is, after each complete stage, the given instruction requires that the following stage be completed. To such an instruction one cannot associate any potentially implementable constructive process.

Here it turns out to be convenient to use conventional terminology, according to which the corresponding instruction determines an unboundedly extendable (potentially infinite) process. For the justification of this terminology, one could also extend the original idea on constructive processes by considering along with potentially realizable processes more abstract formations, such as processes identified with their instructions. In connection with the appearance of the potential infinity of constructive processes the question arises as to the means by which one can be certain that a constructive process defined by a given instruction terminates. Constructive mathematics here applies an important principle, called the constructive selection principle (Markov's principle), enabling one to establish such facts by the method of contradiction, that is, the reduction to absurdity of the hypothesis that the corresponding constructive process is potentially infinite. Examples of instructions: 7): write $ \mid $; 8): write on the right of an arbitrary word over the alphabet $ 0 \mid $ the word $ \mid $; 9): $ 9 _ {a} $): write $ \mid $ and go to $ 9 _ {b} $); $ 9 _ {b} $): erase $ \mid $( that is, replace this letter by the empty word) and go to $ 9 _ {a} $); 10): $ 10 _ {a} $): add $ \mid $ to the right of an arbitrary word over the alphabet $ 0 \mid $ and go to $ 10 _ {b} $); $ 10 _ {b} $): if the currently processed word is $ 0 \mid \mid $, then terminate the process, otherwise return to $ 10 _ {a} $); 11): $ 11 _ {a} $): write $ 0 $ and go to $ 11 _ {b} $); $ 11 _ {b} $): add $ \mid $ to the right of the currently processed word and go to $ 11 _ {c} $); $ 11 _ {c} $): if a perfect natural number has been obtained, then terminate the process, otherwise add $ \mid $ to the currently processed word and return to $ 11 _ {b} $).

The instruction 7) defines a constructive process that terminates in one stage by writing the one-letter word $ \mid $. The process of carrying out 9) is potentially infinite. It is not known whether the constructive process defined by 11) terminates (in 11) ideas from number theory have been used for brevity; clearly, a longer instruction of this sort is possible using exclusively the ability to scan, write and compare words over the alphabet $ 0 \mid $). The instructions 8) and 10) have a rather special character: their accomplishment can begin with any word over the indicated alphabet, and, furthermore, the constructive process defined by 8) always terminates, while at the same time, as in the case of 10), it is potentially infinite for certain initial words. Instructions of the above types are conventionally called algorithms (in the present context, one is concerned with algorithms operating on words).

The constructive treatment of existential statements leads to the necessity of considering algorithms. The assertion that a constructive objects with a given property exists, that is, a statement of the form 12): $ \exists x A ( x) $, in relation to ideas about constructive objects as the results of constructive processes, is regarded as established in constructive mathematics only in the case when a potentially realizable constructive process can be indicated which terminates by the construction of the required object. In a similar manner, establishing an existential statement with a parameter 13): $ \forall x \exists y A ( x , y ) $( "for all x there exists an y such that Ax, y" ) presupposes that one can indicate a "general" constructive process starting from an arbitrary constructive object $ x $ of a given primitive type and terminating with the construction of a required $ y $. In other words, 13) expresses the existence of an algorithm for finding $ y $ starting from $ x $. Such a treatment of existence entails a constructive interpretation of disjunction: The statement $ A \lor B $( "A or B" ) is considered to be established only if a constructive process can be presented that terminates with the indication that one of its components is true. The further explanation of the meaning of statements of a more complex structure and the elaboration of rules for handling them in accordance with the original constructive aims, constitutes the problem of constructive semantics and constructive logic. The constructive treatment of existential and disjunctive statements given above is essentially different from the traditional one: In set-theoretic mathematics, for example, 12) can be proved by reducing its denial to absurdity. Such a proof usually contains no method for constructing the required constructive object. Constructive mathematics maintains that such an argument does not prove 12) but only its "double negationdouble negation" , that is, $ \neg \neg \exists x A ( x) $. The latter statement is generally regarded in constructive mathematics as being weaker than 12). Thus, constructive mathematics does not apply the rule of cancelling the double negation nor, consequently, the law of the excluded middle (the constructive treatment of disjunction also indicates that there is no basis for accepting the latter).

The primitive mathematical structures of natural, integer and rational numbers can be directly treated as words of certain simple types over a fixed alphabet; here the relations of equality and order are easily reduced to graphical coincidence and difference of words. The introduction of more complex structures such as the real numbers and functions on them, etc., are realized in constructive mathematics by the notion of algorithm, which, roughly speaking, here plays the same role as the concept of a function in traditional mathematics. In considering the intuitive notions of algorithm too vague for such constructions, constructive mathematics makes here an important step by standardizing the usable algorithms by means of accepting one of the modern precise definitions of this notion together with a corresponding hypothesis in the form of the Church thesis, which asserts that the operational possibilities achievable by algorithms are the same in the intuitive and in the precise senses of the word. In fact, the widest application in constructive mathematics has been attained by Markov's normal algorithms (cf. Normal algorithm). The constructive treatment of existence also leads to the need of making precise the notion of algorithm. For example, the negation of 13) is the assertion of the impossibility of there being some algorithm, while intuitive ideas that suffice for recognizing some or other concrete instruction as an algorithm, in principle do not allow one to obtain some non-trivial theorems on impossibility. On the basis of the principle set out above and using the modern theory of algorithms in constructive mathematics, one develops a number of mathematical disciplines including constructive mathematical analysis, elements of functional analysis, differential equations, the theory of functions of a complex variable, etc. (see Constructive analysis). The theoretical models obtained in this way are based on more modest abstractions than the usual system and although they are not so transparent and elegant as the traditional methods, they are nevertheless, it would seem, capable of serving the same circle of applications.

Having a common critical source with the intuitionistic mathematics of Brouwer and borrowing from it a number of constructions and ideas, constructive mathematics has a certain similarity to the latter. Apart from this, there is also a principal difference both of a general philosophical and a concrete mathematical nature. In the first place, constructive mathematics does not single out the belief, peculiar to intuitionism, in the primitive character of mathematical intuition by supporting that this intuition itself is formed under the influence of practical activities of the human being. Accordingly, abstraction in constructive mathematics proceeds not from mental constructions as in intuitionism, but from the simplest real observable constructive processes. In the mathematical setting, constructive mathematics does not apply the deductive concept of free choice sequences, which goes beyond the framework of constructive processes and objects, nor the intuitionistic theory of the continuum as a medium of free formation based on them. On the other hand, intuitionistic mathematics does not accept the constructive selection principle and does not regard it necessary to eliminate intuitive algorithms in favour of corresponding precise definitions. It should be pointed out that in a recent years a certain trend has emerged towards bringing the constructive and intuitionistic approaches closer together: in certain constructive investigations, in particular those relating to semantics, inductive definitions are used and corresponding to them, inductive proofs recalling Brouwer's construction in the proof of his so-called bar-theorem (see Bar induction) which occupies one of the central places in intuitionistic mathematics.

See also the references to Constructive analysis.

References

[1]	A.A. Fraenkel, Y. Bar-Hillel, "Foundations of set theory" , North-Holland (1958)
[2]	A. Heyting, "Intuitionism: an introduction" , North-Holland (1971)
[3]	D. Hilbert, "Grundlagen der Geometrie" , Springer (1913) pp. Appendix VIII
[4]	A. Heyting (ed.) , Constructivity in mathematics , North-Holland (1959) Zbl 0086.00701
[5]	A.A. Markov, "Theory of algorithms" , Israel Program Sci. Transl. (1961) (Translated from Russian) (Also: Trudy Mat. Inst. Steklov. 42 (1954))
[6]	A.A. Markov, "On the logic of constructive mathematics" , Moscow (1972) (In Russian)
[7]	"Problems on the constructive approach in mathematics 1–6" Trudy Mat. Inst. Steklov. , 52; 67; 72; 93; 113; 129 (1958 - 1973) (In Russian)