Constructive Mathematics
by Allan Calder
It is commonly held that if human beings ever encounter another intelligent form of life in the universe, the two civilizations will share a basic mathematics that might well serve as a means of communication. In fact, since the time of Plato it has been generally believed that mathematics exists independently of man's knowledge of it and thus possesses a kind of absolute truth. The work of the mathematician, then, is to discover that truth. Not all mathematicians, however, have shared this belief in a "God-given" mathematics. For example, the 19th-century German mathematician Leopold Kronecker maintained that only counting was predetermined. "God made the integers," he wrote (to translate from the German). "All else is the work of man." From this point of view the work of the mathematician is not to discover mathematics but to invent it.
The question of whether mathematics is discovered or invented is not an idle one. Depending on their answer to it mathematicians can have radically divergent views on how the work of mathematics should be conducted. In particular, the belief that mathematics is invented has given rise to a controversial theory known as constructive mathematics, which maintains that to prove that a mathematical object exists it is necessary to show how the object can be constructed. Most recently constructive mathematics has been put forward in a new and challenging form by Errett Bishop of the University of California at San Diego, but its origins can be traced to Immanuel Kant, who in the 18th century maintained that the ultimate truth of mathematics lay in the fact that its concepts could be constructed by the human mind. The consequences of this point of view for such fundamental issues as the validity of mathematical proofs and the meaning of mathematical existence can perhaps best be understood by beginning with the ideas and methods of ancient Greek mathematics, which have guided the development of mathematics over the past 2,500 years. To the Greeks mathematics was essentially geometry, and the quintessence of the subject was Euclid's Elements, where the deductive methods of the Eleatic school of philosophy, the logical procedures of Aristotle and Platonic idealism came together in the notion of an axiomatic system. Euclid began with certain basically undefined objects such as points, lines and planes and a number of axioms, or presumably self-evident statements, about those objects and applied the Aristotelian rules of inference to obtain new statements called theorems. The underlying assumption that because the axioms were "true" and the rules of inference "logical" the theorems too would be true was made plausible by the intuitive nature of Euclidean geometry. Although objects such as a point (which has no size) and a line (which has length but not width) cannot be found in the natural world, most people feel they know what these objects are. Moreover, Euclid's theorems could be checked empirically, that is, an experiment could be done with the aid of pencil and paper to verify that, say, two triangles with sides of the same length have angles of the same size.
In the modern era mathematics has continued to depend on the axiomatic method, but in many cases this method has been applied to objects that lack the intuitive, or constructible, qualities of Euclidean geometry. To the constructivists such applications have robbed mathematics of its meaning. As a result a number of proposals for reinstating intuitive meaning have been put forward over the past 100 years, the latest being Bishop's new constructive mathematics. The earlier efforts played an important part in determining the development of mathematics, however, and so before discussing Bishop's program I shall review the history of this controversy. It is long and varied, but its fundamental issues can be understood by following the evolution of a single ideain mathematics, namely the concept of infinity.
The famous paradoxes of Zeno concerning issues such as infinite divisibility and continuity led the ancient Greek mathematicians to be extremely cautious about infinities. The fundamental object in Greek mathematics was length, and Euclid in particular referred not to unending lines but only to line segments that could be extended to any desired length. This notion of potential infinity - that for any line there is always a longer line - is a reasonable extrapolation from natural experience. The concept of completed, or actual, infinity - that there are actually infinitely long lines - is metaphysically quite different, and it requires a daunting leap of the imagination when it is first encountered. Hence it is not surprising that mathematicians avoided actual infinities as long as they could, limiting themselves to the consideration of potential infinities until well into the modern era.
The modern rebirth of mathematics came in the 17th century, when René Descartes and Pierre de Fermat, by the introduction of Cartesian coordinates, transformed geometric problems into arithmetic ones. This arithmetization of geometry made numbers rather than lengths the fundamental objects of mathematics and paved the way for the independent development by Isaac Newton and Gottfried Wilhelm Leibniz of the infinitesimal calculus: a set of rules for the manipulation of numbers that were infinitely small without being zero. The concept of infinitely small entities (the notion of limits was not made explicit until much later) was troubling in an age when mathematical objects were considered to have the same reality as, say, the electron is thought to have today. In fact, it was some time before the undeniable utility of the calculus forced mathematicians into an uneasy acceptance of it and of the actual infinities it implied. For the next 200 years mathematicians wielded the techniques of the calculus successfully while continuing to question their philosophical basis. Then at the end of the 19th century this irritating grain of sand within the mathematical oyster brought forth a pearl: the theory of sets.
The early development of set theory was due primarily to Georg Cantor, who defined a set as a collection of real or abstract objects, along with a rule by which it could be decided whether or not any given object belonged to the set. This deceptively simple idea had profound consequences for the concept of infinity. Sets such as the set of all real numbers are by their very nature actual infinities. Considering such objects led Cantor to the astonishing conclusion that just as the cardinality, or number of elements, of finite sets can vary, so can the cardinality of infinite sets. In other words, some sets are more infinite than others.
More precisely, two sets have the same size, or cardinality, if the elements of one of the sets can be paired one for one with the elements of the other. And a set is said to be countably infinite if it has the same cardinality as the set of natural numbers 1, 2, 3, - For example, the even numbers 2, 4, 6,... can be matched one for one with the natural numbers and thus are a count-ably infinite set. (As this example indicates, an infinite set can have the same cardinality as a part of itself.) Cantor showed that for any given infinite set there is always another set with greater cardinality. For instance, he observed that no matter how the real numbers are paired with the natural numbers, there will always be some real numbers left unpaired, and so the cardinality of the real numbers is greater than that of the natural numbers. In fact, Cantor proved that beginning with the countably infinite sets an infinite hierarchy of infinities can be generated.
IN "THE SCHOOL OF ATHENS," painted in the early 16th century, Raphael depicts the great philosophers and mathematicians of ancient Greece: Plato (with one hand raised) and Aristotle stand at the center of the painting, Pythagoras contemplates his system of proportions at the lower left and Euclid draws a circle on a slate at the lower right To the Greeks mathematics was essentially geometry, and it was in Elements, Euclid's treatise on the subject, that the notion of an axiomatic system was first laid out In this system certain self-evident statements called axioms are assumed to be true and new statements called theorems are derived from them using the Aristotelian rules of inference. The intuitive nature of Euclidean geometry lends support to the assumption that because the axioms are self-evident and the rules of inference are logical the theorems too are true. The development of mathematics is still guided by the axiomatic method, but over the past several centuries the objects of mathematical inquiry have become increasingly more abstract and less intuitive. As a result some mathematicians have questioned their validity, and most recently a revival of interest in these ideas has been sparked by the work of Errett Bishop of the University of California at San Diego. Bishop proposes to rebuild mathematics without the use of nonintuitive concepts, an approach he calls constructive mathematics. In Bishop's system it is not sufficient to show that a mathematical object must exist logically. One must specify a procedure for actually constructing the object. Such a procedure does not have to be implemented, but it must terminate after a finite number of steps and at the end of each step it must be evident how to proceed to the next.
Eventually set theory would become the basis of modern mathematics, with sets - the new fundamental objects - providing mathematicians with a powerful tool for abstraction. At the outset, however, many of the leading mathematicians of the day found the very notion of an infinite set such as the set of all real numbers absurd. Even Cantor admitted that considering infinite sets as single entities was a concept to which he had been "logically forced, almost against my will." This erasing of the distinction between potential and actual infinities was "in opposition to traditions that had become valued." Yet the sets themselves were less disturbing than the uses to which Cantor put them, and mathematicians were particularly shocked by the novel method Cantor devised to prove there are infinitely many of the numbers that are called transcendental, or nonalgebraic.
Any real number x is algebraic if it satisfies an equation of the form anxn + an-ixn-1 + ... a1x + a0 = 0, where a1, a2, ... an are integers. (For example, the rational numbers are those real numbers that can be expressed in the form p/q, where p and q are integers and q is not zero; thus any rational number is algebraic because it satisfies the equation qx - p = 0 for some values of p and q.) Cantor proved that numbers that do not satisfy this requirement-transcendental numbers - exist, and that there are in fact infinitely many of them, by first showing that the set of algebraic numbers is countably infinite. In other words, he proved that those numbers can be put into a one-to-one correspondence with the natural numbers. As we have seen, the set of real numbers is not countably infinite, and so there must be some "leftover" real numbers that are not algebraic. Now assume that those transcendental numbers are countable: either finite or countably infinite. It is not difficult to show that a set formed by combining two countable sets is itself countable. (This presents no problem if one or both of the sets are finite. If both sets are infinite, then to show that the combined set is countable it suffices to put one of the sets in one-to-one correspondence with the odd numbers and the other in one-to-one correspondence with the even numbers.) Hence if the assumption were true, then the set of real numbers (which is made up of the algebraic numbers and the nonalgebraic numbers) would be countable - a false conclusion. Therefore the assumption that the transcendental numbers are countable is false. They must be un-countably infinite.
THEORY OF INFINITE SETS, which was developed by Georg Cantor in the 1870's, installed sets as the fundamental objects in mathematics, a position that had been held first by lengths and then by numbers. Cantor pointed out that certain infinite sets, such as the even numbers (top row) and the rational numbers (bottom row), are countable in the sense that they can be put into a one-to-one correspondence with the natural numbers 1, 2, 3... (middle row), but other infinite sets, such as the set of real numbers, are not countable because they are essentially larger than the set of natural numbers. (The rational numbers, or the set of all fractions, have no natural order; they are shown here in order according to the sum of the numerator and the denominator.) Cantor devised a series of "transfinite" numbers to express the cardinality, or number of elements, in these infinite sets and then developed a general arithmetic for infinite as well as finite numbers. Before Cantor most mathematicians had limited themselves to the concept of potential infinity: the notion that for every number there is a larger number. Infinite sets forced them to confront the quite different concept of an actual, or completed, infinity: a collection of infinitely many objects that can be considered simultaneously. Constructive mathematicians believe that numbers, not sets, are the basis of mathematics and that since infinite sets do not seem to exist in nature, mathematicians can have no real, intuitive understanding on which to base judgments concerning them. Hence many of the most familiar and useful techniques of modern mathematics must be altered significantly to be constructively valid.
Cantor's proof makes use of the classic method of reductio ad absurdum: proving a proposition by showing that its denial leads to a contradiction. To understand the outraged reaction of mathematicians such as Kronecker to the proof it is necessary to understand that according to mathematical tradition there could be no existence without construction. Or to be more precise, in order to establish that a mathematical object existed it was considered necessary to specify a procedure by which the object could, at least in principle, be constructed. This procedure did not have to be implemented, nor did it have to be implementable in any "reasonable" amount of time. The only stipulations were that the procedure must terminate after a finite number of steps and that at the end of each step there must be no question as to how to proceed to the next. Cantor's proof that the set of transcendental numbers was infinite failed rather spectacularly to meet these requirements, however, in that it did not give rise to one example of a transcendental number, let alone an infinity of them. (It is interesting to note that not everyone considered even the traditional definition of existence to be sufficiently stringent. One mathematician reportedly spent 10 years constructing with only a ruler and a compass a regular polygon of 65,537 sides, an object whose existence had been established by Carl Friedrich Gauss.)
Cantor's proof was the first important example of what has come to be called a pure-existence proof. Giving not the slightest hint of how even a single transcendental number might be found, it established the existence of such numbers by proving that it would be contradictory for them not to exist. Once again the basic issue is infinity. A proof by reductio ad absurdum that establishes the existence of an object in a finite set is perfectly acceptable to any mathematician; one can always in principle produce the object by checking through all the members of the set. But the same is not true for, say, the transcendental numbers, which belong to the infinite set of real numbers. For this reason many mathematicians rejected Cantor's proof completely, objecting that a contradiction was no substitute for a tangible example. This controversy was far from being resolved when in 1889 David Hilbert published an even more contentious pure-existence proof.
The proof concerned a problem that had been formulated by the German mathematician Paul Gordon. One of the outstanding mathematical questions of the day, Gordon's problem proposed the existence of certain (finite) sets of objects with special properties in a number of situations. Hilbert showed by reductio ad absurdum that the sets under consideration existed in every case. Cantor had proved the existence of a set of objects for which at least some examples were known; certain transcendental numbers had been discovered as much as 30 years earlier. Now Hilbert was maintaining that he had established the existence of objects no one had ever seen and no one had the vaguest idea how to construct. "This is not mathematics," said Gordon. "It is theology."
In Hilbert's hands, however, the pure-existence proof soon became a powerful tool, and as the application of set theory began to yield important results in mathematics, the violent objections to its methods began to subside. "Theology," Gordon came to concede, "also has its merits." After Kronecker's death in 1891 the opposition to nonconstructive methods faltered, until in 1907 it found a new voice in the Dutch mathematician L. E. J. Brouwer. Mathematics would become meaningless, Brouwer argued, unless a clear distinction was made between real, or constructive, existence and pure existence. These two notions had become identified throughthe extension of classical logic - specifically the law of the excluded middle - to apply to infinite, as well as finite, sets.
Aristotle's law of the excluded middle states that every proposition is either true or false, and without it there can be no proof by contradiction. For example, in Cantor's proof that there are transcendental numbers the assumption that all numbers are algebraic is shown to lead to a contradiction; therefore by the law of the excluded middle there must be transcendental, or nonalgebraic, numbers. Aristotelian logic is so much a part of daily living that questioning its validity in any situation may seem silly. Most people feel they know the law of the excluded middle is correct because it is continually reaffirmed by their daily experience. For example, given a bag filled with a number of marbles of different colors, no one would object to being told that either there is a red marble in the bag or there is not. In other words, it is not necessary to look in the bag to verify that one of the two assertions is true. And to determine which one is true it suffices to check through the contents of the bag; after a finite length of time the question will be decided.
The situation is quite different when the law of the excluded middle is applied to an infinite set such as a bag containing an infinity of colored marbles. In this case whether the marbles are examined one by one or 1,000 at a time it will never be possible to examine all of them. Therefore although at some point in the examination it may be possible to state that the bag does contain a red marble, it will never be possible to state that the bag does not contain a red marble. This is the fix implied in the notion of infinity: No matter how much of the set has been examined there will always be more to come. The only way to know that the bag does not contain a red marble is to "see" the infinity of marbles all at once. Since no actual infinities have been found in nature, mathematicians have no real, intuitive knowledge of them. Hence to apply the law of the excluded middle to infinite sets they must extrapolate from their experience with finite sets. This extrapolation seems particularly difficult to justify in view of the fact that the Greeks who devised the law of the excluded middle were highly suspicious of actual infinities. Indeed, as Brouwer concluded, the results of such an extrapolation from finite experience need not be "constructively" true, that is, it is possible to prove the pure existence of objects that cannot be constructed [see illustration on page 160]. Brouwer argued that by according such "ideal" objects the same validity as real, or finitely constructible, objects, mathematics lost its certainty. Ideal objects would be used to create more ideal objects, and soon there would be no way [missing text] real meaning.
Proposition: There are infinitely many prime numbers.
Euclid's Proof
1. Let p1, p2, ... pm be any finite set of prime numbers.
2. Consider the number p1 x p2 x ... pm + 1, which cannot be divided evenly by any of the primes p1, p2, ... pm. This number either is prime itself or it is divisible by some other prime p.
3. In either case there must be a prime that is not part of the set p1, p2, ... pm. Hence the set of primes is infinite.
Modern Proof
1. Assume that the proposition is false, that is, there are only finitely many prime numbers p1, p2, ... pm.
2. Consider the number p1 x p2 x ... pm + 1, which cannot be divided evenly by any of the primes p1, p2, ... pm. This number either is prime itself or it is divisible by some other prime p.
3. In either case there must be a prime that is not part of the set p1, p2, ... pm. This result contradicts the assumption that the set of primes is finite, and so the assumption must be incorrect Hence (by the taw of the excluded middle) the set of primes is infinite.
CONSTRUCTIVE AND NONCONSTRUCTIVE PROOFS differ in their use of infinity, as can be seen by comparing Euclid's original proof of the proposition that there exist infinitely many prime numbers with the standard modern proof of the same assertion. (A prime number is a positive integer that can be divided only by 1 and itself.) Euclid's constructive proof (left) demonstrates that for any finite group of prime numbers there is a larger group; the modern, nonconstructive proof (right) demonstrates the existence of an actual infinity of prime numbers. The nonconstructive proof employs the technique of reductio ad absurdum: proving a proposition by showing that its denial leads to a contradiction. Proofs by contradiction rely on Aristotle's law of the excluded middle, which states that any proposition is either true or false. Constructive mathematicians object to the application of this law to infinite sets on the grounds that it may never be possible to decide which alternative is true (see illustration on page 160).
Brouwer's critique came at a time when set theory was particularly vulnerable. After 1900 the reorganization of mathematics on the basis of sets had resulted in the formulation of a number of unresolved paradoxes. For example, Cantor himself observed that since for every set there is a set of higher cardinality, there must be a set V that has higher cardinality than the set of all sets U. which includes everything; on the other hand, because U does include everything the elements of V must be elements of U, and so the cardinality of U must be equal to or greater than that of V. Paradoxes such as this one indicates that there was some defect in the set-theoretic foundations of mathematics, and it was Brouwer's assertion that the defect was due to the introduction of ideal objects.
Brouwer believed the crisis of the paradoxes would have to be resolved by purging mathematics of ideal objects and arguments, that is, by completely rebuilding mathematics along strictly constructive lines. Because this program, called intuitionism, would have wiped out most of contemporary mathematics, even mathematicians sympathetic to Brouwer's criticisms were unwilling to adopt it. They were far more amenable to a plan devised by Hilbert not for purging mathematics from within but for justifying it from without. In this way mathematicians would not, as Hilbert put it, be driven from the paradise Cantor had created for them.
Hilbert believed that although ideal objects might not have meaning in themselves, meaningful objects and theorems could be derived from them. In his view certainty could be restored to mathematics by considering it as a purely formal system: a game whose interest lies not in the objects with which it deals but in its rules and the relations they create among the objects. Mathematics would be shown to have meaning, Hilbert maintained, when the system was proved to be consistent, or free from contradictions.
Hilbert's program, generally referred to as formalism, called first for the representation of mathematics as a formal axiomatic system. It was hoped that by transforming the statements of mathematics into strings of meaningless symbols to be combined according to the rules of logic, whatever unavowed principles of reasoning had given rise to the paradoxes would be revealed. More important, once mathematics was completely formalized one could undertake to demonstrate that it was consistent. For this purpose Hilbert introduced a new theory called proof theory, or metamathematics, in which meaningful statements about the meaningless signs and configurations of the axiomatic system could be formulated. The arguments of metamathematics were required to be completely constructive, indeed finitistic, in nature. Hence there would be no questioning of the validity of a metamathematical proof of the consistency of mathematics.
Brouwer did not accept the proposition that proving mathematics to be consistent would restore its meaning, and he spent most of his life trying to show that mathematics could be done constructively. His program never gained much support, however, not least because the mathematical efforts of the intuitionists tended to be awkward and contrived. And when Brouwer attempted to rid mathematics of ideal notions while preserving certain of its long-established aspects, he introduced ideas that seemed to many mathematicians to be just as idealistic as those he was eliminating.
Ironically, it was not a great faith in mathematics that made mathematicians reject intuitionism but rather a lack of such faith. Although many feared their discipline was indeed losing real meaning, it appeared that the only way to keep the subject alive was to accept some ideal notions. As Hilbert put it: "Compared with the immense expanse of modern mathematics, what would the wretched remnant mean, a few isolated results, incomplete and unrelated, that the intuitionists have obtained." To most mathematicians Hilbert's formalism offered an attractive compromise. If mathematics could be shown to contain no contradictions, then at least it would be assured that if two people (or one person on two different occasions) played the game of mathematics, they would not come up with two different correct answers.
GOLDBACH'S CONJECTURE asserts that every even integer is the sum of two prime numbers, and although this famous proposition has never been proved, there is an efficient procedure for determining whether any particular even number is the sum of two primes. Hence it would be a simple task to program a computer to check each even number in turn and print out a 0 if the number is the sum of two primes and a 1 if it is not, as is shown here. Because the set of even numbers is infinite, the string of O's and (perhaps) 1's generated would also be infinite. Is it correct to apply Aristotle's law of the excluded middle to this infinite string and say that it either does include a 1 or does not? The problem is that it may never be possible to decide which of the two alternatives is correct If a 1 is printed out, one can say conclusively that there is a 1 in the string (and the conjecture is false), but no matter how long the computer runs, as long as no 1 is printed out one can never say that there is no 1 in the string (and the conjecture is true). In constructive mathematics it is possible to assert that the string either does include a 1 or does not only if a finite procedure can be specified for deciding which alternative is true. Constructive mathematicians believe every problem in mathematics can be reduced to a numerical problem such as Goldbach's conjecture and every numerical question can be reduced to a problem of deciding whether or not a 1 appears in a sequence of O's and 1's. Therefore if it were possible to prove constructively that every sequence of O's and 1's either does include a 1 or does not, all problems in mathematics would be solved, since proof would have to include a finite procedure for determining which alternative is true. Most mathematicians, however, believe no such procedure exists, so that no all-embracing constructivist proof can be found.
Then in 1931 Kurt Gödel showed that Hilbert's formalist scheme was doomed to failure. Gödel showed that it is not possible using metamathematics to prove that any formal axiomatic system rich enough to include basic arithmetic is consistent; the best that can be hoped for is to know that such a system is inconsistent. By this time, however, set theory and formalism were so much a part of mathematics that they could no longer be rejected simply because the fundamental goal of formalism had proved unobtainable.
Over the past half century formalism has become an integral part of mathematical thinking and intuitionism has come to be viewed as a quaint mathematical curiosity. Today most mathematicians choose the clean elegance of pure-existence proofs even when constructive proofs of the same results are available, and the certainty of such mathematics is rarely questioned. A few issues concerning set theory continue to be debated (in particular the use of the axiom of choice, which is discussed below), but for the most part the controversy over the set-theoretic methods of Hilbert and Cantor has subsided. Henceit may seem all the more remarkable that a revival of constructive mathematics is now under way.
The new interest dates from the publication in 1967 of Errett Bishop's book The Foundations of Constructive Mathematics. Although the efforts of Bishop's more polemical predecessors generally seemed clumsy and contrived, Bishop's work demonstrates that the results obtained by constructive methods can be just as beautiful and useful as those obtained by formalist methods. Brouwer wanted to build certainty into mathematics at its foundations, starting with an intuitive system of axioms for arithmetic and working up, but Bishop's plan for constructivizing mathematics has a different orientation. He is concerned not with founding mathematics but with doing it constructively, and so he begins with the standard rules of arithmetic and the rational numbers and tries to proceed "realistically" from there. In Bishop's view certainty can be achieved by avoiding idealistic notions and continually checking the objects and theorems generated for intuitive meaning. His results show that a great deal of valuable mathematics can be effectively and elegantly developed in this straightforward manner.
For example, rather than rejecting Cantorian set theory, as Brouwer did, Bishop modifies the theory to give it constructive validity. In particular he insists that to define a set it is not sufficient to simply give a rule by which membership in the set can be decided. He requires that procedures also be specified for actually constructing a member of the set and for demonstrating that two members of the set are distinct. An interesting result of these modifications is that they make one of the most disputed postulates of Cantorian set theory - the axiom of choice - appear to be completely acceptable.
Cantor's axiom of choice states that for any collection of nonempty sets (sets with at least one member) it is always possible to choose a representative from each set. In other words, it is possible to give a rule for selection such that if two people go through the collection following the rule, they will choose the same representatives. To understand why this axiom, which is employed throughout mathematics, is controversial consider the following example proposed by Bertrand Russell.
For any infinite collection of pairs of shoes the rule "Choose the left shoe from each pair" satisfies the axiom of choice, but what rule will serve with an infinite collection of pairs of socks? If there were only a finite number of pairs of socks, it would be possible to go through the collection and mark one sock in each pair so that the rule "Choose the marked sock" would suffice. Since there are infinitely many pairs, however, there is no way to mark a sock in every pair ahead of time, and so there appears to be no such rule for selection. Moreover, the axiom of choice can also present problems when it is applied to a collection consisting of a finite number of sets or even of a single set. For example, Fermat's last theorem is a famous unproved proposition in number theory. A set can be defined to consist of 0 and 1 if Fermat's theorem is true or 2 and 3 if the theorem is false. In this case the rule "Choose the smallest number in the set" specifies a unique representative, but until the theorem is proved there is no way to identify an actual number representing the set.
In Bishop's constructive revision of set theory, however, the axiom of choice appears to be noncontentious, because it is stipulated that to call a set nonempty one must show that the construction method specified in the definition of the set actually generates a member of the set. In constructive theory, then, each nonempty set in a collection can be assumed to have a distinguished member, namely the one that had to be constructed to prove the set nonempty. The axiom of choice can always be satisfied by choosing the distinguished member from each set in the collection.
To understand the ramifications' of Bishop's constructive set theory consider the set of real numbers. In order to define this set constructively it is necessary to specify a method for constructing the real numbers in terms of the intuitively valid rational numbers. In other words, it is necessary to construct the irrational numbers such as V2 and e from the rationals. One might assume that such a number could be considered to be constructed if there were a procedure for computing its decimal expansion to any desired decimal place. This definition of construction is not sufficient, however, because the set of numbers obtained is not closed under the basic operations of arithmetic, as the real numbers must be. In other words, with this definition the sum of two real numbers is not necessarily a real number, the product of two real numbers is not necessarily a real number, and so on. The following example shows how it is possible to construct two numbers a and b in this manner and yet not be able to construct their sum.
It is not known whether or not the sequence 0123456789 appears in the decimal expansion of the irrational number π. Moreover, if the sequence does appear, say, beginning with the kth decimal place of π, then it is not known whether the "critical number" k is even or odd. There is a purely mechanical procedure, however, for determining whether a particular number n is indeed the critical number of π: one simply computes π to the n + 9th decimal place. As a result one can define a to be the number whose decimal expansion begins .333... and continues the same way unless some odd number n turns out to be the critical number of π; in that case 4 is placed in the nth decimal place and all decimal places to the right. Similarly, b can be defined as the number that begins .666... and continues the same way unless some even number n turns out to be the critical number of π; in that case 5 is placed in the nth decimal place and all decimal places to the right.
Note that if π has no critical number, then a equals 1/3, b equals 2/3 and a + b equals 1. On the other hand, if the critical number of π exists and is even, then a is greater than 1/3, b equals 2/3 and a + b is greater than 1, whereas if the critical number of π exists and is odd, then a equals 1/3, b is less than 2/3 and a + b is less than 1. Now try to begin writing down the decimal expansion of a + b. If the sum begins with 1, then it cannot be less than 1 and the critical number of π, if it exists, must be even; if the sum begins with .9, then it cannot be greater than 1 and the critical number of π, if it exists, must be odd. Since no one has any idea how to show that the critical number of π, if it exists, is either odd or even, it is not possible to write down even the first digit of the decimal expansion of a + b. As this example demonstrates, defining numbers by specifying how to compute their decimal expansion is too naive an idea, by nonconstructive standards as well as constructive ones.
How, then, can the set of real numbers be constructed? A real number is determined (in constructive or nonconstructive terms) when it can be approximated arbitrarily closely by rational numbers. For instance, the decimal expansion of a number x to, say, n decimal places differs from the number by less than 1/10". (Consider the familiar decimal expansion of π, which begins 3.141592...; taking the expansion to the fourth decimal place one obtains 3.1415, a number that differs from π by .00009..., which is less than .0001, or 1/104.) By taking a large enough value of n one can always obtain in this way a rational number that is arbitrarily close to x. As we have seen, using decimal expansions to represent real numbers is not always a rich enough notion. There are, however, many other methods for obtaining rational approximations of real numbers. Considering a real number as being defined once it has been approximated by any such method (not just decimal expansions) provides a perfectly adequate system. In constructive theory this means that a real number is considered to be constructed when a (finite) procedure has been specified for producing a rational approximation to within any given degree. In other words, it must be possible to obtain in a finite number of steps a rational number that differs from the real number in question by less than that degree. For example, to approximate a + b, the number whose decimal expansion cannot be written down, to within 1/10n one simply computes π to n + 9 decimal places. If this computation shows that the critical number of π is less than or equal to n + 1, a + b can be computed exactly to n + 1 decimal places. Otherwise a will look like .333... and b will look like .666... up to at least the n + 1th decimal place, and so the rational number 1 will differ from a + b by less than 1/10n.
More generally the numbers constructed by Bishop's definition obey all the rules of standard arithmetic, that is, for any numbers x and y that can be constructed by this definition it will be possible to construct their sum x + y, their difference x - y and so on. To see that x + y can be approximated arbitrarily closely, or to within 1/10n, note that since x and y can be constructed, there must be numbers r and s that differ respectively from x and y by less than l/10n + i. Therefore the sum r + s differs from x + y by less than 2/10n + 1, which is less than 1/10n, and so r + s is a suitable approximation.
Now that a proper method for constructing the real numbers has been established, only a procedure for deciding when two real numbers are distinct is needed to complete the definition of the set of real numbers. That can be done quite simply, by calling two real numbers x and y different if it is possible to construct a rational number r that lies between them. In other words, either x will be greater than r and r will be greater than y or x will be less than r and r will be less than y.
AXIOM OF CHOICE, one of the most widely used and widely disputed tenets of modern set theory, states that for every collection of nonempty sets it is possible to choose a representative from each set. In other words, given a collection such as one of those shown here it should be possible to specify a rule for choosing representatives so that two people going through the collection will make the same choices. For instance, for the infinite collection of pairs of shoes shown at the top the rule "Choose the right shoe from each pair" will suffice. There seems to be no such rule, however, that will serve for the infinite collection of pairs of socks shown at the bottom. This example, due to Bertrand Russell, involves infinite collections of sets, but similar problems can arise with finite collections. In Bishop's version of set theory these problems appear to be eliminated because to define a set constructively it is necessary to give not only a rule by which membership in the set can be decided, as is required in traditional set theory, but also a (finite) procedure for constructing a member of the set To show that a set is nonempty, then, it is necessary to show that the method of construction actually gives rise to a member of the set As a result it is always possible to assume that each set in a collection of nonempty sets contains a distinguished member, namely the one that had to be constructed to show that the set was nonempty. In this way the axiom of choice can always be satisfied.
A curious consequence of Bishop's constructive notion of a set is that it is not possible to consider the set of real numbers as being made up of two nonempty sets with no members in common, a formulation that is frequently used in contemporary mathematics. For example, in nonconstructive set theory the set G consisting of all real numbers less than 1 and the set D consisting of all real numbers greater than or equal to 1 can be considered to be the whole of the set of real numbers. The same is not true constructively, however, because it is not possible to assign certain real numbers such as the number a + b, described above, to one set or the other. And one cannot say a + b belongs either to G or to D and therefore G and D make up the real numbers, because that requires applying the law of the excluded middle to the infinite set of real numbers. (There is always the chance that it may someday be possible to place a number such as a + b that is defined with respect to an unsolved problem in arithmetic in one of the sets G and D. It seems safe to assume, however, that there will always be unsolved problems in arithmetic, so that it will always be possible to define similar numbers.)
This restriction on the makeup of the set of real numbers is reflected in the types of real-number functions that can be defined constructively. In nonconstructive set theory a function f from set S to set T is a rule assigning to each member s of S a member t of T, that is, f(s) equals t. For example, the rule that assigns to each person that person's mother can be thought of as a function from the set of all people to the set of all women. As this example indicates, each member of S must be assigned to one and only one member of T but not all members of T must be assigned to some member of S. (In other words, every person has a mother but not every woman is necessarily a mother.) In constructive set theory a function from set S to set T is still a rule that assigns to each member of S a member of T, but it is also required that the rule be effectively computable, that is, for any particular member 5 of S it must be possible to construct the member f(s), or t, to which it is assigned. Now consider the function from the set of real numbers to itself specified by the following rule: f(r) equals 0 if r is less than 1, and f(r) is 1 if r is greater than or equal to 1. Functions of this type - called step functions because of the appearance of their graph - are widely used in contemporary mathematics [see illustration below]. They are not well defined constructively, however, because it is not possible to decide whether numbers such as a + b are in the set of numbers less than 1 (G) or in the set of numbers greater than or equal to 1 (D), and so it is not possible to decide whether 0 or 1 should be assigned to them. On the other hand, the function considered as being defined not from the set of all real numbers to itself but from the set consisting of G and Z to the set of real numbers is perfectly acceptable.
STEP FUNCTION (color lines) is a widely used function on the real numbers that cannot be defined constructively. In nonconstructive mathematics a function on the real numbers is a rule that assigns to each real number r another real number f(r). For example, the rule that defines the step function is: If r is less than 1, then f(r) equals 0, and if r is greater than or equal to 1, then f(r) equals 1. In some cases, however, it is possible to define a real number and yet not be able to determine in a finite number of steps whether it is less than 1 or greater than or equal to 1. As a result there is no way to determine whether a 1 or a 0 should be assigned to the number. In Bishop's constructive mathematics it is required that the rule defining a function on real numbers be effectively computable. In other words, for each r it must be possible to construct f(r) in finite number of steps. Hence the step function cannot be defined constructively on real numbers.
The nonconstructive step function defined on all the real numbers is one of the simplest examples of a discontinuous function. Intuitively speaking, a function from the set of real numbers to itself is continuous if the value of f(r) varies continuously, or without jumps. (Heuristically, the graph of such a function can be drawn without lifting a pencil from a piece of paper.) As r varies through 1, the value of the step function f(r) jumps from 0 to 1, and so the function is discontinuous. Since the real numbers are defined in terms of the rational numbers close to them, the value a constructively defined function assigns to a given real number will depend on the values it assigns to nearby rationals. Hence it appears unlikely that it will be possible to constructively define a function on the whole of the real numbers that is not continuous. (Although this observation, which was true of Brouwer's construction of the real numbers, has not been proved for Bishop's, no constructively defined discontinuous function has ever been found.)
Discontinuous functions arise constantly in mathematics, particularly in its applied branches, and so the prospect that only continuous functions can be defined in constructive theory is not pleasing. On the other hand, even in nonconstructive theory it is not possible to apply a discontinuous function to all real numbers. One cannot determine the value of, say, the step function for a given real number until it has been determined which of the sets G or D the number is in. Hence in practical terms this characteristic of constructive functions is less troubling than it might first appear to be.
Because the requirements of constructive mathematics are more stringent than those of nonconstructive mathematics every theorem that is true constructively is also true nonconstructively. (It is possible, however, that two theorems that are distinct constructively might have the same nonconstructive interpretation.) Therefore constructive mathematics could be considered to be simply a branch of modern mathematics. Alternatively, every nonconstructive theorem can be made constructive by adding "assuming the law of the excluded middle" to its statement. Or non-constructive proofs can be reinterpreted constructively. For example, consider the constructive meaning of a nonconstructive proof that there exist irrational numbers a and b such that the number ab is rational.
The proposition is proved nonconstructively as follows. The number \/2 is irrational, and the number \/2\/2 is (by the law of the excluded middle) either rational or irrational. If \/2\/2 is rational, then obviously the proposition is proved by the example in which a equals \/2 and b equals \/2. On the other hand, if \/2\/2 is irrational, then the proposition is proved by the example in which a equals \/2\/2 and b equals \/2, because (\/2\/2)\/2 equals \/2\/2\/2, which equals \/22, or 2. (This is a particularly interesting proof because unlike many pure-existence proofs it appears to come close to generating an example. To actually obtain the example, however, it would be necessary to know whether \/2\/2 is indeed rational or irrational.)
What does the proof show constructively? To begin with, it indicates that trying to prove the proposition that for any irrational numbers a and b, ab is irrational is a waste of time. One can show constructively that this task is hopeless by assuming that the proposition is true. In that case \/2\/2 must be irrational, and by the same reasoning (\/2\/2)\/2 or 2, must be irrational, an obvious contradiction. Hence the proof shows constructively that it is not the case that for all irrational numbers a and b, ab is irrational.
Bishop predicted that once the advantages of his program became clear, modern mathematics as it is currently practiced would cease to exist as an independent field, becoming instead a branch of constructive mathematics. The Foundations of Constructive Analysis is now out of print, however, and in the 12 years since its publication there has been little sign that such a transformation is taking place. Although the number of mathematicians practicing constructive mathematics has been slowly increasing, for the most part mathematicians have seen little reason to change the fundamental ways in which they work. In spite of the unresolved problems at its foundations modern mathematics is extremely successful, and it is not even clear that the constructivists' charge that the subject lacks real meaning is valid. After all, the utility of mathematics in the real world is undeniable. To many applied mathematicians this issue that Albert Einstein called a "frog-and-mouse battle among the mathematicians" seems totally irrelevant. Moreover, the major problems that determine the development of mathematics are usually highly intuitive, so that the subject never drifts too far from "reality." The widely held belief that abstract mathematics is more than a meaningless game would appear to be well founded. Even if there is never to be a constructive revolution, however, the future for constructive mathematics as a vital mathematical discipline seems secure. The current surge in the production of constructive results has shown that in some cases there are substantial advantages to tackling problems from this point of view. Not only can new and sometimes deeper insights be gained but also the resulting theorems are generally more useful. For instance, when the existence of a certain number has been proved constructively, that number can be computed, often in practice as well as in theory. Bishop has pointed out that modern probability theory includes few general methods for actually computing probabilities, and so now a constructive development of the subject is being carried out, most notably by Bishop's former student Y. K. Chan. Constructive mathematics could surely be profitably employed in many other areas of applied mathematics where it is ultimately more important to provide solutions than simply to show they exist.
The majority of mathematicians are now the product of several generations of formalist training, and that places them in a mental "trap" from which it is difficult to view mathematics objectively. From within this trap mathematical certainty can be called into question only by the discovery of unavoidable inconsistencies inherent in the formal axiomatic system of mathematics. And it is generally believed that although such inconsistencies may exist, they can be corrected by making minor modifications of axioms. Hence the question of whether abstract mathematics has real meaning cannot even be formulated. Mathematicians who find themselves doubting the validity of their subject are generally expected to follow the advice the 18th-century French philosopher Jean d'Alembert gave to those who questioned the calculus: "Go on and faith will return."
The formalist point of view, which allows criticisms of mathematics only in its own terms, has led to excesses on both sides of the constructivist controversy. In particular the unfounded belief that constructivism is a cancer that would destroy mathematics has prevented the systematic treatment of tangible existence. It may be impossible to convert every pure-existence proof into a constructive proof, but often it may be feasible to start from a point where tangible existence has already been established and build from there. On the other hand, it is misleading for constructivists to categorically reject pure existence, which does imply the constructively valid notion that it would be contradictory for something not to exist.
It is generally supposed that mathematical ability comes from the human mind's capacity to blend intuition and reason. The vitality of mathematics springs mainly from intuition, however, which formalism tends to devalue. Indeed, in the finished product of mathematics it is not uncommon to find that all signs of intuition have been removed. A proper consideration of constructivism could restore a more appropriate balance between intuition and reason. Moreover, to believe that mathematical truth exists independently of man's knowledge of it is an act of faith that most mathematicians enter into unconsciously. The constructivists are beginning to show that much of mathematics can be done without such an assumption.
Published in: Scientific American (Oct. 1979) pp. .
