Constructive Mathematics for Beginners Rudolf Taschner, Vienna, Austria (email: rtasch@pop.tuwien.ac.at ) (short version of a talk, given in the series "WISSENSWERTES AUS DER MATHEMATIK" on March 9, 1998) The hero of the story that I want to tell you is the number w = sum_{n in N*} z_n/10**n. The integers z_n are defined to be +1 if from the n-th to the 2n-th decimal place of pi only the digit 3 appears, to be -1 if from the n-th to the 2n-th decimal place of pi only the digit 7 appears, and to be 0 in any other case. As we know that pi starts with the decimal expansion pi = 3.14159 26535..., the first ten integers z_1, z_2, ..., z_10 are zero. Computers nowadays have calculated more than six billion decimal places of pi, and neither blocks of threes nor blocks of sevens appeared of sufficient length that would for any n imply z_n not= 0. The number w therefore is extremely small, at least |w| < 10**6000000000, but nobody knows which of the three cases w = 0, or w > 0, or w < 0 effectively holds. By constructing this number w, Brouwer stressed the difference between potential and actual infinity: We can, at least in principle, calculate as many decimals places of pi as we want, therefore we are also able to fix as many integers z_n as we want - w thus becomes a real number, a member of R, if the term real means: feasible to any arbitrary accuracy epsilon > 0. However, there is not the slightest gleam of hope to gain an overview of all decimal places of pi. But only this knowledge would allow the decision between w = 0, or w > 0, or w < 0. To put it differently: If someone insists that each real number must be either equal to zero, or greater than zero, or less than zero, this person implicitly believes in an omniscience about the infinite decimal places of any fuzzy irrational number [footnote 1] like pi -- which is obviously absurd! In formal mathematics, this absurdity is hidden by harmless sounding axioms. The thesis of this paper asserts that this hiding procedure should be replaced in mathematics courses straight from the beginning by strict constructive, intuitive reasonable methods. The price one has to pay is to reject the tertium non datur -- it is untenable that w = 0 and w not= 0 are exclusive statements. This price in all its consequences seems to be high: Consider for instance the function f: [-2 , 2] -> R which is defined as follows: f(x) = x + 1 + w for -2 <= x <= -1, f(x) = w for -1 <= x <= 1, and f(x) = x - 1 + w for 1 <= x <= 2. This is a continuous function with f(-2) < 0 and f(2) > 0. However, f(c) = 0 for a real c would immediately decide which of the relations w <= 0, or w >= 0 holds: One only has to calculate a rational number r with |c - r| < 1. Rational numbers always can be separated in those less than zero, those greater than zero, and zero. But r <= 0 implies w >= 0 and r >= 0 implies w <= 0 -- an impossible decision by the nature of the number w. Therefore, the existence of the rational number r and a fortiori of the real number c is absurd. Thus, Bolzano's theorem about zeros of continuous functions f: [a , b] -> R fulfilling f(a)f(b) < 0 is not provable within the context of constructive mathematics. With the damage of Bolzano's theorem, one loses also Rolle's theorem, the mean value theorem, the implicit function theorem, etc. -- almost nothing of essential analysis seems to remain. Nevertheless it is possible to justify even introductory courses of mathematics in a constructive framework, and it is confirmed by personal experience in lectures on constructive analysis for future mathematics teachers at the Technical University of Vienna during more than 10 years. There are for instance two constructive substitutes for Bolzano's theorem: one which weakens the assertion, the other which sharpens the prerequisite. As the late Errett Bishop and his colleagues Douglas Bridges, Fred Richman and others demonstrated, these substitutions suffice to save the core of analysis. We first sketch the first substitute: Consider a continuous function f: [a , b] -> R fulfilling f(a)f(b) < 0 and an arbitrary small epsilon > 0. There exists a delta > 0 such that the inequality |x - y| < delta implies |f(x) - f(y)| < epsilon. We then choose numbers c0, c1, c2, ..., cN with a = c0 < c1 < c2 < ... < cN = b and cn - c_(n-1) < delta for all n = 1, 2, ..., N. The union of the rectangles ]cn - delta , cn + delta[ x ]f(cn) - epsilon , f(cn) + epsilon[ is a region which overlaps the graph of f and at least one of these rectangles -- we call it ]c - delta , c + delta[ x ]f(c) - epsilon , f(c) + epsilon[ -- must contain points of the abscissa. The conclusion therefore is: it is always possible to construct an "almost-zero" c with the property |f(c)| < epsilon. The second substitute for Bolzano's theorem is the following: For any continuous function f: [a , b] -> R fulfilling f(a)f(b) < 0 and being locally nonzero it is possible to construct a real number c with f(c) = 0. The property of "being locally nonzero" explicitly means: for any two numbers x and y with x < y there exists a number z with x < z < y and f(z) not= 0. One must regard that f(z) not= 0 implies the existence of a rational number r > 0 with |f(z)| > r (the fact that the assumption f(z) = 0 leads to a contradiction would not suffice). The proof of this substitute follows in the tracks of Bolzano's original arguments, but instead of consecutive bisections of intervals one now introduces consecutive trisections: the first trisection is [a , p], [p , q], [q , b] where p = (2a+b)/3, q = (a+2b)/3 and in [p , q] one chooses a number r with the property f(r) ( 0. Then the original interval [a , b] is replaced by [a , r] if f(a)f(r) < 0 or by [r , b] if f(r)f(b) < 0. It is clear how this procedure goes on and leads to a converging sequence of points, chosen from each of the selected intervals, with the desired number c as limit. Many functions are locally nonzero, for instance real analytic functions, especially polynomials. Therefore the "algebraic" proof of the fundamental theorem of algebra by Gauss remains valid constructively. One benefit of this constructive access to analysis in introductory courses becomes clear from this example: The cornerstones in proofs of difficult theorems predominate. Students gain a feeling of what is really possible in mathematics -- and what melts into the shadow of purely formal reasoning. A second benefit is a deeper consideration of appropriate definitions, as we shall demonstrate with the following example: In formal mathematics, the concept of function is fairly simple: It is an assignment f: A -> B which associates each member a of A with an uniquely determined member b = f(a) of B. This definition goes back to Dirichlet who, as an example, has considered the indicator-function chi_Q: R -> R of the rational numbers: chi_Q(x) = 1 if x is a rational number, chi_Q(x) = 0 if the real number x is irrational. In constructive mathematics, chi_Q is untenable: The assignment chi_Q(w) is fundamentally unattainable. It is not hard to define functions f: A -> B, if A is a countable set of real numbers: in this case, the constructivist interprets A and B as sequences, and the notion of a sequence is well defined constructively. The set Q of numbers p/q with integers p, q fulfilling q > 0 and g.c.d.(p , q) = 1 is such a countable set, and for any natural number n the function fn: Q -> R' with fn(p/q) = q**(-1/n) is well defined constructively. (R' stands for the set of all numbers r = q**(-1/n), q and n ranging independently N*.) Difficulties arise if f: S -> T is defined on an uncountable set S like an interval. According to Brouwer, it is only possible to define functions f: [a , b] -> R which a priori are continuous on this interval [footnote 2]. The underlying idea is the following: A function f: A -> B with a countable set A is the starting point. Let z denote an accumulation point of A (not necessarily belonging to A). f is defined to be continuous at the point z, if for any positive epsilon there exists a positive delta such that for any x and y from A the two inequalities |x - z| < delta and |y - z| < delta imply |f(x) - f(y)| < epsilon. If this condition prevails it is easy to construct an extension of the function f to all accumulation points at which f is continuous -- and this can very well be an uncountable set. The function f: Q* -> Q* (Q* being Q without zero) with f(p/q) = q/p = (q/(p for instance is continuous at each real number different from zero. The antiquated diction, "y = 1/x is not defined for x = 0 because it is not continuous there", is now justified by this definition. It is not hard to prove that the functions fn, defined just above, are continuous at each real number z which is different from all rational numbers and there take the value fn(z) = 0. Just choose the integer r such that r**(-1/n) < epsilon and then fix delta to be the minimum of all differences |z - p/q|, where p ranges the integers and q ranges the positive integers with q <= r. The funny part of this example is the pointwise limit of fn with n->infty: In formal mathematics one gets the Dirichlet-function chi_Q. Within the constructive framework one first gets the function, which is constant 1 at the rational points, therefore trivially continuous at each real z, finally constant 1 at each real number -- far away from the Dirichlet function. This difference is stressed by integration theory: Both in formal and in constructive mathematics, the functions fn are integrable in the sense of Riemann with integral over [0,1] of fn = 0. But the limit n->infty in the formal context leads to the Lebesgue-integral of chi_Q being zero, in constructive theory, however, leads to the Riemann-integral of the constant function 1 being one -- deviating from Lebesgue's dominated-convergence theorem. Although severe differences between the traditional formal mathematics and the constructive access to analysis exist, a responsible lecturer of constructive mathematics may account for teaching mathematics in his way. It is merely necessary to show the students how to switch back to the traditional beaten track: One only has to forget the fuzzy number w -- in other words: to restrict the set R to the numbers described by the usual axioms -- and in a counter-move to consider constructively unfeasible functions like the Dirichlet-function -- in other words: to enlarge the concept of function with all the pitfalls associated with it, as for instance non-measurable functions and in consequence the partition of a ball into finite pieces which can be put together to form two balls of the same size. The decision between formal or constructive mathematics is then left to the students as they please. Highlighting this liberty as early as possible appears to be an essential goal in the teaching of mathematics. Literature: E. Bishop, D. Bridges: Constructive Analysis. Springer; Berlin, Heidelberg, New York, 1985 D. Bridges, F. Richman: Varieties of Constructive Mathematics. Cambridge Univ. Press; Cambridge, 1987 L. E. J. Brouwer: Collected Works I. North Holland; Amsterdam, 1975 A. Heyting: Intuitionism. An Introduction. North Holland; Amsterdam, 1971 R. Taschner: Lehrgang der konstruktiven Mathematik I, II, III. Manz; Wien, 1991, 1992, 1993 H. Weyl: Ueber die neue Grundlagenkrise der Mathematik. Math. Z. 10 (1921), 39(79 Footnotes: 1 If someone should prove a theorem that inferred from the law of calculating pi enough information to decide whether w = 0, or w > 0, or w < 0, Brouwer could choose another number e.g. pi**pi, or pi**e, or e+pi, or ... instead of pi itself. As the pool of (uncountable) fuzzy irrational numbers is larger than the supply of (countable) recursive procedures to gain proves, there is no doubt that Brouwer is on the winning side. 2 Brouwer even asserts that f is uniformly continuous. His argument uses a metamathematical principle, similar to the principle of induction, which substitutes the theorem of Heine and Borel.