If one wants to use a short
slogan which hits at the very
centre of mathematics then one
may well say it is the science
of the infinite.
Hermann Weyl.

The Constructive Revolution
Pat Hughes

Does anybody (God excepted) really know what infinity is? Can any finite being really comprehend infinity? We must surely be careful to justify any assumptions we may make about the infinite.

For example, suppose we happen to have a countably infinite stack of cards (i.e. one card corresponding to each natural nunber) and that each card has a coloured spot on its underside. If we have the patience and the longevity to spend turning them over one at a time to look at these spots, will we ever be able to say with certainty one of the following:

A There are no cards with a blue spot.
or
B There is at least one card with a blue spot?

You will agree (I hope) that we may.not necessarily ever be able to make either one of the statements A or B truthfully, since we could conceivably go on and on turning over red, yellow or green cards without ever actually coming across a blue one. In that case why is it traditionally assumed that the statement "A or B" is true (Either there are no blue cards or there is at least one)? Can you give one good reason why it should be true? To satisfy common sense? ('Common sense is a deposit of prejudice laid down in the mind prior to the age of eighteen' - Albert Einstein). Common sense is the same thing as 'experience', and what experience can we finite beings possibly have of the infinite? Just because we can make certain 'verifiable' statements about a finite pack of cards, we are not qualified to make the same assertions in the infinite case. Since the process of inspecting the elements of an infinite set one by one can never be completed we are not entitled to assume the results of such an inspection.

The principle which most mathematicians have assumed either implicitly or explicitly, and by which they justify themselves in this, is called the principle of the excluded middle (PEM) which roughly states that: any given (finite or infinite) set either has an element or else it does not. In the preceding paragraph I have argued that we are not justified to assume IPEM (the infinite part) unless we are prepared to let mathematics be just an abstract game with no relevance to the real world - and even then we still run the risk of meeting contradictions.

So we throw out IPEM.

Is anything left? And if so, can we be sure that there are no other dubious 'Principles' which are even harder to pinpoint? We have to become constructivists and insist that:

Nothing can be claimed to exist unless and until it has been constructed;
i.e. Existence <==> Constructibility
(previously we had only one-way implication).

If we stick to this definition of existence rigorously then we can never make unjustifiable or questionable assumptions, since in assuming that something exists we imply that it has already been constructed, so we can actually demonstrate its existence. We cannot say that 'There is an even prime' without adding immediately '2 is an even prime'.

Bonus 1. We no longer have to turn a blind eye to the traditional antinomies uncovered by the set-theoreticians (Russell's paradox and the like). Inconsistencies cannot exist by definition.

Bonus 2. The infamous axiom of choice goes the same way as IPEM.

The only exceptions to our basic rule that we permit are that we assume the notions of 'integer' and 'mathematical induction' to be clear, natural and not open to question as being representative of the real world. (Can we say the same of Zernelo's set-theoretic axioms?) Now we have a foundation for our constructions and proceed to rebuild mathematics step by step.

We define a set by describing exactly how one may construct an element of it, and how we may show that two given elements are equal. As before we construct the set Z of all integers, define cartesian products of sets, construct the rationals, order them, and evolve simple arithmetic. Which brings us to the real numbers. Classically a real number x in R is defined as an equivalence class of cauchy sequences of rationals. This is not good enough, as we now cannot define an equivalence class without specifying a particular sequence which belongs to that class, and if we are going to do that for each x in R we might as well define x to be the sequence itself and forget about equivalence classes. However, to define a cauchy sequence we have to produce not only a sequence {xn}, n in Z, of rationals, but also a sequence {Nk ; k in Z} of integers such that:

| xm - xn | <= 1/k for all n, m belonging to Nk.

This is very cumbersome and would make real number arithmetic harder than necessary. We use the concept of a 'regular' sequence instead, and define a real number x to be a sequence {xn}, n in Z, of rationals such that, for all m, n belonging to Z:

| xm - xn | <= 1/m + 1/n

xn is called the nth rational approximation to x (we show later that |xn - x | <= 1/n). We can now perform real arithmetic by manipulating rational aproximations to real numbers.

We define two real numbers {xn} and {yn} to be equal if, for all n in Z:

| xn - yn | <= 2/n

We can show that this is an equivalence relation on R. Define:

x + y = {x2n + y2n} = {zn}, where zn = x2n + y2n, (n = 1 to infinity)

The sequence z = {zn} is a real number since

{ zm - zn } = | x2m + y2m - x2n - y2n |
<= | x2m + x2n | + | y2m - y2n |
<= 1/2m + 1/2n + 1/2m + 1/2n
= 1/m + 1/n

z is well defined (i.e. (x,y) ---> x+y is a function from RxR to R).

Multiplication is a little more tricky and is done by associatlng to each real x = {xn} an integer kx called the canonical bound, such that | xn | < kx for n belonging to Z+. This con be done by letting kx be the least integer greater than | x | + 2. Now, if X and have canonical bounds kx and ky respectively and k = max {kx, ky}, we define:

x.y = { x2kn. y2kn }, n from 1 to infinity
max { x, y } = { max {xn.yn }}
-x = { -xn }
a* = {a, a, a, a .... }, where a belongs to Q
| x| = max { x, -x }
min { x, y } = - max { -x, -y }

Each of these sequences is easily shown to be a well-defined real number. And when you have done that, you can verify that the real numbers obey the same laws of arithmetic as the rationals (assoclativity, commutativity, distributivity, &c.) - cf. (1).

What about an order relation on R? Consider the real number u = {xk}, (k from 1 to infinity), where xk = 0 except if the k-th digit in the decimal expansion of pi is the first of a series of eighty.eight consecutive eights in which case xk+i1 = 1/k0 for all i > 0.

The natural way to define '<=' is so that 0 <= u. However we can't (yet) prove either that 0 = u or that 0 '<' u, so each of these statements is meaningless, since nothing is true unless and until it has been proved. So we have to define '<=' independently of '<' and '=', thus for x, y members of R, define:

y < x (or x > y) <==> there exists N belonging to Z+ such that
for all n >= N, (x - y)n > 1/n

y <= x (or x >= y) <==> there exists N belonging to Z+ such that
for all n >= N, (x - y)n >= -1/n

where (x - y)n is the nth rational approximation to (x - y).

So for the real real numbers the trichotomy 'x > y or x < y or x = y' is invalid. On top of this we have that a non-empty bounded set of real numbers need not have a least upper bound. For instance { k0.xk: k in Z+}, where xk is as defined above,does not have a least upper bound constructively, although classically IPEM shows it to be either 0 or 1.

Never mind - we can get on without these ..... but if I were to write down all the mathematics that has already been translated into constructive terms, I would not only fill this issue of MANIFOLD but many more besides, and I just want to give an indication of a few of the possibilities in analysis alone: convergent sequences and series, absolute convergence, compactness, continuity, differentiation (Rolle's theorem, the Mean Value Theorem, Taylor expansions, etc), integration by Riemann's method (integration as an inverse to differentiation) Cauchy's Integral formula, the Riemann mapping theorem), metric spaces and completeness (Baire category theorem), compactness (leading to the Tietze extension theorem), measure theory (Fubini's theorem etc.), the Hahn-Banach theorem, the spectral theorem, etc .... And the work has only just begun. I should note that these theorems have to be phrased differently to fit in with constructive principles a typical example being Rolle's theorem.

It classically states that if a function f is differentiable on a closed interval [ a, b ] with f(a) = (b), then there exists a point c in [ a, b ] such that f'(c) = 0. The classicist using IPEM claims that the result follows from the demonstration that the assumption of the non-existence of such a point leads to a logical contradiction. But with the constructive definition of existence this claim is not valid. We can, however, construct points where the absolute value of the derivative is arbitrarily small and this result is a sufficiently powerful replacement of Rolle's theorem.

Do you get the idea? Now if you have the slightest niggling uncertainty about accepting the Principle of the Excluded Middle (and even if you haven't). read (1) and then: Join the realist revolution and bring mathematics back to the ground!

Constructivism is for real mathematicians.

Appendix

In constructive mathematics inconsistencies cannot exist by definltlon, since everything that exists has been constructed, and it is impossible to construct a contradiction. So Rusell's paradox must have an explanation. The question is what?

Let's first consider the constructive attitude to negation. By negating a statement we do not in general obtain any statement at all unless it is a positive one (the only way to negate the assertion 'All dodos are dead' is to catch a live dodo - and a handful of tail feathers will not do). Therefore there should be no need to mention negation at all, and we ought to make every concept positive. Bearing this in mind, we define the symbol 'not-a-member-of' by:

a not-a-member-of A if and only if a belongs to A ==> O =1, where A is a set and a an element.

Russell's Paradox
Define w to be the set of all sets which 'do not belong to' themselves,
i.e. w = { x; x is-not-a-member-of x }.
Consider the following two possibilities:

(a) w belongs to itself. Then by definition of w, w is-not-a-member-of w, or in other words, w is-a-member-of w ==>0 = 1
(b) w is not a member of w. Then w satisfies the condition for membership of w, so w is-a-member-of w. But w is not-a-member-of w, so 0 = 1. So w is an impossibility.

How do we explain this constructively? The first thought that leaps to the minds of converted constructivists is of the glaring and direct use of the Principle of the Excluded Middle to make the paradox work. The two impossibilitles (a) and (b) do not necessarily lead to a contradiction. Perhaps w lies in some sort of limbo between the two. In fact, at first sigh, it seems that in taking a way out of the 'contradiction' Russell's paradox gives a direct counter-exmawle to IPEM and completely knocks the bottom out of classical mathematics. The realist case proved at a stroke?

But before we pounce too eagerly we must look at the paradox more closely. Does w actually qualify to be called a 'set' under our definition of the word? And if so is our definition acceptable? Does it actually mean anything to talk about sets belonging to themselves? (Can we talk about sets without seeing them as an inviolable hierarchy of basic elements, sets of basic elements, sets of these sets etc.? So that the relation 'belongs to' is meaningless unless applied to an element and a set of the next order up in the hierarchy). For an analysis of these points, I refer the reader to (1). but I believe the answers should be affirmative. How about the following explanation?

We defined w to be the set of all sets such that x does-not-belong-to x. Remember that constructively nothing is true unless and until it has been proved, so, in order for a particular set s to belong to w we have to have proved already that a belongs-to a ==> 0 = 1. Now as we have only just defined w we cannot have proved anything about it yet, and in particular we have not (yet) proved that a belongs-to a ==> 0 = 1..

Therefore w is different from each of its elements or:
w belongs-to w ==> 0 = 1.

Now we have proved that w does-not-belong-to w. So w joins the collection of the sets x for which x does-not-belong-to x, increasing their number by one. In other words the set {x; x does-not-belong-to x} is now strictly greater than w, and we shall have to call it w1. We have w1 = w union {w}, and w is now no longer the collection of all sets which 'do not belong to' themselves Similarly we obtain,
w2 = w1 union {w1},
w3 = w2 union {w2}
etc.,
giving a whole hierarchy of sets, each of which is strictly greater than the preceding one. It is impossible to pin down {x; x does-not-belong-to x} and the paradox dissolves, unfortunately leaving no conclusions either way about the acceptability of IPEM

BIBLIOGRAPHY
(1) E. Bishop: Foundations of Constructive Analysis.
(2) Stolzenberg: Review of (l) Bull. Am. Math. Soc. 76 no.2.
(3) Fraenkel and Bar-Hillel: Foundations of Set Theory