Reality and Truth in Mathematics

Michael Beeson Department of Mathematics and Computer Science San Jose State University San Jose, California 95192 USA email: beeson@mathcs.sjsu.edu

February 18, 1999

1 Introduction

In the first part of the twentieth century, there was a crisis in the foundations of mathematics, precipitated in part by the discovery of paradoxes such as Russell’s paradox about the set of all sets, and in part by the work of Zermelo, who proved the counterintuitive theorem that every set can be well-ordered.^{1} The usual ordering on the set of real numbers is not a well-ordering^{2}, but Zermelo’s theorem implies that there must be a well-ordering of the reals. Since nobody could find such a well-ordering, the proof was closely examined, and led to much discussion.^{3}

What does it mean to say that a well-ordering of the reals exists if we can’t find one? The discussion of this issue led to Zermelo’s formulation of the axiom of choice, and probably contributed to Brouwer’s development of intuitionism. Brouwer maintained that it means nothing at all to say that a well-ordering of the reals exists if we can’t find one. Other mathematicians, notably David Hilbert, disagreed, and the controversy has never been definitively settled. Instead, what happened was that axioms for set theory, originally developed to clarify the issues involved in Zermelo’s proof, became regarded as the “foundation” of mathematics, so that when mathematicians find themselves wondering or disagreeing about the ultimate meaning of a piece of mathematics, they usually stop arguing when they have seen how to reduce the mathematics in question to set theory. While some philosophers continued to examine the basic issues, most mathematicians preferred to get on with the mathematics. Just to be explicit, here is a list of the “basic issues” in question:

1A well-ordering of a set X is an ordering relation x < y on the set such that (1) it obeys the usual axioms of order, namely: x < y and y < z implies x < z; x < x is impossible; and if x ≠ y then x < y or y < x, and (2) every subset of X has a least element; that is, for every subset A of X, there is an element b of A such that b < c whenever c is a member of A different from b.

2The set of positive numbers, for example, has no least element.

3I do not mean to imply that the “crisis in foundations” began suddenly with Russell’s paradox and Zermelo’s theorem; Cantor had already derived paradoxes in set theory, which he solved by rejecting the Absolute Infinity, and there had been controversies between Kronecker and Dedekind, and between Gordan and Hilbert. But Zermelo’s theorem dealt with the continuum, not some strange sets on the fringe of mathematics, and while it was not a contradiction, it certainly seemed counterintuitive.

• What is real, and how do we know it?

• What does it mean to say a thing exists?

• Can things exist that we can’t know about?

• Can things exist that we don’t know how to find?

• What does it mean to say something is true?

• How can we know whether something is true?

• Can things be true that we can’t ever know to be true?

Within fifteen years of Russell’s paradox and the furor over Zermelo’s proof, L. E. J. Brouwer had given answers to all of the questions above, at least in the realm of mathematics, in his philosophy known as intuitionism. Brouwer’s answers were as follows: What is real, in mathematics at least, is that which can be constructed. What it means to say a thing exists, is that we know how to construct it. Consequently, if a thing exists, we at least know how to construct it, so there can’t be things we don’t know about or can’t find. What it means to say a thing is true is that we have a proof of it^{4}, and that is also the way, and the only way, that we can know a thing is true. Consequently there can’t be true things that we can’t ever know to be true.

Brouwer’s answers were rejected by a majority of mathematicians, along with the philosophical system that supported those answers. For example, Brouwer’s famous opponent, David Hilbert, strongly disagreed with Brouwer about both reality and truth. For him reality did not depend on our constructions. He would have agreed with the statement attributed to Frege, that mathematicians discover theorems in the same way that explorers discover islands. Yet Hilbert’s answer to the last question, engraved on his tombstone^{5}, is the same as Brouwer’s: whatever is true can be proved. While for Brouwer this was a consequence of the meanings of the terms, for Hilbert it was an article of faith.

In spite of their rejection, Brouwer’s ideas continued to draw the interest of some philosophers, logicians, and a few mathematicians, and have not been definitively proved wrong. Now the twentieth century is drawing to a close; and during the intervening decades, there has been relevant scientific and mathematical progress. The question to be addressed in this paper is the following: What, if anything, has twentieth-century progress in physics, mathematics, and logic contributed to our understanding of the philosophical questions listed above?^{6} We will see whether Brouwer’s answers stand up under the light of a century of scientific progress, and what answers, if any, our progress has supplied.

4Proof for Brouwer meant mental construction, not a linguistic or symbolic object.

5His epitaph (see the last paragraph of [47]) is literally, “Wir müssen wissen. Wir werden wissen.” (We must know. We will know.)

To start with, I will list the main achievements of the century which may be relevant, more or less chronologically.

• The development of formal logic and axiomatic systems, by Russell, Zermelo, Hilbert, Heyting, and others

• The reorganization of mathematics along set-theoretic lines, by the Bourbaki^{7} and others.

• The scientific analysis of the notion of “algorithm” by Church, Kleene, and Turing in the thirties

• The understanding of the difference between syntax and semantics, and their connection through the completeness theorem for first-order logic

• Quantum mechanics

• The recursive unsolvability of the halting problem

• The incompleteness theorems

• Tarski’s definition of truth and the related theorem on undefinability

• Kleene’s recursive realizability interpretation

• The independence proofs in set theory

I will set ground rules for the discussion to follow. First, I will assume that there is such a thing as reality; that is, I propose to dismiss the solipsist position without discussion.^{8} Second, as used in this paper, existence is a binary property. Just as you can’t be “a little bit pregnant” or “a little bit dead”, you can’t be “a little bit real”. Either you exist, or you don’t. Third, existence cannot be defined in terms of something simpler. Creation, existence, and destruction are elemental and fundamental.^{9}

6The title of this paper would have a much nicer ring in Dutch: Werkelijkheid en Waarheid in Wiskunde. All three of these words have meaningful overtones: werkelijkheid implies that reality is that which is workable, that with which we can work. Waarheid carries the implication that truth is testable; something is true if we can find a warrant for it, a reason to assert it. And wiskunde, the Dutch word for mathematics, means literally “exact knowledge”.

None of the English words have such rich connotations, and besides, in Dutch the title is alliterative. As it turns out, Brouwer published a Dutch translation of his famous 1908 paper The unreliability of the logical principles in 1919 under the title Wiskunde, waarheid, werkelijkheid. (See the table of contents of [9].) I did not know that when I gave this paper a title.

7The Bourbaki were a group of French mathematicians whose coordinated efforts at writing mathematics in a more formal way were very influential.

8That Brouwer was not a solipsist is evident, for example, from the first page of [8].

Disclaimer: Given the stated aim of the paper, a certain amount of historical discussion is necessary, but I wish to emphasize that the primary subject of this paper is philosophy of mathematics, not its history. A complete history of work relevant to the questions listed above would require a much longer and more scholarly work, and would certainly go back at least half a century before Brouwer, whose work is taken as the starting point here.

Acknowledgements: Boris Kushner, Wilfried Sieg, and Richard Tieszen read drafts of this paper and supplied valuable criticisms, for which I thank them.

2 The meaning of existence

The concept of existence is central to several of the “basic issues”. It is a concept that came explicitly to the fore when Zermelo claimed to prove the existence of a well-ordering that nobody could exhibit. Existence is involved in the Russell paradox, which shows that a certain set R = {x : x ∉ x} cannot exist, although one is surprised by this fact, since its definition seems simple enough until one sees the paradox. Existence is involved in the solution put forth to the paradox by Russell and Whitehead, in Principia Mathematica, which involved building a hierarchy of sets, sets of sets, sets of sets of sets, each one of whose existence could be safely assumed or proved, and which would not include the set R.

Brouwer’s central point was that no sensible meaning could be attached to the phrase “there exists” other than “we can find”, and that therefore mathematics should be done using that meaning, let the chips fall where they may.

Existence is a philosophical issue that far transcends mathematics, and has been considered for millenia by philosophers. It has also received considerable attention in this century from physicists seeking to understand the mysteries of the subatomic world and the origin of the universe, in conditions where the quantum nature of reality is not masked by statistical averages. For example, one of the fundamental questions about existence is whether things that exist, have an existence independent of the mind, or whether the mind is somehow necessarily involved in existence. This question came up in one form in connection with Brouwer’s intuitionism, and in another form in connection with quantum mechanics, and was considered already thousands of years ago. In this section, therefore, we consider the meaning of existence, and specifically, whether and what twentieth-century progress has contributed to our understanding of existence.

9All religions address these three processes. Hinduism in particular gives God three major aspects: Brahma the Creator, Vishnu the Preserver, Shiva the Destroyer.

2.1 Examples

It is not obvious that we always mean the same thing when we use the word “existence” or the words “there exists”. Consider the following examples, and ask yourself what it means for these things to exist: tables, chairs, and beer mugs; electrons; fields (as the electromagnetic field); space (not “outer space”, but the space in which things are placed and located); wave functions; abstractions like justice, truth, beauty; Ideas in the Platonic sense; minds and “I”; God.

In the realm of mathematics, ask yourself what it means for the following things to exist, and whether it means the same thing in each case: integers; functions from integers to integers (sequences of integers); real numbers; sets of numbers; infinitesimals and non-standard reals; measurable cardinals; the set or class of all sets (the “set-theoretic universe”).

Commonplace objects like tables, chairs, and beer mugs seem to exist because they are tangible, i.e., they produce sense-impressions. The philosophical view known as naive realism says that reality is that which corresponds to our sense-impressions.^{10} This view would require us to reject as unreal (that is, nonexistent) all the other items in the list. Electrons, for example, cannot be sensed directly; their existence is inferred from their effects on measuring instruments. But in appropriate experiments, we can determine their size, shape, mass, diameter, and electrical charge, which enables us to form a good mental model of “an electron”. Even so, their existence is not quite on the same footing as tables, chairs, and beer mugs, because according to physics, any two electrons are absolutely interchangeable. If someone sneakily switched your electron for another one while you weren’t looking, you couldn’t tell, and not just in practice, in principle you couldn’t tell. This seems to run counter to our intuitive feeling that when a thing exists, it can be distinguished from the rest of the universe. Nevertheless, nobody denies (nowadays at least) that electrons exist; we seem to feel that anything with a long list of properties must exist–something must be there to have the properties.

When we come to fields, such as the electromagnetic or gravitational field, opinion may not be quite unanimous. Some may insist that the gravitational field is merely a mental construction, a figment of the imagination. In our minds, we assign a number to each point in space, and we call that the gravitational field. On the other hand, according to Einstein, the field has mass and attracts other matter, just as an electron does, and exerts its effects on measuring instruments. Quantum theory has shown us that the truth is more complicated: neither fields nor the particles which “carry the field” can exist without the other! The photon is the carrier of the electromagnetic field, for example, and the graviton is the carrier of the gravitational field. Even though no graviton has ever been detected, every physicist believes gravitons exist and are every bit as real as photons. The classical field has been shown not to exist after all; it was only a figment of our imaginations used in an approximate theory.

10For a classic refutation of naive realism, see Russell[50].

While the classical field has been shown not to exist in my lifetime, on the other hand, the quark has been shown to exist. While I was a student in the 1960’s, quarks were regarded as mathematical fictions that could never be observed. Now they are as real as electrons [41].

Moving further down the list, unanimity of opinion breaks down completely: there are dozens of opinions about the nature of the existence of “I”, including the Buddhist position that the “I” does not really exist^{11}, and the Hindu position that it does not exist separately from God.^{12} Other fundamental questions on which there is no unanimity are: whether the existence of the “I” is independent of the existence of the body, and whether God exists.

In the mathematical universe, there is a similar progression from the familiar and concrete things, whose existence is universally recognized, to the “fringes”, where unanimity breaks down, but the issues of existence are nevertheless significant ones. Kronecker made the famous remark that “God made the positive integers, the rest is due to man.” This seems to symbolize the fact that the integers are “almost tangible.” Although of course they are not sense-objects, we seem to have direct mental experience of the positive integers. It is now an elementary exercise to construct the negative and then the rational numbers from the integers, so the next question of existence is the sequences of integers. Here there is already a divergence of opinion: must a sequence be given by a rule, or can it be determined by an arbitrary set of pairs ⟨n, m⟩ provided we can prove single-valuedness (only one m for each n)? Cauchy showed us how to construct real numbers from sequences of rationals, so the existence question for sequences of integers is the same as for reals. Sets of numbers can certainly be determined by a defining property, but do there exist sets of numbers without any defining property? This is one of the questions on which definite progress has been made in this century, as we will see below.

Non-standard and infinitesimal reals, which were used at the end of the seventeenth century by the founders of calculus, were resuscitated and placed on a modern footing by Abraham Robinson. But most mathematicians probably feel that they don’t really exist. They take a view much like the view that gravitational fields don’t really exist; these numbers are mental creations, figments of the imagination. True, you can use them, but they aren’t real in the same sense as π. A good theory of mathematical existence should offer tools to answer this question: do infinitesimals exist, or not? It seems that hardly anyone is willing to defend their existence (see [44],[45] for one; see also [49], page 267ff) but I haven’t heard a convincing disproof.

11For example: “Know that there is nothing which is not a reflection, there, yet nothing.”

[38], p. 357. The various branches of Buddhism take different positions on some fundamental ontological and epistemological issues, so the statement in the text is not only an oversimplification of a complex position, but as soon as one tries to elaborate it, it becomes controversial.

12“This is the truth: the sparks, though of one nature with the fire, leap from it; uncounted beings leap from the Everlasting, but these, my son, merge into It again.” (Mundaka-Upanishad, Book 2; p. 52 in [55]. This account may make it seem as if the “countless beings”

have a separate existence, but there are hundreds of passages with this sense: “God lives in the hollow of the heart, filling it with immortality, light, intelligence.” ([55], p. 66)

Measurable cardinals and other, even more esoteric, large cardinals, cause the same kind of breakdown in unanimity of opinion that religious issues do. There is no majority opinion and most people agree not to discuss these things at the dinner table.

2.2 Properties of Existence

Is it possible to say anything sensible about the meaning of existence, that would cast some light on the examples above, and give us some tools for analyzing these questions? In view of the intractability of these problems over the past centuries, even a little progress would be interesting. Since, as mentioned at the outset, it is not possible to define existence, let us begin by enumerating some of its properties.

We can’t speak meaningfully of existence without saying something exists. We are isolating or selecting some “thing” (or concept, idea, etc.) and saying that it is an entity. The idea is similar to that put forward by the Gestalt psychologists. Nearly everyone has seen those images which can be viewed in two different ways, for example as a vase or as two faces.

We then have to distinguish:

• specific existence: this dog “Harley” exists

• general existence: dogs exist, ghosts exist

In both cases, to make the claim clear, we have to

(a) explain what it means to be given the, or one of the, things whose existence is asserted. What does it mean to be given (presented with) a dog? a ghost? This much is necessary to make the proposition “X exists” meaningful. We must also explain

(b) how to recognize something as an X, which generally will involve knowing what you can do with or to an X. (It’s a dog if it has a certain characteristic appearances and behaviors; but note that no one such characteristic is absolutely essential, e.g. there are three-legged dogs, hairless dogs, dogs that don’t play Frisbee, etc.)

Now, to establish it as true that X exists, or X’s exist, we might

(c) produce a specific X (in the case of Harley) or evidence that a specific X has been produced (in the case of aliens, miracles, or subatomic particles for instance)

(d) show how to produce an X on demand (in the case of subatomic particles but not aliens or miracles). For example, electricity exists because you can get it from a wall socket. Originally it was harder to prove electricity existed.

Let’s test these ideas. Does there exist a monkey that can play Till There Was You on the accordion? It’s hard to imagine what would make us believe in the existence of such a monkey other than seeing and hearing the performance, or the very trusted secondhand report of the performance. The above criteria seem to explain the meaning of this sentence quite adequately.

Now consider the question, “Do monkeys exist?” This may seem at first glance to be a different kind of question. However, in both cases we’re singling out a certain kind of entity; the fact that there is a single word monkey for one kind and no single word accordion-monkey for the other is a linguistic accident (or non-accidental consequence of the relative rarity of accordion-monkeys, but a linguistic phenomenon rather than an essential philosophical difference). If we hadn’t ever seen a monkey, we would want visual proof of their existence just as we now want it for aliens.^{13}

2.3 Non-constructive existence of concrete objects

The point will not be lost on those educated in mathematical philosophy, that the above criteria for existence are closely related to those put forward by the constructivists. As a test case, then, let us try to construct non-mathematical examples of non-constructive existence.

Example 1 : Does there exist an animal which is a dog if Goldbach’s conjecture is true and a cat if not? (Here the only significance of Goldbach’s conjecture is that it is an unsolved mathematical problem.)

Presumably the vast majority of mathematicians will answer yes, such an animal exists. For either Goldbach’s conjecture is true or not; in the former case my dog Harley will do for the animal, and in the latter case my brother’s cat Simon will do.

We can get mathematics completely out of the picture:

Example 2 : Does there exist a dog which is a Dalmatian if global warming is a serious danger and a Chihuahua if not?

This assumes that the proposition “global warming is a serious danger” is well-defined; if you don’t think so, substitute some other well-defined question to which we don’t know the answer. Now, I asked several non-mathematicians this question, and they all said, of course not. What a silly question! Of course, we don’t have to take their opinion seriously, perhaps they are the same people who think aliens exist. But the essence of their opinion seems to be that in Example 2, two dogs exist, one of which has the desired properties but we don’t know which one. It is the fact that the question asks about a dog which makes it seem nonsensical; and when the meaning is untangled, it seems to have no content^{14}, which is why the question is “silly.”

13A surprisingly high percentage of the population does not have such high standards for believing in the existence of aliens! I take this to show simply that these people are neither philosophers nor scientists.

14This disentanglement is related to Herbrand’s theorem [32],[61], page 89, which says that when ∃xϕ(x) is provable in classical first-order logic, then there are specific terms t_{i} such that the disjunction of the ϕ(t_{i}) is also provable.

My position is that examples like these show that the concept of existence as used in ∃xϕ(x) when ϕ is a complex property is not a primitive concept. We should consider as primitive, the concept of existence as used in ∃xϕ(x), where ϕ(x) is a property that can be verified on demand of any particular x that is presented.

2.4 Platonism vs. Constructivism

It is the thrust of this section that the distinction between Platonist and non-Platonist philosophies of mathematics has some subtleties that have been overlooked.^{15}

The preceding principles used the word “produce”. We produce a dog by presenting him for sense-perception, but how do we produce an integer or a set, or an abstraction like justice? To produce such a thing means to present it to the mind. On the modern Platonist view held by Gödel, mathematical objects have an existence independent of the mind, and the mind (or part of it) functions similarly to a sense organ in allowing us to apprehend mathematical objects. This is in contrast to the view of Brouwer, in which mathematics is a series of mental constructions. According to this view, my integers are different from your integers–mine are in my mind, and yours are in your mind.^{16} When I tell you that 4 + 3 = 7, I predict the result you will get by performing certain constructions on your integers. On this view, we can communicate certain properties that our integers have in common, but ultimately we must rely on intuition for the certainty that your integers are isomorphic to my integers.

On the Brouwerian view, we aren’t “given” a mathematical object, rather we are told how to construct it in our own mind. The principle that if X’s exist, we should know what it means to be given an X, is replaced by, if X’s exist, we should know what it means to construct an X (in our mind). On the Gödelian view, mathematical objects are treated just like dogs and cats: we present them to each other for apprehension by the mind. Note that even with dogs and cats the mind, not only the sense organs, is involved: damage to certain neural areas can cause people to not recognize dogs and cats even though their eyes are functioning correctly. We are using dogs and cats here as examples of objects which are not mental constructions, i.e., they have an existence independent of the perceiving mind.

15The section entitled Philosophical Remarks, pp. 332-347 in [24], is recommended to the reader who needs orientation in this long-running debate. In the terminology of that section, Brouwer would be a neo-conceptualist.

16Strictly speaking, the conclusion that my integers are different from yours does not follow so easily: The word in as used in in my mind doesn’t necessarily imply a spatial location; indeed we usually don’t think of integers as having a spatial location. Perhaps the integers I construct are literally the same integers as you construct, even though we do it “in” different minds. The same integers could be in both of our minds. (I am indebted to Amanda Beeson for pointing this out.) However, I believe the conclusion follows by another argument: if we each make a separate act of creation (construction is creation) then the results of those different acts of creation must be different.

Traditionally, the Platonist view of existence is illustrated by considering the existence of abstractions such as justice, rather than by mathematical objects. Let us consider whether the difference between the Platonist and Aristotelian view of existence is the same as the difference between the Gödelian and Brouwerian views. On the Platonist view, an abstraction like justice really exists. The opposite view, which I will call Aristotelian, is that justice is just an attribute of situations; some situations are just and some are not, or some are more just than others. Transferring this question to mathematical philosophy, we can ask whether the set of all even integers (or the property of evenness) exists, or whether evenness is just an attribute of integers, without an existence of its own. The difference between the Gödelian and Brouwerian view is “where” the mathematical objects live: in our minds, or outside our minds? The difference between the Platonist and Aristotelian view is whether properties have an existence of their own. The word “reification” means making an object out of a property; let us call a “reifist” a person who believes this can always be done. A reifist believes^{17} “every adjective is also a noun.” Gödel (and before him Plato, Cantor and Dedekind) were “reifists”, while Aristotle, Kronecker and the early Brouwer were not. On the other hand, Brouwer was a “mentalist”, believing that mathematical objects exist within the mind, and Gödel was by contrast an “objectivist”. Cantor, Dedekind, and Gödel were reifist objectivists.^{18} Brouwer was a non-reifist mentalist, at least in his early papers. Later, when Brouwer introduced higher-order species (species of species), he became a reifist mentalist. The position of Kronecker seems to have been non-reifist objectivist; since he thought God made the integers, presumably they were not in each of our minds separately, but simply apprehended by our minds. So all four possible positions have famous representatives.^{19}

We have to ask why, if these distinctions are meaningful, they have remained unresolved for so long. What experiment could distinguish them? Well, the answer is clear: if we destroy all minds capable of mathematics, do the integers still exist? If so, then the objectivists are right. If not, they’re wrong. Nobody seems to doubt that Mt. Everest would still exist, for example, but the outcome of the experiment about the integers is still in doubt, and in addition to ethical questions, there seems to be a fundamental contradiction in the instructions for the experiment, since after the destruction of all minds capable of mathematics, we still need such a mind to test for the existence of the integers, even if we believe them to exist outside that mind. So here we have a meaningful but untestable distinction. This is definitely philosophy, not science.

17I am indebted to Nathan Hellerstein for this phrase.

18Dedekind was even willing to consider the collection of “all the potential objects of my thought” as an object; he used it to “prove” the existence of an infinite set ([14], Theorem 66, p. 64).

19I could not find a famous mathematician who advocated the position that the integers don’t exist. That is, the reification of the adjective “seven” as in “seven fingers” to the noun “seven” seems to be accepted by all mathematicians. On the other hand, it was pointed out to me by R. Tieszen that some “nominalist” philosophers have made such a claim, e.g. [21], [31].

Note that these difficulties are completely independent of the old “mind of God” objection, according to which the destruction of all (mathematical) minds is impossible because among them is the Mind of God, which contains the whole universe. There are enough difficulties in the theory of existence without considering this one.

2.5 Existence, creation, and destruction

Although existence cannot be defined in terms of something simpler, it may help to examine the processes of creation and destruction, by which a thing comes to exist. We have already said that existence is not partial: a table either exists or it does not exist. But as the table is being created, there is a moment when three legs are attached and the fourth leg is about to be attached, when it is not yet a table; followed soon by the attachment of the fourth leg and the table is born. One might argue that the exact moment of creation is fuzzy: how dry must the glue be before the leg is really attached, turning the table parts into a table? The truth is, though, that it is the concept of “table” that is fuzzy, not the existence.

The moment of creation of a human being is at the heart of the abortion debate. As with the table, it is the concept of “human being” that is fuzzy, not the concept of existence. In mathematics, we have to watch out for the same phenomenon. The Russell paradox, for example, exposes a fuzziness in our concept of class.

3 Existence in mathematics

It is time to return to our theme: the contributions of scientific progress in the twentieth century to the solution of the problems of existence (reality) and truth in mathematics. In the first decades of this century, the relation between syntax and semantics was not yet clear. For instance, there is no discussion in Principia Mathematica of the semantics of the system. Although the main purpose of the work was to establish a consistent framework for mathematics, and the obvious consistency proof (today) is to exhibit a model of the theory, no such argument is to be found in Principia. Another piece of evidence is that the completeness theorem for first-order logic was not formulated in print until 1928.^{20} During the 1920’s, the focus of attention was the decision problem for first-order logic (a primarily semantic question: which formulas are true in all models?) rather than completeness (which adds a syntactic component: which formulas have proofs?) Sometime between 1900 and 1930, the modern distinction between syntax and semantics developed and became understood; it seems likely that it was in the late 1920’s. The historical evidence is not conclusive, but for our present purpose the exact date does not matter.

20See the historical notes in [27], pp. 47-48, which suggest that the 1928 formulation was not yet correct; but see also [56], where it is argued that indeed the question was well-understood at that time.

3.1 Hilbert

Hilbert very well understood that the same axioms might have different models; he wrote Foundations of Geometry [35] putting non-Euclidean and Euclidean geometries on an axiomatic basis, completing the work Euclid had begun. In this book he explicitly exhibited different models for geometry (produced earlier by Beltrami and Klein). His famous dictum concerning proper axiomatizations was that you had to be able to substitute “tables, chairs, and beer mugs” for “points, lines, and planes”, and the reasoning should still be correct if the axioms held. These facts show that Hilbert was by no means ignorant of the distinction between syntax and semantics. Yet, in [36] Hilbert took the position that consistency guarantees existence. For example, there are groups if there is no contradiction in group theory. What Hilbert seemed to take as a definition of existence was later proved as Gödel’s completeness theorem. As a definition of existence, however, it won’t serve. For example, just because there’s no contradiction in the assumption that a measurable cardinal exists, that doesn’t prove that one does exist. After all, there can certainly be different kinds of large cardinals whose existence is mutually exclusive, but each one by itself is consistent. It seems Hilbert just hadn’t thought this through carefully (this had to wait for Gödel and Tarksi), and it shows that the relations of syntax and semantics were not entirely clear in 1904.^{21} Now that we know about the completeness theorem, and the difference between first-order and secondorder logic, and the incompleteness theorems, we can formulate the matter more clearly. Hilbert had in mind systems which are second-order categorical, such as the Peano axioms.^{22} Such axiom systems do in essence define their unique model, so if they are consistent, that model exists. But every first-order axiomatization, strong enough to meet the conditions of the incompleteness theorem, necessarily has other models as well, in which non-standard “integers” occur. Note that Hilbert’s axiomatizations in Foundations of Geometry were second-order axiomatizations; a proper first-order treatment of geometry was eventually given by students of Tarski in mid-century [7]. But the completeness theorem, forging the link between non-contradiction and model existence, is a theorem about first-order axiomatizations, not second-order. So Hilbert was mistaken, if we interpret his “consistency” in the first-order sense, but not if we interpret it in the second-order sense; and at the time, the difference was not so clear as today.

21The history of the development of the modern distinction between syntax and semantics of first-order logic, and the question of what Hilbert knew and when he knew it, are discussed at length in [56].

22“Second-order categorical” means there is only one model of the Peano axioms in which the second-order variables (to which mathematical induction applies) range over all subsets of the model.

Hilbert’s position lives on, however, in the usual interpretation of “there exists” in mathematics when it is applied to an object rather than a mathematical system. When we say “there exists a real number x such that P (x)”, and accept a proof by contradiction, we are saying x exists, because no contradiction follows from its non-existence, i.e., it is consistent to assume it exists, therefore it exists. Technically, the first-order consistency would be that ¬∃xP (x) is unprovable, which is weaker than proving ¬¬∃xP (x). We would be wrong if we tried to prove the existence of a nonstandard integer from the independence of some sentence ¬∃xP (x) in Peano’s Arithmetic. But if we interpret consistency in the second-order sense, Hilbert’s definition of existence by consistency explains the classical interpretation of “there exists”.

3.2 Reductionism

Reductionism is the search for fundamental “building blocks”. This scientific method was the engine of science in the eighteenth and nineteenth centuries. In chemistry it led to the discovery of atoms and the explanation of the structure of matter via the periodic table. It was natural to try a similar approach in mathematics. I am not certain who began this effort, but Dedekind was one of the pioneers [13].^{23} He showed how to construct the real numbers from sets of rationals, and how to construct rationals from pairs of integers. Frege ([23], §72, p. 85) reduced the concept of integer to that of class: The integer 7, according to Frege, is the class of all sets with seven elements. This decreased the number of elementary building blocks to one: sets. Evidently Frege did not believe Kronecker’s attribution of the creation of the integers to God. During the twentieth century’s opening decade, Russell and Whitehead carried the reductionist program forward in [51], adopting Frege’s definition of integers. But as the axiomatization of set theory progressed, and attention was focused on well-founded sets, this particular reduction did not survive, and was replaced by the von Neumann integers.^{24}

The question remains whether these reductions are formal devices or definitions. For example, is the integer 2 really {0, {0}}, or is it really the class of all two-element sets, or neither, but just some indivisible, atomic thing existing without internal structure, being 2 by virtue of its “place” as the successor of 1? Is the rational number 2/3 “really” an ordered pair of integers, or an equivalence class of such ordered pairs? For that matter, is an ordered pair of objects “really” some kind of set, or is the definition of sets as ordered pair just a convenient isomorphism that enables us to reduce the number of “primitive concepts”? I take the position that this question is not relevant to the main issues of truth and reality. Most mathematicians recognize that using one reduction or another is a matter of convenience. Opinion is more divided about the other central reduction, of function to set of pairs.^{25} Here the question is different–the question is whether the two notions really are isomorphic or not. Brouwer took the idea of sequence of integers as fundamental, and developed real numbers from this idea. He was also a practitioner of reductionism, reducing concepts from the rest of mathematics to sequences of integers whenever possible. However, he believed he was really defining the reduced concepts, since their original definitions did not make sense to him.

23Dedekind did this work in 1858, but did not publish it until 1872, according to the preface of [14].

24The von Neumann integers are defined by: 0 is the empty set, n + 1 = n ∪ {n}.

Dedekind, and after him Frege and Russell, attempted the most ambitious reduction of all: the reduction of mathematics to logic. The hard part here is the reduction of infinity to logic. Dedekind’s construction of the integers on a logical basis involved two steps: (1) reification of adjective “seven” to noun “seven”, and (2) reification of adjective “is-integer” to noun “Integers”, the completed totality of natural numbers. Brouwer criticized the latter in his 1907 thesis [9], p. 78. on the grounds that the totality of Dedekind’s thoughts, his Gedankenwelt, “cannot be viewed mathematically, so it is not certain that with respect to such a thing the ordinary axioms of whole and part will remain consistent.” This step was basic to Dedekind’s attempt to reduce mathematics to logic. The fundamental mystery is infinity, and Brouwer thought it to be an irreducible mystery. Logic for Brouwer was merely a linguistic trace of mathematics; mathematics consists in mental constructions; these constructions exhibit regularities which are described by the laws of logic in the same way as the law of gravity describes regularities in the motions of the planets.

3.3 Implications of Kleene’s work for Brouwer’s ideas

Brouwer had several notions of sequence, and it is very instructive to review the reasons why. First, if existence means “we can find”, as it did for Brouwer, then in order that a sequence x_{n} satisfy ∀n∃m(m = x_{n}), the sequence must be given by a law, or as we would now say, there must be an algorithm for computing x_{n}, given n. On the other hand, Brouwer felt that we have a geometrical intuition about the real-number line: to each point of the visible (or visualizable) line, there corresponds a number. Based on this intuition, Brouwer felt that computable functions on the reals must be continuous. That is, an approximation to the output should be computable from an approximation to the input. In other words, any function guaranteed to work on all real inputs must work by computing with approximations to the input. A step function, for instance, is not defined on all real numbers, but only on those real numbers for which we can decide on which side of the step they lie.

25The reduction of the concept of function to that of set (of pairs) was not made by Dedekind or Cantor. During their time the concept of function itself was still evolving. See the discussion in [2], pp. 418ff.

Brouwer couldn’t justify this continuity theorem (called^{26} the “fan theorem”) using only lawlike sequences. There appeared to be a gap between existence justified by “we can find”, and existence as justified by geometrical intuition. He turned to the second criterion for existence we discussed above: when can we say we are given a real number? He thought we could be “given” a real number by a sequence of choices, for example choices made by tossing a die or making an arbitrary decision to determine the next decimal place. Such sequences he called “choice sequences”. Of course, you could make your choices in accordance with a law, so the lawless sequences are a subclass of the choice sequences; but the converse was not obvious. Brouwer claimed to prove the continuity theorem, but his proof involved reasoning about the nature of possible thoughts, and few were convinced.

These issues were greatly clarified in the thirties and forties, when the definition and theory of computable functions were developed, and applied by Kleene and others to the subject of “recursive analysis”. Kleene showed that there is a binary tree in which all recursive paths run out of the tree, but yet there are arbitrarily long paths in the tree. That is, König’s lemma fails in recursive analysis. This implies the failure of the continuity theorems and shows that there really are more choice sequences than lawless sequences. For more details see [2], Chapter IV.

Our interest in the matter here is in the meaning of existence. It seems that the work of Kleene shows that you can’t have it both ways: if you can be “given” a real number by a sequence of choices, as our geometrical intuition suggests, then “for each n there exists an m” cannot mean “we can find m from n by an algorithm”. By accepting the geometric criterion for the existence of reals, we are forced to accept a wider, possibly non-algorithmic meaning for “for each n there exists an m”. Brouwer was well aware of that, although he did not have Kleene’s precise definitions and theorems. What Brouwer did about it, we will discuss below under Existence and the Laws of Logic.

One can use Kleene’s tree to construct a recursive covering of the set of recursive reals in [0,1], which has arbitrarily small measure.^{27} Hence the set of recursive reals has measure zero, even in constructive mathematics, at least with the most obvious definition of measure. There is a direct contradiction between the viewpoint that all reals are recursive and our geometric intuition, which says the unit interval should have measure 1. This is a particularly clear example of a case in which mathematical and logical work has yielded a result of philosophical significance. We can’t have all three of the following:

• every (computable) method is recursive

• ∀x∃yA(x, y) means there is a (computable) method to get y from x • The unit interval has measure 1

26Technically, the fan theorem is about trees; the continuity theorem is deduced from the fan theorem in a 1924 paper [9], p. 286.

27This theorem is due to Lacombe, and was proved independently slightly later by Zaslavskii and Tseitin. A proof and original references can be found in [2], page 69.

Brouwer wasn’t faced with this dilemma directly^{28}, because to see this dilemma clearly, we need the precise definition of computability, and the development of recursive analysis. Our geometric intuition won’t allow us to give the unit interval measure 0. We have to give up either Church’s thesis (every computable method is recursive), or the fundamental constructive explanation of existence as “we can find”.

These facts became known in the 1950’s as the subject of recursive analysis was developed (in parallel in Russia and the West, at that time on opposite sides of the Iron Curtain). It seems that the Markov school took the incredible step of accepting that the unit interval has measure zero. In the West, people simply continued to study formal systems which did not include Church’s thesis as an axiom, saying that Church’s thesis is “problematic”.

If existence means computability, there aren’t enough reals. Brouwer realized that, and invented choice sequences to provide more. But these same choice sequences can occur in the unwinding of quantifiers, e.g. ∀n∃mm = α(n), so existence must go beyond computability. At least relative computability, using the parameters of the formula as oracles, must be involved. Kleene clarified this situation in his book [37], in which he first defined formal systems using function variables for choice sequences, and then gave a realizability interpretation for these systems using what would now be called “Kleene’s second model of the lambda-calculus”. This notion of realizability showed that, in spite of the presence of axioms about choice sequences that contradict Church’s thesis, it is still true that when ∀x∃yA(x, y) is provable, then y can be found recursively from x.

3.4 Set Theory

Ideas about the existence of sets precede and guide the formulation of axioms. In turn, the axioms and theorems proved from them and about them, help to clarify our notions about the existence of sets. At the beginning of the century we had only informal work on set theory, by Dedekind and Cantor, and formal but inconsistent work by Frege. (Russell used Russell’s paradox to show Frege’s system inconsistent in 1903.)

Russell and Whitehead’s axiomatization in Principia was based on an analysis of existence. Classes exist; to be given a class A = {x : ϕ(x)}, we need a propositional function ϕ, which produces a proposition ϕ(x) when given an x. But functions have to be defined on classes, so we need to know that the domain of ϕ exists, before the definition of A makes sense. Therefore, we need some classes to get started with, and for this Russell used the types; essentially one iterates the power set to get the types. Eventually, Russell and Whitehead found themselves forced to assume another axiom, the axiom of reducibility, which they could not justify, so the exercise was a failure in explaining the existence of sets, though it may have been successful on other fronts.

28However, in an article written in 1952 (p. 509 of [9]), he clearly shows awareness of the difficulty that a system of lawlike numbers will have measure zero.

It was against this background that Brouwer formulated his theory of sets, which he called “species”. These sets^{29} were at first essentially determined by functions defined on N^{N}, but later sets of sets of sets were also allowed. You could be given a species essentially by the separation axiom, as the set of points satisfying a given property, but there wasn’t much you could do with a species, except use it to define another species. In particular, there was no good way to define a number set-theoretically, since you couldn’t get a number by defining (for instance) a Dedekind cut as a species.^{30} Brouwer’s notion of set is coherent but impotent.

Zermelo and Fraenkel gave an axiomatization of set theory that eventually became widely used. In essence their axioms say “what you can do with a set” (make more sets according to these rules.) The axioms do not address the question of how we can be given a set; but nowadays the usual justification for the axioms, and the stated “intended model” of the axioms, is the cumulative hierarchy of sets, defined by iterating the power set. This construction depends on a prior understanding of ordinal, so we have to ask how we are given an ordinal. Since an ordinal is a transitive set linearly ordered by ∈, according to von Neumann, we have to know how we are given a set before we know how we are given an ordinal; and we have to know how we are given an ordinal before we can construct the cumulative hierarchy; and we have to do that before we can know how we are given a set. So the notion of existence underlying Zermelo-Fraenkel set theory is circular. But as I said, we don’t discuss this at the dinner table. Presumably the circle is not vicious: it just means that there is some a priori notion of set or ordinal which is required first.

That being the case, Quine set out to give a new foundation to set theory with his axiomatization NF (for New Foundations). This theory is beautiful in its simplicity: it has only two axioms, extensionality and the axiom that {x : ϕ(x)} exists whenever ϕ is a stratified formula. Stratified means that integers (called “levels”) can be assigned to all the set variables in ϕ in such a way that when a ∈ b occurs in ϕ, then a is assigned a lower level than b. The Russell formula x ∉ x obviously is not stratified, so the Russell set can’t be directly defined in NF. Whatever the beauties of NF, there seems to be no underlying “intended model”, other than perhaps the true universe of sets, and nobody has ever been able to define a model, so it is still an open problem whether NF is consistent. The axioms are uninformative for problems of existence: they don’t tell us anything about how we can be given a set. See [22] for more information about NF.

29Brouwer used the word “species” in his review of Fraenkel’s book on set theory ([9], p.

441), so clearly not too much significance should be placed on the difference, if any, between a “set” and a “species”.

30Of course, you can define Dedekind cuts, but you can’t prove they have the properties of the real numbers.

Another, and much more recent, foray in axiomatic set theory is Aczel’s non-well-founded sets [1]. As usual when a new mathematical concept is introduced, most people regard non-well-founded sets as convenient mental fictions, as opposed to the “real” sets, which are members of the cumulative hierarchy. Remembering that complex numbers, the gravitational field, and atoms were once so regarded, perhaps we should pause. What do we have to do to construct a non-well-founded set? How can we be given a non-well-founded set? If these questions can be answered, then they exist, in the same sense as well-founded sets.

3.5 Sets, Classes, and Properties

At the beginning of the century the Russell paradox had just shown the necessity of distinguishing carefully between a property (such as x ∉ x) and its extension (the set or class consisting of things having the property). Clearly it was partly because of these difficulties that Brouwer was led to develop his intuitionistic philosophy, with its leading ideas of mentalism and constructive logic. The exact relation between sets, properties, and the extension of properties was not clear at that time. If membership in a set is considered a property, then every set is the extension of a property; but the Russell paradox shows that not every property has an extension, or perhaps it shows that not every extension of a property is a set. For instance, the property of being a set has the class of all sets for its extension, but this class is not a set, or perhaps it has no extension at all. By mid-century these matters had been clarified considerably, by means of the definition and study of the cumulative hierarchy of sets, the development of both ZF set theory and GB class/set theory, and the understanding of the relations between them. In particular, the understanding that the cumulative hierarchy can be cut off at any inaccessible cardinal, producing a model of ZF which can be extended to a model of GB by considering its power set to define the classes of the model, went far towards determining the present-day philosophical view of the mathematical community, which amounts to this: we’ll use as much of the cumulative hierarchy as we need, and we usually don’t need much of it, so we won’t worry either about just how much more of the cumulative hierarchy there is, or about whether there are any sets not in the cumulative hierarchy at all. This comfortable conclusion seems to have settled the matter in the minds of most mathematicians, leaving only a few philosophers, logicians, and set theorists to poke around the edges.

In the sixties, Paul Cohen introduced the technique of “forcing”, and used it to show that the axiom of choice and the continuum hypothesis are independent of the Zermelo-Fraenkel axioms [12]. Other set theorists followed this lead, and hundreds of long-standing questions were “settled” in the same fashion. The technique extends nicely to all known plausible axiom systems. Some of these results improved our grasp of the facts relevant to questions of reality and truth, for example, the question of whether each set is definable. Models were constructed in which every set is definable (from ordinal parameters–of course parameters are necessary since there are only countably many parameter-free definitions). Other models were constructed in which there are real numbers which are not so definable. The conclusion is that the known axioms of set theory do not settle that matter. The geometric continuum, according to modern set theory, contains a “sea” of reals whose simplest definitions are arbitrarily complicated (e.g. constructed as generic over the cumulative hierarchy up to larger and larger inaccessibles). It is tempting to identify these reals with Brouwer’s choice sequences: from within a given level of the cumulative hierarchy, they appear to be generated by random choices. The non-randomness in their definition is only apparent on a higher level. Indeed, formal theories of lawless sequences turn out to have models constructed by forcing, so precise logical research bears out this intuition.

One result deserves particular mention here: Feferman [17] proved that no set-theoretically definable well-ordering of the continuum can be proved to exist from the Zermelo-Fraenkel axioms, even with the aid of the axiom of choice and the generalized continuum hypothesis. This confirms our intuition that we can’t find such a thing, in spite of Zermelo’s theorem.

3.6 Predicativity

Russell and Whitehead introduced a “vicious circle principle” [51], p. 37, to prevent the paradoxes. They say “the vicious circles in question arise from supposing that a collection of objects may contain members which can only be defined by means of the collection as a whole.” The “principle” is simply that such collections “have no total”, that is, do not exist. On the Platonist view, this principle is nonsensical–why should the possible definitions of an object affect its existence? On the other hand, if we take it seriously, we have to outlaw definitions that might violate the principle, for example all definitions of a set of integers that involve quantification over all sets of integers in the definition. Such definitions are called impredicative. Questions about the validity of impredicative definitions were raised by Weyl and Poincaré long before the paradoxes and Principia. In the twentieth century a thorough metamathematical study of the implications of the predicative position was carried out by Feferman [16], [18], [19]. The upshot of these studies is a clear identification of the portion of classical mathematics that can be proved using predicative principles, and a precise identification of the proof-theoretic strength of predicative formal systems. Space does not permit a thorough discussion of the issues, but see the papers of Feferman just cited.

4 Reality, Truth, and Set Theory

Gödel’s work showed us that existence at higher types is connected to truth at lower types, something we might otherwise never have suspected. But if we use higher types, we can define truth predicates for lower types, and prove the consistency of theories mentioning only lower types, so that we obtain corresponding to a sequence T_{n} of theories of higher and higher types, a sequence of purely arithmetical facts A_{n}, each one provable in T_{n} but not in T_{m} for m < n. This is a philosophically important result, since it shows, or at least suggests, the futility of the non-reifist position. If we give up sets of sets of integers, we’re giving up hope of settling certain questions about integers alone. This refutation of the non-reifist position is not airtight, however, since we haven’t shown that higher types are the only way to prove these arithmetical facts; only that they do prove more arithmetical facts. We will return to this point below.

Even ZF, or any true axiomatization, will still leave you only a recursively enumerable set of theorems, while after Tarski we know that the truth set of arithmetic is much more complex. Turing [60], and later Feferman [15], studied transfinite progressions of axiomatizations, each obtained in a natural way by “reflection principles” asserting the soundness of the previous theories. In this way we can get well beyond a recursively enumerable set of theorems; so more reality can buy more truth in this sense also: knowledge of the existence (of wellorderings) enables the construction of longer progressions of axiomatizations based on the reflection principle, and hence to more arithmetic truths.

Since Gödel emphasized the point, the belief that reality at higher types is directly related to truth about the integers has been widespread among logicians. Let me therefore present some evidence to the contrary. A theorem of Kreisel, Shoenfield, and Wang [40] states that every true sentence of arithmetic is derivable in PA by transfinite induction on some primitive recursive well-ordering of the integers^{31}. So, if we want to know the whole truth about arithmetic, it would be enough to possess the ability to recognize of specific primitive recursive linear orderings whether they are, or are not, well-orderings. It follows from a “basis theorem” due to Kreisel [53], page 187, that any primitive recursive ordering which is not a well-ordering has a Δ_{2}^{0} descending sequence. That is, the descending sequence is itself arithmetically definable, and using only two quantifiers. Therefore, esoteric sets like inaccessible cardinals are not after all necessary for arithmetic truth. Well-orderings seem to be important but it would be enough to know all about countable well-orderings.^{32}

31For those who need a clear statement of the theorem: If R is a primitive recursive binary relation, provable in PA to be a linear ordering on the integers, the schema T I(R) is the collection of all formulae of the form

∀y(∀xRyA(x) → A(y)) → ∀zA(z)

32This is recursion-theoretically sensible as the truth set for arithmetic is Δ_{1}^{1}, while the set of

A philosophically important point about the theorem of Kreisel, Shoenfield, and Wang is that the reduction of arithmetic truth to transfinite induction on primitive recursive well-orderings is not subject to the argument given above for higher-type sets, that perhaps there are other ways to establish arithmetical truth. Indeed, the statements of transfinite induction on primitive recursive well-orderings are themselves arithmetical, so they are among the truths to be established. Therefore, there can’t be any easier way to find out the truth about arithmetic: however we proceed, we will still have to settle which primitive recursive orderings are well-orderings.

There is a technical problem of interest here: What if we use intuitionistic arithmetic instead of classical? We can formulate the conjectures that every constructively true sentence of arithmetic is derivable by transfinite induction on some well-founded primitive recursive ordering. This statement is expressible in various intuitionistic theories, but I believe not much is known about its metamathematical status, except of course that (restricted to negative arithmetical statements) it is consistent with theories that have a classical interpretation. But for example, is it consistent with intuitionistic analysis plus Church’s thesis?^{33}

5 Existence and Physics

Although the primary purpose of this article is to discuss reality (existence) and truth in mathematics, I believe that the fundamental issues of reality and truth naturally extend beyond the bounds of mathematics, and that fundamental insights may be obtained by considering truth and reality in physics as well, if for no other reason than to see what the differences in the analysis may be. Moreover, some concepts, such as space, belong to both mathematics and physics. Finally, I will put forward the view that quantum mechanics has essential implications for the foundations of mathematics.

5.1 The existence of space

Kant thought the nature of space inherent in the nature of mind, but he was proved wrong. In fact, he was proved wrong several times. First, in regard to mathematical space, the development of non-Euclidean geometry shattered Kant’s position. But a Kantian could still retrench, by claiming that non-Euclidean spaces were figments of the imagination, while real (physical) space was Euclidean, and its nature was inherent in the mind. This holdout position was seriously set back by Einstein’s special theory of relativity, which unified space and time, and dealt the death blow by Einstein’s theory of general relativity in 1915.^{34}

primitive recursive well-orderings is Π_{1}^{1}, i.e. definable using one universal function quantifier.

A set is Δ_{1}^{1} if both it and its complement are Π_{1}^{1}.

33One can also ask about the consistency with Church’s thesis and intuitionistic secondorder arithmetic of the statement that the true sentences of arithmetic are those derivable using the recursive ω-rule. The classical truth of this statement is a theorem of Shoenfield [54].

Can we say that space exists? General relativity says that mass-energy structures space. The mathematical description involves assigning 15 numbers T_{μν} to every “point”^{35}. This assignment of numbers is called the “energy tensor.” It seems that in general relativity, space is completely described by the energy tensor, so we have to ask whether perhaps space is just the energy tensor. Certainly when working with relativity, we are “given” a space by being “given” an energy tensor. But the answer to this question is certainly “no, space is not just the energy tensor.” The reason is that we know that general relativity is not a complete description of real, physical space. The energy tensor describes energy by assigning numbers to every point. In reality energy comes in quantum-mechanical swirls rather than precise values at every point. So the question of the nature, and perhaps even the existence, of physical space is still an open question. This seems to be, however, a scientific rather than a philosophical question; or at least, we can expect that the philosophical aspects will become much clearer once a suitable scientific theory is found that encompasses both relativity and quantum theory.

Current theories of quantum gravity require radical revisions in our conceptualization of space, requiring the use of spaces of e.g. 23 dimensions, all of which except the usual four time and space dimensions are “rolled up” to a circle of very small diameter, so we don’t perceive them. The consensus is that the “final” theory will involve quantum fluctuations in the topology of space-time itself. Clearly philosophical ideas about the nature of space will be struggling to catch up to science for some time to come.

5.2 Quantum mechanics and virtual existence

In an experiment often used to illustrate quantum mechanics, electrons are “fired” at a target through a diffraction grating. The diffraction grating can, at least in principle, be reduced to two small, closely spaced holes in a solid plate. The electron must (at least it seems it must) pass through one of these holes to reach the target. We fire a lot of electrons and the target measuring device records where they land. Instead of two piles of electrons, interference patterns (such as you would expect to see when using light instead of electrons) are observed, unless we measure carefully which hole the electron goes through. If we do look carefully at which hole is used, the electrons behave like particles.

34A more generous view of Kant might hold that he only thought that the nature of our everyday immediate experience of space (and medium-sized physical objects) is inherent in the nature of mind. I think modern knowledge of the effects of neurological damage and disease disproves even this claim, but the details are not relevant to the topic of this paper.

35The points in question are points in a mathematical space, not in the physical space itself, so there is no philosophical circularity here.

The upshot is that (when we see the interference pattern) we can’t know the electron’s position well enough to say which hole it went through, and indeed maybe it didn’t really go through either hole, but somehow went through both holes simultaneously. It’s even possible that it didn’t go through either hole, but instead “tunneled” through. (This happens in every transistor, it’s not an esoteric occurrence. The fact that your radio plays music depends on this quantum behavior of electrons.) In other words, it’s not merely that we can’t know its position, it simply is false that the electron at all times has a unique position and velocity. The uncertainty principle is not a matter of epistemology, but of ontology.

Does the electron exist while it’s tunneling? or does it flash momentarily out of existence and then back into existence again?

These questions turn up again in quantum electrodynamics and in subatomic physics, where interactions between photons and electrons, or more generally between any two particles, are calculated by summing over many (usually infinitely many) possible intermediate states. These intermediate states cannot be observed, but in those states neither the original nor the final particles exist, and some other particles may exist that didn’t exist before and won’t exist after the interaction. These are called “virtual” particles. They have a nebulous status: they don’t “really exist” in the sense that they are unobservable–you are never “given” a virtual particle. Moreover, all infinitely many of these intermediate states “happen” at the same time, and make their contribution to the final result. So there is an observable result; it is therefore hard to say that the virtual particles “don’t exist”– how could a non-existent particle produce an observable result?

If some mathematicians are tempted to sweep these difficulties under the carpet as irrelevant to mathematics, the new field of quantum computation should put a stop to that. Algorithms have been developed to speed up various difficult computations by dividing the computations into parts that can be done simultaneously. (This is called “parallel computation”.) In quantum computing, the idea is to get parallel computations performed by the virtual states, so that a single piece of hardware can perform a large number of computations at the same time. A quantum algorithm has been developed to speed up factoring integers, and people are now working to build machines which can actually execute such algorithms, using very thin optical fibers capable of trapping photons in a single quantum state.^{36}

The philosophical moral is that the concepts of existence that we have formed, based on our experience with the world of tables, chairs and beer mugs, and even on our experience with numbers and simple sets, are clearly inadequate to deal with virtual particles. Reality is just more complicated. There is another kind of existence, virtual existence, which is different from ordinary existence. Virtual objects cannot be observed but they can have observable effects. One real object (enjoying the ordinary kind of existence) gives rise to several, even infinitely many, virtual objects, which coalesce into one ordinary object again. According to quantum electrodynamics, this is happening constantly– even the vacuum is seething, it is a sea of virtual particles constantly being created and destroyed. Physicists believe, as mentioned above, that a correct theory of quantum gravity will require the existence of virtual space, that is, intermediate states will have to be summed over all possible higher-dimensional topologies. The roadblock to a successful theory of quantum gravity seems to be that nobody knows how to formulate such a sum.

36See http://p23.lanl.gov/Quantum.html for an introduction to quantum computation, as well as five tutorials and links to reports of current research at Los Alamos National Laboratory and elsewhere.

Schrödinger showed, in a famous thought-experiment, that virtual existence cannot be confined to subatomic objects. He described an apparatus designed to place a cat in a state of virtual existence. More precisely, the initial state is a live cat, and there are two intermediate virtual states, live cat and dead cat, corresponding to the two holes in the two-slit experiment. The final state will be live cat or dead cat, but the apparatus can be arranged so that a box contains two virtual cats, one alive and one dead. When the box is opened, the cat will be in a normal state, either alive or dead, but the result is as unpredictable as which hole the electron will pass through. Mathematically, the two virtual cats are described by a wave function which is linear combination of the live-cat and dead-cat wave functions.^{37}

5.3 Quantum mechanics and the continuum

We have already discussed the difficulties in accounting for the “fullness” of the geometrical continuum by a “number line” composed of computable numbers. Brouwer wanted to allow “choice sequences” to fill up the continuum. These were meant to allow for numbers whose approximating sequences (decimal expansions, roughly) were generated by random choices or by “free choices” of a conscious being. Now, randomness in physical processes arises either from uncertainties in our knowledge of the initial conditions, or from quantum uncertainty. The former (known as “chaos”) is not relevant. Only quantum uncertainty can lead to a truly random physical process.^{38} Also the free choices of a conscious being must, so far as modern physics is concerned, involve quantum mechanical uncertainties. Since the laws of classical physics are deterministic, if human behaviour is not deterministic, then there must be quantum systems in the brain which propagate quantum uncertainties from the microscopic to the macroscopic level. See [46] for speculations as to what these quantum systems might be. In either case, then, quantum mechanics offers the possibility that physical processes may exist that might go beyond the computable. It’s easy to give an example of such a sequence: a Geiger counter measures the radioactive decay of cesium-137 atoms; the next member of the sequence is the number of seconds until the next decay. After every N decays (for some fixed N) we replenish the supply of cesium-137, so that the process is theoretically infinite. It should not be technically difficult to arrange a mapping of these sequences onto the unit interval in such a way that any real number in the unit interval is equally likely to be generated. Then, since the measure of the computable reals is zero, the probability that a quantum process would generate a computable real is zero. All those classical reals that the set theorists love to classify may have physical reality after all.

37For a discussion of Schrödinger’s cat and other philosophical problems associated with the implications of quantum mechanics for macroscopic objects, see [25], pp. 11-15.

38Technically speaking, this is an unproven claim. Perhaps there are classical situations in which the results are not computable. In this connection Kreisel long ago proposed the problem whether, in the three-body problem of Newtonian mechanics, it is or is not a recursively solvable problem whether three spheres with given masses, initial positions, and initial velocities will eventually collide. So far as I know this problem is still open.

5.4 Quantum Set Theory?

Those who have thought about the matter enough to realize that there is no essential difference in kind between the existence of electrons and the existence of integers,^{39} may wonder then whether the naive notions of existence, derived from our experience with tables, chairs, and beer mugs, but inadequate for the foundations of physics, might also be inadequate in the foundations of mathematics. At the present time, titling a paper “Quantum set theory” would probably brand the author as a crank. But who knows what the future may bring? Thirty years ago quantum computing would have sounded equally ridiculous.

5.5 Information Structures Energy

I propose that existence involves energy structured by information. In the case of particles, the information is carried (or described) by the quantum wave function. Mathematical objects are the extreme case in which there is no energy, only pure information. The number 7 consists of information only. Add a small quantity of energy (perhaps in the form of ink and paper) and you can create an instance of the numeral ‘7’. According to the uncertainty principle, anything involving energy E must have a finite lifetime, at least h̄/E. Mathematical objects can be eternal because their energy is zero. Perhaps the quantum vacuum is an example of the other extreme, energy without information.

6 Existence and the Laws of Logic

In mathematics, it is through logical reasoning that we attempt to arrive at the truth about mathematical objects. We would, it seems, like to separate that process from the more fundamental process of constructing or obtaining objects themselves. To draw an analogy, in mathematics we tend to look at the existence of monkeys as one kind of question, and the existence of monkeys that can play Till there was you on the accordion as another kind of question. That is, we first address the question of what the basic objects allowed in mathematics are, and then the question of proving the existence of objects with certain properties is considered. But I maintain that, in mathematics as in life, this is an artificial distinction. For example, the question as to what sets exist (in general) is not philosophically far removed from the question whether a measurable cardinal (a certain kind of set) exists.

39To avoid confusion: the sentence does not say there is no essential difference between electrons and integers. We use different methods to investigate the two, of course, and they have different properties. But we cannot say that electrons are “more real” than integers, or vice-versa.

The plan of first circumscribing a class of objects whose existence is assured, and then regarding the phrase “there exists” as a kind of selection from this class, goes back at least to Russell and Whitehead. When they introduce the propositional function ∃ (page 17 of Principia, volume 1), they say it means “some propositions of the range [of propositions P (x), where the allowed values of x are those for which P (x) is meaningful] are true”. This implies that the range of allowed values is already determined. Indeed, the driving idea of Principia is to circumscribe the “universe” of types once and for all, at the beginning of mathematics.

6.1 Brouwer and the unreliability of logic

Brouwer’s starting point was that “there exists” must mean “we can construct”. But some very basic laws of logic suffice to prove that A ∨ B is equivalent to asserting the existence of an integer n such that if n = 0 then A, and otherwise B. It follows that for Brouwer, to prove ∀x(A(x) ∨ B(x)) is to show how to determine, given x, which alternative A(x) or B(x) holds. Now in case B is the negation of A, we find that the “law of the excluded middle”, A ∨ ¬A, has a non-trivial content, and indeed there are many examples in which we cannot at present prove ∀x(A(x) ∨ ¬A(x)) in a style Brouwer would approve. For example, we do not know whether e^{e} is rational or not, and we don’t even have an algorithm for deciding of a given rational x whether it equals e^{e} or not, so we can’t prove ∀x(x = e^{e} ∨ x ≠ e^{e}), where x ranges over rational numbers.

Brouwer seized the bull by the horns: he declared the law of the excluded middle to be “unreliable”, and set off to develop mathematics without it. Both Brouwer and Hilbert thought that this would result in weaker mathematics. They would surely both have been surprised by the technical results which Gödel obtained using the double-negation translation. This simple translation had to await the development by Heyting of formal rules for intuitionistic logic^{40}.

40Brouwer was an anti-formalist; he felt that symbols were only a means of communication, which carry or suggest meaning, and he felt that no system of formal rules could encompass mathematics. Gödel’s incompleteness theorem should, therefore, not have surprised him at all. Attempting to verify this prediction, I searched Brouwer’s Collected Works for his reaction to the incompleteness theorems, and found that there is not one direct reference to Gödel

Brouwer’s rejection of the law of the excluded middle became far betterknown than his position of mentalism and the resulting restrictions on his mathematical ontology. Although Brouwer’s logic was stimulated by the paradoxes, changing to intuitionistic logic by itself does nothing to stop the paradoxes. The Russell paradox, for instance, can be derived without any appeal to argument by cases. After defining R = {x : x ∉ x}, we then prove R ∉ R directly, from which we conclude R ∈ R. We don’t need to divide into cases according as R ∈ R or not.

6.2 The negative translation

A negative formula is one which does not contain ∃ or disjunction. Classically, ∃ can be replaced with ¬∀¬ and A ∨ B can be defined in terms of conjunction and negation, so every formula has a classically equivalent negative form. The negative translation of a formula is this form, where in addition atomic formulae are to be double-negated.

Once formal rules for intuitionistic and classical logic were both available, it was easy to prove that this translation preserves logical provability.^{41} Hence, every classical proof can be translated into a corresponding constructive proof. In the case of certain axiom systems, notably Peano’s Arithmetic, the translations of the axioms are provable in the constructive system, so every classical theorem of PA has its negative translation provable in Heyting’s arithmetic HA. Since double negations on prime formulae can be dropped in arithmetic (they are decidable), every negative theorem of PA is a theorem of HA. Intuitionistic arithmetic is not weaker than classical arithmetic, a result which surely surprised some people.

6.3 Set theories with intuitionistic logic

Brouwer developed intuitionistic mathematics in a way that used not only a restricted logic, but a different notion of the fundamental mathematical objects, since he put the continuum, filled with somewhat mysterious choice sequences, at the center. This basic approach did not change until the work of Bishop [4]. Bishop kept the restricted logic, but eliminated the choice sequences in favor of a different mathematical development. When Heyting and Kleene formulated their intuitionistic systems, they simply postulated the continuity of real-valued functions (or some equivalent property). This they no doubt considered an improvement over Brouwer, who attempted to justify continuity by arguments about the possible mental processes. Brouwer’s anti-formalist position prevented him from postulating anything at all. Bishop took a different course: he simply restricted his attention to the continuous functions^{42} , and said that if there are any other functions, never mind them, we’re only interested in the continuous ones. This position stimulated the consideration of versions of set theory with intuitionistic logic. Such theories were first constructed by Myhill and by Feferman. Technical results on these theories are described in [2]. The point to be made here is that most of these theories permit some form of the Gödel negative translation, so that the phenomenon persists when higher types are added: using intuitionistic logic alone does not make a theory weaker.

anywhere in the Collected Works (Brouwer rarely refers to anyone). There is the following indirect reference in a survey paper published in 1952([9], p. 508): “[T]he hope originally fostered by the Old Formalists that mathematical science erected according to their principles would be crowned one day with a proof of noncontradictority, was never fulfilled, and, nowadays, in view of the results of certain investigations of the last few decades, has, I think, been relinquished.” This is taken almost verbatim from [10], p. 2, written four years earlier.

41Credit for the negative translation belongs to Kolmogorov [39], who published in Russian.

He also constructed the first intuitionistic formal logical systems. Gödel [29] extended the translation from predicate logic to arithmetic. See [26] for an extension of the result to ZF set theory.

If one takes the idea of rule or operation as primitive, as well as sets, so that for example the union operation exists even though its graph is not a set but a proper class, one can formulate coherent formal systems based on a combination of the lambda-calculus for rules and some axioms of set theory. This was the approach pioneered by Feferman in [20], [2]. Feferman’s set-theoretic axioms are very different from those of ZF. It is possible to create a coherent theory of rules and sets by simply taking the usual ZF axioms, adding a new primitive for rules, and the axioms of the lambda-calculus. The replacement axiom can then be formulated as, the range of an operation on a set is a set. Such a theory has been studied in [3], where various results standard for intuitionistic theories have been proved about it. The point is that the modifications of the axioms of set theory and the inclusion of rules as a primitive are more or less independent changes. Once you have decided whether or not rules are fundamental objects, you still have to make an independent choice about what sets you think exist, at least as far as known formal systems indicate. There is no direct relation between your ontological commitment (represented by set-theoretic axioms) and your epistemological commitment (represented by intuitionistic logic and the use of rules instead of functions).

6.4 Recursive realizability

We usually take it for granted that propositions can be combined by means of the logical operations of conjunction, negation, disjunction, and implication. Classically these operations are defined by their truth tables, but constructively this won’t work. In intuitionism, we can only accept a proposition as meaningful if we know what it means to construct a proof of it. Heyting, following Brouwer, gave explanations of the logical connectives and quantifiers in these terms. These explanations are straightforward for all the operations except ∀ and implication.

42Technically, the functions uniformly continuous on compact sets.

A proof of ∀xA(x) amounts to a method for transforming any x (in the range of the variable) to a proof of A(x). Similarly, a proof of A → B is a means of transforming a proof of A to a proof of B. When Heyting gave this definition, recursion theory had not yet been developed, and “method” was still an informal term. But in 1945, Kleene replaced “proof” by “integer” and “method” by “recursive function”, and the result was the definition of recursive realizability. This provided a new semantics for intuitionistic arithmetic.

The realizability semantics has been extended to almost every constructive formal system; indeed, it is hard to imagine calling a system constructive if it does not permit a realizability interpretation. The realizability interpretation connected the constructive unprovability of the law of the excluded middle to the recursive unsolvability of the halting problem, a thoroughly satisfying connection.

There has been a lot of work in the last twenty years that spun off from the notion of realizability; I refer to category-theoretic interpretations of constructive systems, including the realizability topos, and much work on the extraction of algorithms from formal proofs. Although this work is interesting and satisfying, it does not address the philosophical issues with which this paper is concerned.

6.5 The meaning of implication

Realizability gives us a much better picture of the meaning of intuitionistic logic than we had before it was invented, but the question arises whether the realizability interpretation is the “intended interpretation” of intuitionism (at least of intuitionistic arithmetic). Markov and his school of Russian constructivists took this interpretation at face value, but in the West, in the fifties, only a few logicians were interested in constructive mathematics anyway, and they did not accept the realizability interpretation, both because of doubts about Church’s thesis (is every “method” really recursive?) and because the realizability interpretation seems, like the Tarksi truth definition, to presume that we know the meanings of implication and quantification as applied on the right-hand side of the definition. For this reason, both the truth definition and the realizability definition can only be used to define truth (or constructive truth) in a formal language, not a priori.

Kreisel attempted to revise the Heyting explanation, adding “second clauses” to the definitions of what it means to prove an implication and a universally quantified statement. A proof of A → B would be, according to Kreisel, a method of transforming a proof of A into a proof of B, together with a proof of this fact. For this to be any reduction, we must assume that statements of the form “p proves B(x)” are simpler than arbitrary statements; Kreisel supposed they were decidable. The plan was, to turn this into a precise interpretation by using recursion theory. There were many technical difficulties, but Goodman eventually produced a “theory of constructions” based on this idea. Modern work has connected the theory of constructions with the Frege structures of Aczel.

Although this “second clause” interpretation has sometimes been claimed to represent Brouwer’s idea of the meaning of the logical connectives, in reality Brouwer’s view was rather different. Brouwer explained the quantifier combination ∀x∃y in terms of functions. If x and y are integers, then this means there is a function α that gets y from x. If x is a function itself, then it means that y can be gotten from x by a continuous function. If x ranges not over all integers or functions, but over a species of integers or functions, since species have to be defined as the ranges of functions, it is possible to reduce this case to the former case. Brouwer did not believe that linguistic constructions necessarily corresponded to underlying mathematical constructions, so a priori it might not be meaningful to put an implication arrow between any two propositions. After investigation, though, everything is reduced to functions from integers to integers, which in turn are given by choice sequences. So Brouwer really reduced logic to ontology: all we have to do is explain what choice sequences are, and we will understand intuitionism, logic, species, and all.

A more modern attempt to explain the logical connectives was made by Martin-Löf in his theory of types [42]. The leading idea of this theory is that we construct “types”, which are domains over which quantifiers may range, by certain primitive operations. This idea was present already in Principia Mathematica; but Martin-Löf retains the idea of “operation” as a primitive notion as well. This theory has been of interest both to philosophers and computer scientists. A number of interesting technical results have been obtained, which show the connections of this viewpoint with those of category theory and recursion theory.

6.6 The Dialectica interpretation

When Heyting introduced his formal systems for intuitionism, of course he allowed the construction of A → B from any formulas A and B. The fact that Brouwer did not do so was hardly noticed. One is tempted to speculate that Gödel may have studied Brouwer carefully, because in 1941 he introduced an formal interpretation of intuitionistic number theory which has a remarkable parallel to Brouwer’s views.^{43} This interpretation, which is called the Dialectica interpretation (after the journal in which it was published), presumes that quantifier-free statements are meaningful (even those involving implication); and statements of the form ∃x∀yA(x, y) are meaningful, where A is quantifierfree. Let us call this EA form. Here x and y range over functionals of finite type. Gödel’s idea was to explain the meaning of any compound formula by reducing it to an equivalent one of this form. He gave a recursive definition of an interpretation that does just that. When he presented the interpretation for publication (over a decade after he invented it), it was presented as a purely formal reduction of an intuitionistic theory with all the usual connectives, to a quantifier-free target theory. Each formula A has a translation in EA form, ∃x∀yA^{∗}(x, y). The theorem is that if A is provable in finite-type arithmetic, then for some term t, A^{∗}(t, y) is provable in Gödel’s quantifier-free theory T.

43I could find no evidence for or against this speculation. However, there is some evidence, in a lecture Gödel gave in 1938, that he was influenced by Hilbert and Ackermann’s work on functionals of higher type. See [52] for details and references.

To carry out the reduction of formulas to EA form, Gödel had to use a few logical principles that are not constructively derivable, so it is not the case that A is provably equivalent to its translation ∃x∀yA^{∗}(x, y). This does not interfere with the translation’s soundness as stated above, but it probably made Gödel reluctant to advance the interpretation as an explanation of constructive meaning, and perhaps accounts for the delay of over a decade in publishing the work, although of course this is only speculation. No such reservations did Errett Bishop have in the late sixties, when (in [5]) he independently rediscovered the Dialectica interpretation and advanced it as an explanation of constructive meaning. Bishop’s paper was not widely read, and few people realize that the Dialectica interpretation is a candidate for a fundamental philosophical definition of the meaning of the constructive logical connectives. This interpretation is, in my opinion, quite close to the original intentions of Brouwer. It is interesting that similar notions were outlined by Brouwer, made metamathematically precise by Gödel, and rediscovered by Bishop.

7 Conclusions

In this section, we will take the basic issues listed in the introduction one by one, and consider them in the light of the scientific progress discussed above.

What is real, and how do we know it? Brouwer answered, that which can be constructed, and we know it by constructing it. The developments of recursive analysis have given the lie to this: we know that lots of non-constructive real numbers must exist to fill up the geometric continuum. Bishop has skillfully papered over this difficulty so that we can, if we like, just not mention these non-constructive real numbers, but by considering only continuous functions, we make sure that our functions are defined on the non-constructive reals that we don’t mention. By defining measures in terms of functions, and restricting functions to be continuous, the evil conclusion that the unit interval has measure 0 is avoided ([6] contains the definitive treatment, improving on [4]). But what does Bishop think is filling up the unit interval? This question will be answered below.

What does it mean to say a thing exists? Brouwer answered, it means that we can construct it. His choice sequences were only “potential infinities”, not objects that could be said to exist; but existence in the context ∀n∃mα(n) = m means that “choices” are allowed as “constructions”. The many results on realizability show us that it is at least consistent to think that the real numbers are the only source of non-constructive existence.

Can things exist that we can’t know about? Brouwer said no, because things exist only if we can construct them in our minds. But the real numbers constructed by forcing techniques must give us pause. These seem to be perfectly acceptable choice sequences; indeed forcing can be used to construct models of theories of choice sequences. Fixing a model of set theory, then, there are plenty of reals that we can’t know anything about “within that model”. This is somewhat incoherent, as we know in our minds, rather than within a model of set theory. But it shows that there is a transfinite sequence of more and more recondite real numbers, more and more “generic” if you like.

Another way of expressing the matter is this: Viewed from within a fixed axiomatic theory, most reals are “generic”. Strengthening the theory (by adding more true axioms) will “precipitate” some more reals from the “sea of genericity”, so you will be able to distinguish them by their properties. But most (“almost all”) will remain generic.

Taking up the defense of the constructivist point of view, we might maintain that these numbers don’t exist, because they are never completed. They represent not a single construction, but an infinite series of constructions, and hence they don’t exist. We may then answer the question asked above, “what does Bishop think is filling up the unit interval”? The constructivist must maintain that the unit interval is filled up with non-existentent potential infinities. The vast majority of members of [0,1] do not exist, because we cannot construct them, but because we can construct arbitrarily long partial Cauchy sequences, they “might exist”. This position is not absurd. Indeed, it sounds a lot like the position of mainstream physics, that the vacuum is seething with virtual particles that don’t really exist either. But it does require conceiving of sets having members that don’t exist. Certainly no present-day formal theories allow for that.

Can things exist that we don’t know how to find? For example, a wellordering of the reals, or a uncountable subset of the reals which is not in oneone correspondence with all the reals? While we may be no closer to unanimity on this question than we were in 1905, we understand the ramifications much better. Indeed, we seem to have a choice in the matter: we can take Brouwer’s meaning of existence, in which case his answer is valid, or we can take Hilbert’s, which the Gödel negative translation has shown can be defined in terms of Brouwer’s. We just have to be careful not to mix, in the same context, two different meanings of “existence”.

As computer assistance in mathematical problem-solving is becoming more commonplace, the interest of the mathematical community in proofs that supply algorithms is increasing. For example, invariant theory, which was a “hot topic” in the nineteenth century, languished for most of the twentieth, but recently it has been revived, and a book has been published with the title Algorithms in Invariant Theory [57]. This is not an isolated incident, as a perusal of any mathematics publisher’s catalog will show. The community presently takes the view suggested above: we have existence, and we have constructive existence. If you can prove constructive existence, that’s better, because algorithms are useful, but very few people regard nonconstructive existence as meaningless. Since the negative translation (and the formal tools to make its formulation possible), it really isn’t possible to maintain that position: classical existence can be interpreted as non-contradictory existence. So Brouwer’s conclusion that classical mathematics is meaningless was off the mark.^{44}

What does it mean to say something is true? Brouwer said that it meant we can prove it. For simplicity let us restrict the discussion to the truth of sentences in the language of Peano Arithmetic. Now, Tarski’s truth definition can be constructively understood, like any other inductive definition. And it has a convincing character: this does seem to be what we mean by truth. Then Brouwer’s claim becomes a conjecture: every true arithmetical sentence is provable. Now, by Gödel’s incompleteness theorem we know that any notion of “provability” for which this would be true cannot be captured in a formal system. But that is what Brouwer believed all along, so one could imagine his reaction^{45}: “Of course.”

To maintain Brouwer’s conjecture requires, in view of the incompleteness theorems, a strong faith in the non-mechanical nature of the human mind. There doesn’t seem to be the slightest evidence in favor of the conjecture; it must be taken as an article of faith.

After a century of technical progress, this is the conclusion: what Brouwer took to be the definition of truth is an unprovable conjecture.

How can we know whether something is true? Brouwer said, the only way is to prove it. This seems to be the common viewpoint of all mathematicians, constructive or not. It is what distinguishes a mathematician from a physicist (who will accept empirical evidence), or from a person of faith (who will accept a revelation).

This hallowed principle of mathematics is undergoing a challenge these days, from some who believe there is room for the experimental method in mathematics. For example, computers have been used to provide evidence for the Riemann hypothesis ^{46} that would be convincing enough for a physicist, showing lots and lots of zeroes on the critical line and none off the critical line, yet mathematicians still aren’t satisfied.

Can things be true that we can’t ever know to be true? Brouwer said no.

44Specifically, on page 510 of [9], Brouwer asks whether a “linguistic application” of classical logic can always be paralleled by “languageless mathematical constructions”, and answers in the negative if the principle of the excluded third is involved. But the negative translation shows that some construction does accompany the use of classical logic.

45Indeed, one must imagine his reaction, since he did not record it.

46The Riemann hypothesis says all the complex zeroes of a certain function, the analytic extension of 1 + 1/2^{x} + … 1/n^{z} + …, lie on the “critical line” Re(z) = 1/2. It is a famous unsolved problem.

But the thrust of the century’s progress is that, however little we like it, there are lots of true things that we aren’t ever going to know. It seems that wellorderings are the key to truth in arithmetic. But how are we supposed to recognize well-orderings, be they primitive recursive well-orderings of the integers, or measurable cardinals? In both cases, we have run out of ideas, and are relying on mere speculations. It seems that a practical limit to arithmetical knowledge has been reached. Even if future generations invent several new kinds of large cardinals, they will just have advanced a few steps down a transfinite road, and will be stuck again. The inscription on Hilbert’s grave (“we must know, we will know”) looks false to us today.^{47}

Chaitin [11] has given a formulation of the incompleteness theorems that makes the limits of our knowledge especially clear.^{48} Chaitin’s formulations of the incompleteness theorems make it clear that the true arithmetical theorems of the formal theories we know and love are just a drop in the ocean compared to all the arithmetical truths, and we don’t have any clear ideas how to extend our theories much further, and even if we did, they would still be formal theories and their theorems would still be just a drop in the ocean of arithmetical truths. Now you might think that “a drop in the ocean” is a gross exaggeration, since the incompleteness theorem says only that there is some true arithmetical nontheorem. Maybe so, and there is certainly disagreement over whether Chaitin’s work has added to the philosophical significance of the incompleteness theorems. But even without Chaitin, there is clear evidence that there are arithmetical truths that we can’t, in any practical sense, ever prove. However little we like it, that’s the way things are.^{49}

47Historical Remarks: Hilbert believed that every well-formulated problem has a solution and will eventually be solved. This is not exactly the same as the question whether whatever is true can be proved, but it certainly implies it. For Hilbert the question had a different meaning than for Brouwer, since Brouwer’s approach involved questioning the meaning of “well-formulated problem”. It is therefore not surprising that Brouwer explicitly repudiated Hilbert’s conviction just mentioned. For example, Brouwer would have denied that the problem of determining whether two given real numbers are equal is solvable. But a specific statement, such as “e^{e} is irrational”, would not be a truth for Brouwer unless we had a proof of it. It was, and still is, the custom in Dutch universities that a thesis is accompanied by some short statements to be defended by the candidate. The last such statement in Brouwer’s thesis ([9], p. 101) is that Hilbert’s conviction is “unfounded.” A exact quotation of, and reference to, Hilbert’s original statement can also be found there.

48Given a polynomial f_{n} of several variables x, depending on a parameter n, let A_{n} be the answer (yes or no) to the question whether f_{n}(x) = 0 has infinitely many solutions in the integers. Chaitin proves that, given a fixed formal theory, such as Peano Arithmetic PA or Zermelo-Fraenkel set theory ZF, there is a polynomial f_{n} such that the sequence A_{n} looks random from within the fixed formal theory. That is, using the resources of ZF, we could not distinguish the sequence A_{n} from the tosses of a fair coin. Morever, in a precise sense, this is true of any randomly selected sequence f_{n}, not just of this special one. Although the formulation in this footnote is not precise, Chaitin’s theorems use precisely defined mathematical concepts.

49This line is delivered with appropriate inflection in the movie Pig, when the young pig learns why certain farm animals are kept even though they do no useful work. The order of the universe was not necessarily established for our convenience.

References

[1] Aczel, P., Non-well-founded sets, Center for the Study of Language and Information, Stanford, Calif. (1988).

[2] Beeson, M., Foundations of Constructive Mathematics, Springer-Verlag (1985).

[3] Beeson, M. Towards a computation system based on set theory, Theoretical Computer Science 60: 297–340 (1988).

[4] Bishop, E. Foundations of Constructive Analysis, McGraw-Hill, New York (1967). The original edition is out of print. There is a revised and extended second edition, E. Bishop and D. Bridges, Constructive Analysis, Springer-Verlag (1985).

[5] Bishop, E., Mathematics as a numerical language, in: Kino, A., Myhill, J., and Vesley, R.E. (eds), Intuitionism and Proof Theory: Proceedings of the Summer Conference at Buffalo, New York, 1968, pp. 53-71, North-Holland, Amsterdam (1970).

[6] Bishop, E., and Cheng, H., Constructive Measure Theory, Memoirs of the A.M.S. 116, Amer. Math.Soc., Providence, R.I. (1972).

[7] Borsuk, K. and Szmielew, W., Foundations of geometry: Euclidean and Bolyai-Lobachevskian geometry, Rev. English translation. [Translated from Polish by Erwin Marquit]. North-Holland, Amsterdam and Interscience, New York (1960).

[8] Brouwer, L. E. J., Volition, Knowledge, Language, in [9], pp. 443-446.

[9] Brouwer, L. E. J., Collected Works, Vol. 1, ed. by A. Heyting, North-Holland, Amsterdam (1975).

[10] Brouwer, L. E. J., Brouwer’s Cambridge Lectures on Intuitionism, ed. by D. van Dalen, Cambridge University Press, Cambridge (1981).

[11] Chaitin, G., Algorithmic information theory, Cambridge University Press, Cambridge/New York (1987).

[12] Cohen, P., Set Theory and the Continuum Hypothesis, Benjamin, New York (1966).

[13] Dedekind, R. Continuity and Irrational Numbers (first published in 1872), in Essays on the Theory of Numbers, Dover, New York (1963).

[14] Dedekind, R. The Nature and Meaning of Numbers, (first published in 1887), in Essays on the Theory of Numbers, Dover, New York (1963). Translation of Was Sind und was Sollen die Zahlen?.

[15] Feferman, S., Transfinite recursive progressions of axiomatic theories, J. Symbolic Logic 27 (1962), 259-316.

[16] Feferman, S., Systems of predicative analysis, Journal of Symbolic Logic 29 (1964) 1-30.

[17] Feferman, S., Some applications of the notions of forcing and generic sets, Fund. Math., vol. 56, pp. 325–345, 1965.

[18] Feferman, S., Systems of predicative analysis II: representations of ordinals, Journal of Symbolic Logic 33 (1968) 193-220.

[19] Feferman, S., Predicatively reducible systems of set theory, in Axiomatic Set Theory, Proc. Sympos. in Pure Math. vol. XIII, Part 2, pp. 11–32, Amer. Math. Soc., Providence, 1974.

[20] Feferman, S., Constructive theories of functions and classes, pp. 159-224 in: M. Boffa, D. van Dalen, and K. McAloon (eds.), Logic Colloquium ’78: Proceedings of the Logic Colloquium at Mons, North-Holland, Amsterdam (1979).

[21] Field, H. H. Science without numbers: a defence of nominalism,Princeton University Press, Princeton, N.J. (1980).

[22] Forster, T. E. Set Theory with a Universal Set, Oxford Science Publications, Clarendon Press, Oxford (1995).

[23] Frege, G., The Foundations of Arithmetic, Blackwell, Oxford (1980). English translation of Grundlagen der Arithmetik, original date 1884.

[24] Fraenkel A., and Bar-Hillel, Y., Foundations of Set Theory, North-Holland, Amsterdam (1958).

[25] Feynman, R., Feynman Lectures on Gravitation, Addison-Wesley, Reading, Mass. (1995).

[26] Friedman, H., The consistency of classical set theory relative to a set theory with intuitionistic logic, J. Symbolic Logic 38 (1973) 315-319.

[27] Gödel, K., Collected Works, Vol I, edited by Feferman et. al., Oxford University Press, New York (1986).

[28] Gödel, K., Collected Works, Vol III, edited by Feferman et. al., Oxford University Press, New York (1995).

[29] Gödel, K., Zur intuitionistischen Arithmetik und Zahlentheorie, 1933, reprinted with English translation in [27], pp. 282-295 [30] van Heijenoort, J. (ed), From Frege to Gödel, A Source Book in Mathe-

matical Logic, 1879-1931, Harvard University Press, Cambridge, Mass./ London (1967).

[31] Hellman, Geoffrey, Mathematics without numbers: towards a modalstructural interpretation, Clarendon Press, Oxford, and Oxford University Press, New York (1989).

[32] Herbrand, J., Recherches sur la théorie de la démonstration, Travaux de la Société des Sciences et des Lettres de Varsovie, Classe III sciences mathématiques et physiques, 33, 128 pp. (1930). Reprinted in [33] and translated in [34].

[33] Herbrand, J., E’crits Logiques (J. van Heijenoort, ed.), Presses Universitaires de France, Paris (1968).

[34] Herbrand, J., Logical Writings (English translation of Herbrand 1968 by W. Goldfarb), Reidel, Dordrecht/ Boston/ Lancester/ Tokyo (1971).

[35] Hilbert, D., Foundations of Geometry, English translation of Grundlagen der Geometrie, Open Court, La Salle, Illinois (1971).

[36] Hilbert, D., On the foundations of logic and arithmetic, in: van Heijenoort [1967], pp. 129-138.

[37] Kleene, S. C. The Foundations of Intuitionistic Mathematics, especially in relation to Recursive Functions, North-Holland, Amsterdam (1965).

[38] Klong-chen rab-´ byams-pa, How the samsara is fabricated from the ground of being, translated by K. Lipman, Crystal Mirror 5, 1977, 344-364. Dharma Publishing, Emeryville, Calif.

[39] On the principle of tertium non datur, Mat. Sb. 32 (1925) 646-667 (Russian). English translation in: [30], pp. 414-437.

[40] Kreisel, G., Shoenfield, J., and Wang, H., Number-theoretic concepts and recursive well-orderings, Arch. Math. Logik u. Grundlagen 5 (1960) 371-391.

[41] Liss T., and Tipton, P., The discovery of the top quark, Scientific American, Sept. 1997, pp. 54-67.

[42] , Martin-Löf, P., Intuitionistic Type Theory, Bibliopolis, Naples (1984).

[43] Myhill, J. Constructive set theory, J. Symbolic Logic 40 (1975) 347-382.

[44] Nelson, E. Internal Set Theory: A new approach to nonstandard analysis, Bull. A. M. S. 83 (1977) 1165-1198.

[45] Nelson, E., The syntax of nonstandard analysis, Annals of Pure and Applied Logic 38 (1988) 123-134.

[46] Penrose, R., Shadows of the mind : a search for the missing science of consciousness, Oxford University Press, Oxford/New York (1994).

[47] Reid, C., Hilbert, Copernicus, an imprint of Springer-Verlag, New York (1996).

[48] Robinson, A., Non-standard Analysis, revised edition, Princeton University Press, Princeton (1996). First published in 1966.

[49] Rucker, R., Mind tools: the five levels of mathematical reality, Houghton Mifflin, Boston (1987).

[50] Russell, B., The Problems of Philosophy, Oxford University Press, Oxford (1912).

[51] Russell B., andWhitehead, A. N., Principia Mathematica, Cambridge University Press, Cambridge (1963). First published in 1910.

[52] Sieg, W., and Parsons, C., Introductory Note to 1938a, in [28], pp. 62-85.

[53] Shoenfield, J., Mathematical Logic, Addison-Wesley, Reading, Mass. (1967).

[54] Shoenfield, J., On a restricted [omega]-rule, Bull. Acad. Polon.Sci. 7 (1959) 405-407.

[55] Shree Purohit Swami and Yeats, W. B. (translators), The Ten Principal Upanishads, Faber and Faber Limited, London (1937).

[56] Sieg, W., Hilbert’s Programs: 1917-1922, to appear.

[57] Sturmfels, B., Algorithms in Invariant Theory, Springer-Verlag, Vienna/New York (1993).

[58] Troelstra, A. S. Metamathematical Investigation of Intuitionistic Arithmetic and Analysis, Springer Lecture Notes in Mathematics 754 (1973).

[59] Troelstra A. S., and van Dalen, D., Constructivism in Mathematics: An Introduction, two volumes, North-Holland, Amsterdam (1988).

[60] Turing, A., Systems of logic based on ordinals, Proc. London Math. Soc. 45 (1939), 161-228.

[61] Troelstra, A. S., and Schwichtenberg, H., Basic Proof Theory, Cambridge University Press, Cambridge (1996).