Why Anti-Realists and Classical Mathematicians Cannot Get Along

1. The law of excluded middle Most intuitionists claim that classical mathematics is flawed and needs to be replaced with intuitionistic mathematics. In particular, they argue that the use of the so-called law of excluded middle (LEM) is unjustified. L. E. J. Brouwer wrote: The long belief in the universal validity of the principle of excluded third in mathematics is considered by intuitionism as a phenomenon of history of civilization of the same kind as the oldtime belief in the rationality of π or in the rotation of the firmament on an axis passing through the earth. (Brouwer, 1948, p. 94)

For Brouwer, the error underlying classical mathematics is, in part, metaphysical: the “various ways” in which classical mathematics is justified “all follow the same leading idea, viz., the presupposition of the existence of a world of mathematical objects, a world independent of the thinking individual, obeying the laws of classical logic . . .” (Brouwer, 1912, p. 81). He complained about treating collections of mathematical entities as completed totalities: the classical mathematician “introduces various concepts entirely meaningless to the intuitionist, such as for instance ‘the set whose elements are the points of space’, ‘the set whose elements are the continuous functions of a variable’, ‘the set whose elements are the discontinuous functions of a variable’, . . .” (Brouwer, 1912, p. 82). As Brouwer sees things, the divergence between classical and intuitionistic mathematics also has an epistemic dimension: The . . . point of view that there are no non-experienced truths . . . has found acceptance with regard to mathematics much later than with regard to practical life and to science. Mathematics rigorously treated from this point of view, including deducing theorems exclusively by means of introspective construction, is called intuitionistic mathematics . . . [Classical mathematicians believe] in the existence of unknown truths, and in particular Topoi 20: 53–63, 2001.  2001 Kluwer Academic Publishers. Printed in the Netherlands.

Stewart Shapiro

[apply] the principle of excluded third expressing that every mathematical assertion . . . either is a truth or cannot be a truth. (Brouwer, 1948, p. 90)

Brouwer’s student Arend Heyting reiterated the focus on mental mathematical construction: [W]e do not attribute an existence independent of our thought, i.e., a transcendental existence, to . . . mathematical objects . . . [M]athematical objects are by their very nature dependent on human thought. Their existence is guaranteed only insofar as they can be determined by thought. They have properties only insofar as these can be discerned in them by thought . . . Faith in transcendental . . . existence must be rejected as a means of mathematical proof . . . [T]his is the reason for doubting the law of excluded middle. (Heyting, 1931, pp. 52–53)

With his teacher, Heyting argued that classical mathematics relies on a “metaphysical” principle that the truths of mathematics are objective. The only way to avoid “a maze of metaphysical difficulties” is to “banish them from mathematics” (Heyting, 1956, p. 3): If “to exist” does not mean “to be constructed”, it must have some metaphysical meaning. It cannot be the task of mathematics to investigate this meaning or to decide whether it is tenable or not. We have no objection against a mathematician privately admitting any metaphysical meaning he likes, but Brouwer’s program entails that we study mathematics as something simpler, more immediate than metaphysics. In the study of mental mathematical constructions “to exist” must be synonymous with “to be constructed”. (Heyting, 1956, p. 2)

Some decades later, Michael Dummett shifted the debate from the arena of metaphysics to semantics, and to the philosophy of language generally. Starting with Dummett (1973), he argued that any consideration concerning logical principles must ultimately turn on questions of meaning. He thus adopted a (now) widely held view that the rules for drawing inferences from a set of premises flow from the meaning of some of the terms in the premises, the so-called “logical terminology”. Since language is a public medium, the meanings of

54

STEWART SHAPIRO

the terms in a language are determined by how the terms are correctly used in discourse: The meaning of a mathematical statement determines and is exhaustively determined by its use. The meaning of such a statement cannot be, or cannot contain as an ingredient, anything which is not manifest in the use to be made of it, lying solely in the mind of the individual who apprehends that meaning: . . . if two individuals agree completely about the use to be made of [a] statement, then they agree about its meaning. The reason is that the meaning of a statement consists solely in its rôle as an instrument of communication between individuals . . . An individual cannot communicate what he cannot be observed to communicate: if an individual associated with a mathematical symbol or formula some mental content, where the association did not lie in the use he made of the symbol or formula, then he could not convey that content by means of the symbol or formula, for his audience would be unaware of the association and would have no means of becoming aware of it. (Dummett, 1973, pp. 98–99)

This common-sense view of language supports Dummett’s manifestation requirement, a thesis that anyone who understands the meaning of an expression must be able to demonstrate that understanding through her behavior – through her use of the expression: . . . there must be an observable difference between the behavior or capacities of someone who is said to have . . . knowledge [of the meaning of an expression] and someone who is said to lack it. Hence it follows . . . that a grasp of the meaning of a mathematical statement must, in general, consist of a capacity to use that statement in a certain way, or to respond in a certain way to its use by others.

Other pieces of Dummett’s argument against the validity of excluded middle are a requirement that the logical constants be graspable one at a time, independent of each other (separability) and a requirement that there be harmony in the use of each connective. Dummett argues that these considerations have ramifications for the proper meaning of the logical terminology. In the prevailing Tarskian semantics, the truth conditions of a complex formula are defined in terms of the truth conditions of its subformulas. Typically, truth conditions can hold (or not) independent of our abilities to know that they do. This is the source of bivalence and excluded middle. Dummett argues that if the language is undecidable, a semantics like this violates the manifestation requirement. On a classical, bivalent interpretation of a mathematical theory, the central notion is that of truth: a grasp of the meaning of a sentence . . . consists in a knowledge of what it is for that sentence to be true. Since, in general, the sentences of the language will not be ones whose truth-value we are capable of effectively

deciding, the condition for the truth of such a sentence will be one which we are not, in general, capable of recognising as obtaining whenever it obtains, or of getting ourselves into a position in which we can so recognise it. (Dummett, 1973, p. 105)

Dummett claims that verifiability or assertability should replace truth as the main constituent of a compositional semantics. In mathematics, verification is proof. Dummett’s proposal thus invokes the central theme of Heyting semantics for intuitionistic logic. Instead of providing truth conditions for each formula, we supply proof conditions. In rough terms, here are some of the clauses for Heyting semantics (see Dummett, 1977, Chapter 1): A proof of a sentence of the form Φ ∨ Ψ consists of either a proof of Φ or a proof of Ψ. A proof of a sentence of the form Φ → Ψ consists of a method for transforming any proof of Φ into a proof of Ψ. A proof of a sentence of the form ~Φ consists of a procedure for transforming any proof of Φ into a proof of absurdity. In other words, a proof of ~Φ is a proof there can be no proof of Φ. A proof of a sentence of the form ∀xΦ(x) consists of a procedure that, given any n, produces a proof of the corresponding sentence Φ(n). A proof of a sentence of the form ∃xΦ(x) consists of the construction of an item n and a proof of the corresponding Φ(n).

Notice that in this framework, one cannot have a (canonical) proof of a disjunction unless one has a proof of one of the disjuncts. So one cannot have a (canonical) proof of an instance of LEM Φ ∨ ~Φ unless one has either a proof of Φ or a proof that there can be no proof of Φ. So if the language is undecidable, then many instances of LEM are not justified by Heyting semantics. And if this semantics sufficiently reflects the meaning of logical constants, then typical instances of LEM cannot be justified on the basis of meaning alone. So, in general, LEM is not analytic and so it is not logically true. As Dummett puts it, a major presupposition of classical mathematics is that there are, or may be, truths that cannot become known. A truth-valued, bivalent semantics suggests that truth is one thing and knowability another. Dummett’s view, sometimes called global semantic anti-realism, opposes this. The anti-realist holds that at least in principle, all truths are knowable. The possibility of an unknowable truth is ruled out a priori. When the discourse is undecidable, intuitionistic logic reflects this anti-realism.

WHY ANTI-REALISTS AND CLASSICAL MATHEMATICIANS CANNOT GET ALONG

As we saw, the epistemic dimension of Brouwer’s thought points toward semantic anti-realism for mathematics, as well as for “practical life and science”. For Brouwer, “there are no non-experienced truths”. It is common to point out that it is hard to adjudicate the clash between classical mathematics and Dummett’s semantic anti-realism, since the parties to the dispute do not mean the same thing by the logical terminology. The classical mathematician might cheerfully concede that of course excluded middle is not logically true on the intuitionistic (i.e., Heyting-Dummett) understanding of the connectives, but LEM is an obvious, analytic, logical (whatever) truth on the classical understanding. The instance Φ ∨ ~Φ just says that Φ is either true or false – not that Φ is either provable or refutable. What could be more obvious than that? We thus broach the problem of shared content. Prima facie, the intuitionist and the classicist talk past one another, since they do not mean the same things by their (logical) terms. In one place, Dummett (1991, p. 17) puts the problem this way, but he maintains that the classical terms have no legitimate meaning: The intuitionists . . . hold . . . that certain methods of reasoning . . . employed by classical mathematicians in proving theorems are invalid: the premises do not justify the conclusion. The immediate effect of a challenge to fundamental accustomed modes of reasoning is perplexity: on what basis can we argue the matter, if we are not in agreement about what constitutes a valid argument? . . . The affront to which the challenge gives rise is quickly allayed by a resolve to take no notice. The challenger must mean something different by the logical constants; so he is not really challenging the laws that we have always accepted and may therefore continue to accept. This attempt to brush the challenge aside works no better when the issue concerns logic than in any other case. Perhaps a polytheist cannot mean the same by ‘God’ as a monotheist; but there is disagreement between them, all the same. Each denies that the other has hold of a coherent meaning; and that is just the charge made by the intuitionist against the classical mathematician. He acknowledges that he attaches meanings to mathematical terms different from those the classical mathematician ascribes to them; but he maintains that the classical meanings are incoherent and arise out of a misconception on the part of the classical mathematician about how mathematical language functions. Thus the answer to the question how it is possible to call a basic logical law in doubt is that, underlying the disagreement about logic, there is a yet more fundamental disagreement about the correct model of meaning, that is, about what we should regard as constituting an understanding of the statement. (emphasis mine)

55

2. Can we still be friends? No one doubts that classical mathematics has been enormously successful, at least in its own terms, and that classical mathematics is deeply entrenched in the scientific web of belief. 1 Mathematicians are loath to give up successful methods, even in light of (what looks like) cogent philosophical criticism. Some philosophers follow suit. When faced with a conflict between classical mathematics and intuitionistic philosophy, they reject the philosophy, perhaps out of hand. There must be something wrong with intuitionistic arguments – Brouwer’s metaphysics/epistemology and Dummett’s views on language – if they lead us out of our classical paradise. In a similar context, and with characteristic wit, David Lewis (1993, p. 15) wrote: I laugh to think how presumptuous it would be to reject mathematics for philosophical reasons. How would you like to go and tell the mathematicians that they must change their ways . . . Will you tell them, with a straight face, to follow philosophical argument wherever it leads? If they challenge your credentials, will you boast of philosophy’s other great discoveries: That motion is impossible, . . . , that it is unthinkable that anything exists outside the mind, that time is unreal, that no theory has ever been made at all probable by evidence, . . . , that it is a wideopen scientific question whether anyone has ever believed anything, . . . ? Not me!

For his part, Brouwer (1948, p. 90) conceded that classical analysis may be “appropriate . . . for science”. Nevertheless, he maintained that classical analysis has “less mathematical truth” than intuitionistic analysis, since the former runs against the mind-dependent nature of mathematical construction. Brouwer thus proposed a bold divorce between mathematics and the empirical sciences. Other thinkers may be more reluctant to jettison classical mathematics. After all, our philosophical arguments are rarely as compelling as mathematical demonstrations. But of course the issue here concerns just what is (or ought to be) a compelling mathematical demonstration. Heyting’s early (1931) echoed Brouwer’s claim that classical mathematics is flawed and should be replaced with intuitionism: “intuitionism is the only possible way to construct mathematics”. However, his (1956) book is more eclectic, arguing only that intuitionistic mathematics deserves a place “alongside” classical mathematics. The later Heyting did not claim a “monopoly” on mathematics, and would rest content if the classical mathematician “admits the good right of” the intu-

56

STEWART SHAPIRO

itionistic conception. Nevertheless, Heyting maintained that the intuitionist is doing things cleanly and honestly, while the classical mathematician relies on a dubious metaphysical principle. For what it is worth, by the time of Heyting (1956), it was apparent that intuitionism had lost the war for the hearts and minds of mathematicians. Dummett joins Brouwer and (the early) Heyting in having no truck with an eclectic orientation. He is not interested in softening the disagreements, nor in making some space for classical mathematics. Dummett (1973, p. 97) explores the thesis that “classical mathematics employs forms of reasoning which are not valid on any legitimate way of construing mathematical statements . . .”. He thus tells mathematicians that they must change their ways, to use Lewis’s phrase. In a sense, Dummett goes further than Brouwer and Heyting. They “just” accuse the classical mathematician of harboring a false, dubious, or unwarranted metaphysical view. The Dummettian accuses the classical mathematician of incoherence. A serious charge indeed. Perhaps there is a less confrontational stance within the general Dummettian framework. One who buys the thrust of Dummett’s argument might claim that the basic principles of intuitionistic logic enjoy a certain type of justification.2 They are true in virtue of the meaning of the logical terminology – when that terminology is construed in something like the Dummett-Heyting manner. Most instances of LEM do not enjoy this level of justification, and neither do those parts of classical mathematics that rely on LEM. This is not (yet) to say that classical mathematics is incoherent, only to note that parts of it have less justification than other parts. If the classical mathematician accepts this assessment, she would probably go on to claim that classical mathematics does not stand in need of this extra justification. She might patiently point out that mathematics has its own rigorous standards for correct and incorrect proof, and that these have stood the test of time, perhaps thanking the philosopher for his interest just the same. It comes down to personal standards of justification. Notice that even this uncomfortable peace – or mutual tolerance – requires us to somehow finesse the problem of shared content (or else follow Quine and ignore matters of semantic content in contexts like this).

3. Attempted reconciliation Neil Tennant (1996), a prominent Dummettian, proposes a way for classical mathematics to enjoy a level of support and justification, even from the perspective of the semantic anti-realist. Tennant notes that the “realist does not wish to be methodologically deprived”. This realist is “unwilling to give up the strictly classical inferences of classical logic”. If Tennant’s realist is a classical mathematician, this is quite correct. Apparently, classical mathematicians remain unconvinced that their mathematics is broken, and if it ain’t broke, don’t fix it. Tennant resolves the problem of shared content in favor of the Dummettian intuitionist. From the start, he insists “with Dummett, on the manifestation requirement in the theory of meaning” and he advocates a “far-reaching logical reform” (Tennant, 1996, p. 205). For Tennant, “the realist is not entitled to . . . strictly classical inferences” (my emphasis). In particular, there is no coherent meaning for the logical terminology that makes LEM analytic. However, Tennant then tries to spell out “how the realist can be allowed to have his cake but also be asked to improve his manners when eating it” (Tennant, 1996, p. 205). That is, Tennant is out to present an anti-realist take on classical mathematics: “The reforming anti-realist is not so much intent on depriving the realist of his classical tools but, rather, on having the realist acknowledge the true nature of his use of them or of his appeal to them” (ibid., 215). As a Dummettian intuitionist, Tennant holds that most instances of LEM are not true in virtue of the (correct) meanings of the logical terms, disjunction and negation in particular. Thus, most instances of LEM are synthetic (if true). If the classical mathematician still claims to know each instance of LEM a priori, then she must regard most instances as synthetic a priori, thus reviving the status that Kant assigned to most mathematics. Tennant then commends “this Kantian perspective to the realist in order for the latter to make better sense of her own commitment to” classical mathematics. Tennant’s title, “The law of excluded middle is synthetic a priori, if valid” is “in a certain sense, a vicarious claim put forward by the perspicuous anti-realist ‘on behalf of ’ the realist” (Tennant, 1997, p. 212). The issue here is whether the classical mathematician can accept this proposal, adopting the Heyting-Dummett understanding of the logical terminology and then

WHY ANTI-REALISTS AND CLASSICAL MATHEMATICIANS CANNOT GET ALONG

accepting LEM as a necessary, but synthetic (and so non-logical) truth, knowable a priori. Tennant’s proposal is similar to Heyting’s claim that LEM embodies a metaphysical principle, which is not part of mathematics itself. For Tennant, the optional metaphysics is perhaps dubious, but the classical mathematician is free to hold it: [T]he holding true (as a matter of necessity) of every . . . instance [of LEM] (or the holding true . . . of any such instance P ∨ ~P, absent any proof or refutation of P) expresses an essentially metaphysical belief. This belief is that the world is determinate in every expressible regard (or at least, in the case of a particular instance of LEM, determinate in the respects answering to the propositional content of P that is involved). Such a belief is synthetic, since its content cannot be known to be true simply on the basis of the meanings of the logical expressions ∨ and ~. (Tennant, 1996, p. 213, emphasis mine) According to the realist’s principle of determinacy, the truthvalue of any declarative statement is determined by reality in advance of our investigation, and the truth-value could attach to the statement quite independently of us and our beliefs and also independently of our available means for coming to know what is the case. (Tennant, 1996, p. 219)

Tennant has a small favor to ask of the classical mathematician. Once she acknowledges the synthetic, metaphysical nature of LEM, she should note each use of it in proofs, so that “we can always be clear as to how and when the justification of a knowledge claim involves recourse to an essentially metaphysical conception of reality”. Whenever the classical mathematician invokes an instance P ∨ ~P, she “must be prepared to acknowledge: ‘Here I presuppose, or give expression to, the metaphysical view that reality is determinate (in the respect P)’.” This way, the “realist metaphysical outlook can be logically corralled” (ibid., 215). If the classical mathematician makes this explicit acknowledgment, then the Dummettian anti-realist would no longer wish to deprive her of anything. We are all to get along famously, or so it seems. Tennant’s picture, then, is that there is no problem of shared content. Classical mathematics employs the same language as intuitionistic mathematics. In particular, the logical connectives have the same meaning in both discourses, and knowledge of this meaning does not suffice to justify instances of LEM. Contemporary philosophers who maintain an analytic-synthetic distinction thereby also invoke a distinction between sentences true in virtue of meaning and sentences true in virtue of the way the world is. Since the classical mathematician’s insistence on LEM does not have its source

57

in knowledge of meaning, it is the world that is responsible for LEM. This commitment, on the part of the classical mathematician, is expressed in the metaphysical principle that the world is determinate. Language does not underwrite the determinacy; the world does. As Tennant puts it, the classical mathematician, “is making a synthetic . . . claim about reality itself, appropriately aided thereto by the anti-realistically licit meanings that are bestowed on the logical operators” (ibid., 223). Of course, it is accepted mathematical practice to explicitly acknowledge all of one’s non-logical axioms and premises, but logical principles are not usually listed. For example, neither the classical nor the intuitionistic mathematician explicitly notes uses of modus ponens or universal elimination. Typically, the classical mathematician does not list instances of LEM, or the use of equivalent inferences, like double-negation elimination, classical reductio, or classical dilemma. Since, on Tennant’s view, LEM is not a logical truth, it should be listed as an axiom or premise whenever it is invoked. This is a minor revisionism. The classical mathematician does not have to give anything up. She is only asked to acknowledge the (metaphysical) principles in her repertoire. She could even delegate the task of noting instances of LEM to a logician who has nothing better to do. Or we might eliminate the revisionism altogether, by changing (or re-describing) the rule. Instead of “acknowledge all non-logical axioms and premises”, we say “acknowledge all specifically mathematical axioms and premises”. The metaphysical principle underlying LEM is not specifically mathematical, and so does not have to be explicitly acknowledged – except perhaps as a courtesy to any interested intuitionists. On Tennant’s view, then, there is little or no revisionism required of the classical mathematician. All she is asked to do is practice a little logical hygiene and acknowledge the metaphysical principle of determinacy. The intuitionist demurs from this metaphysical principle and from most instances of LEM. Recall that some parts of intuitionistic mathematics, such as Brouwer’s theory of free choice sequences and the theorem that all real-valued functions are continuous (see Dummett, 1977, Chapter 3), are inconsistent with classical mathematics. Call the theory of free choice sequences, and the like, Brouwerian mathematics. The classical mathematician must reject Brouwerian mathematics, but since our intuitionist does not accept LEM, he is free to accept it. Perhaps Brouwerian mathematics is itself based on metaphysical principles concerning the

58

STEWART SHAPIRO

underlying nature of the real numbers. The Brouwerian may claim that these metaphysical principles are synthetic a priori. Apparently, these principles conflict with the classical mathematician’s equally synthetic principle of determinacy. When it comes to metaphysical principles, perhaps, you pay your money and make your choice. Or you can play it safe and stick to those parts of intuitionistic mathematics that are classically correct (following E. Bishop (1967)), adopting neither of the metaphysical principles.

on the proposed plan, the classical mathematician cannot say that LEM is true in virtue of meaning, so the usual justification is blocked. There is some tension, right at the start. Recall how Tennant formulates the metaphysical principle that underlies LEM:

4. It is a rotten deal

This seems to be an outright contradiction to Tennant’s statement of anti-realism: “Truth is knowable and consists in the existence of an effectively checkable construction, or warrant, establishing the sentence in question as true”. One who accepts Dummett’s arguments concerning the meanings of the logical terminology, should accept the anti-realism that flows from those arguments, and so such a person should completely reject the metaphysical principle in question. I see only one resolution to this. Dummett himself concedes that if a discourse is decidable, then LEM holds for it. Tennant’s summary of the Dummettian conclusion is a converse to this: “one cannot hold both to Bivalence and manifestationism . . . for any undecidable discourse”. A discourse is decidable if there is a procedure for determining, of any given sentence Φ in the discourse, whether Φ is true or false. So if a discourse is decidable, then for any sentence Φ in the discourse, either Φ is provable or Φ is refutable. Presumably, we can hold to bivalence and manifestationism only for decidable discourses. The principles of semantic anti-realism yield a tight argument for this conclusion, independent of any subtle issues of the meaning of the logical terms, Heyting semantics, or metaphysical principles of determinacy. With intuitionistic logic, one can show that the “decidability” of every proposition follows from LEM and the anti-realist principle that all truths are knowable. Indeed, let Φ be any sentence. The anti-realist holds that if Φ then Φ is knowable; and if ~Φ then ~Φ is knowable. With these conditionals, a straightforward derivation establishes that if Φ ∨ ~Φ then either Φ is knowable or ~Φ is knowable. That is, anti-realism and LEM entail that either Φ is provable or Φ is refutable. As noted above, Dummett’s arguments for manifestation, harmony, and separability suggest that the logical connectives be interpreted along the lines of Heyting

On Tennant’s view, then, the classical mathematician and the intuitionist speak the same language, and so they can follow each other’s discourse and get along – provided that each mathematician explicitly acknowledge any metaphysical principles in play. In what follows, I argue that the situation is not as sanguine as this. Once the classical mathematician accepts the basic Dummett-Tennant framework, she is saddled with a very implausible view, even if this view should be consistent. So the classical mathematician should decline Tennant’s invitation, and, indeed, the whole Dummettian framework for meaning. One problem is that the arguments that underlie Dummett’s revisionism point toward a general and quite global anti-realism. The meanings assigned to the logical terms – the only meanings that they can have – are part and parcel of this anti-realism and cannot be jettisoned from it. The slogan of anti-realism is that all truths are knowable; truth is epistemically constrained. So once the classical mathematician accepts the Dummettian framework, which flows from the arguments establishing the meaning of the logical terminology, she must claim to know – somehow – each instance of LEM. She must claim to have an “effectively checkable construction” establishing each instance of LEM as true. Does the mere adoption of the metaphysical principle that underlies LEM provide such a warrant? In a footnote, Tennant acknowledges this conundrum for the classical mathematician, and replies that the task of finding an acceptable warrant for LEM is “the realist’s problem”, not his. We thus seem to agree that in accepting the Tennant-Dummett framework, the classical mathematician takes on a substantial epistemic burden, namely of showing how LEM is known. Again,

According to the realist’s principle of determinacy, the truth-value of any declarative statement is determined by reality in advance of our investigation, and the truth-value could attach to the statement quite independently of us and our beliefs and also independently of our available means for coming to know what is the case. (Tennant, 1996, p. 219)

WHY ANTI-REALISTS AND CLASSICAL MATHEMATICIANS CANNOT GET ALONG

semantics. This sharpens the conclusion of the last two paragraphs. Accordingly to Heyting semantics, the assertability condition of a sentence in the form Φ ∨ ~Φ consists of either a proof of Φ or a proof that there can be no proof of Φ. So if someone asserts a given instance of LEM, then she claims to know that, for the embedded sentence Φ, either Φ is provable or Φ is refutable. So we are led to the following conclusion: since Tennant’s classical mathematician accepts the Dummettian framework, and the ensuing anti-realism, she must hold that classical mathematics is decidable. Every sentence is either provable or refutable. From the perspective of global anti-realism, the metaphysical principle that underlines classical mathematics is not just a view about the way the world is. The metaphysical principle entails that the world is cooperative, eventually revealing all of its secrets, deciding all of the sentences of mathematics, one way or the other. In Shapiro (1993), I defined “optimism” to be the view that, in principle, every unambiguous sentence of mathematics is either provable or refutable. In the context of semantic anti-realism, LEM amounts to, or entails, optimism. If one takes historical “evidence” to be relevant to the issue of optimism, it goes both ways. The optimist can point out examples of problems, like the four-color result and Fermat’s last theorem, that remained open for a long time but now have a generally accepted resolution. Against this, one can point out examples of very old problems, like the Goldbach conjecture, that remain open to this day. As great a mind as Gödel endorsed optimism (Wang, 1974, pp. 324–325, see also Wang, 1987): . . . human reason is [not] utterly irrational by asking questions it cannot answer, while asserting emphatically that only reason can answer them . . . [T]hose parts of mathematics which have been systematically and completely developed . . . show an amazing degree of beauty and perfection. In those fields, by entirely unsuspected laws and procedures . . . means are provided not only for solving all relevant problems, but also solving them in a most beautiful and perfectly feasible manner. This fact seems to justify what may be called “rationalistic optimism”.

Sometimes this view is called “Gödelian optimism” (e.g., Tennant, 1997, p. 166). The opening of Hilbert’s celebrated “Mathematical problems” lecture (1900) is also an enthusiastic endorsement of optimism:3 However unapproachable these problems may seem to us and however helpless we stand before them, we have, nevertheless, the firm conviction that the solution must follow by . . . logical

59

processes . . . This conviction of the solvability of every mathematical problem is a powerful incentive to the worker. We hear the perpetual call: There is the problem. Seek its solution. You can find it . . . for in mathematics there is no ignorabimus.

The anti-realist rules out unknowable truths on a priori, conceptual grounds concerning the nature of truth. For the anti-realist, truth itself has an epistemic component. If there can be no proof, then there can be no truth either. So anti-realism has no consequences concerning the powers or the limitations of the human mind. But once she adopts excluded middle, the antirealist thereby adopts a thesis that the human mind is capable of deciding every unambiguous mathematical proposition, and this is a substantial thesis about our species. One might very well wonder whether our minds are that powerful. In a discussion of Gödel’s optimism, George Boolos (1995) wonders why “should there not be mathematical truths that cannot be given any proof that human minds can comprehend?” Why not, indeed? We know from Gödel’s incompleteness theorem that for any sound, effective formal system S for arithmetic, there is a true sentence Φ that is not a theorem of S. According to optimism, S is knowable. So it follows from optimism that there is no effective, formal system that captures all and only the knowable sentences of any mathematical theory as rich as arithmetic. So optimism is inconsistent with the mechanistic thesis that the knowable arithmetic propositions are recursively enumerable. Gödel (1951, p. 310) himself came to a similar conclusion: . . . the following disjunctive conclusion is inevitable: Either mathematics is incompletable in [the] sense that its evident axioms can never be comprised in a finite rule, that is to say, the human mind (even within the realm of pure mathematics) infinitely surpasses the powers of any finite machine, or else there exist absolutely unsolvable . . . problems of the type specified . . . It is this mathematically established fact which seems to me of great philosophical interest.

As always, Gödel’s conclusion is careful: either optimism is false, and there are unknowable propositions of arithmetic, or else the mechanistic thesis is false. The mathematician/physicist Roger Penrose has similar sentiments, leaning toward optimism and staunchly against mechanism: I had vaguely heard of Gödel’s theorem prior [to the first year of graduate school], and had been a little unsettled by my impressions of it . . . I had been disturbed by the possibility that there might be true mathematical propositions that were in principle

60

STEWART SHAPIRO inaccessible to human reason. Upon learning the true form of Gödel’s theorem . . . I was enormously gratified to hear that it asserted no such thing; for it established, instead, that the powers of human reason could not be limited to any accepted preassigned system of formalized rules.

Of course, our topic here is LEM and anti-realism, not mechanism (but see Shapiro, 1998). The GödelPenrose conclusion is quite consonant with the intuitionists’ unanimous claim that mathematical provability is inherently informal and is not completely codified in any effective deductive system. When the anti-realist declares that all truths are knowable, he means knowable in principle, with no effective limits placed on how sentences can become known. Similarly, when Tennant’s classical mathematician – the optimist – declares that all sentences are decidable, perhaps she means decidable in principle, not effectively decidable. Notice that the mechanistic thesis that the knowable arithmetic truths are recursively enumerable is already inconsistent with the anti-realist thesis that all truths are knowable (without mentioning LEM or optimism). Under anti-realism, the mechanistic thesis is that the arithmetic truths are recursively enumerable, and this contradicts Tarski’s theorem on the undefinability of truth (noting that Tarski’s theorem is intuitionistically kosher). Even so, in the context of anti-realism and Heyting semantics, Tennant’s metaphysical principle of determinacy – and the ensuing optimism – places a heavy burden on the powers of the human mind. To be blunt, it is fantastic that the mind should be that powerful. Consider the form: (AE!)[Φ]

∀x∃!yΦ(x, y).

Assume, for the sake definiteness, that the displayed variables range over natural numbers. We saw above that Dummett’s arguments concerning language acquisition and understanding point toward Heyting semantics. Under Heyting semantics, a (canonical) proof of a sentence in the form (AE!)[Φ] consists of: a procedure that, given any natural number m, produces a construction of a natural number n and proof of Φ(m, n).

So under Heyting semantics, the form (AE!)[Φ] amounts to the existence of a computable function f such that for every natural number n, Φ(n, fn). That is, ∀x∃!yΦ(x, y) is a statement that a certain function is computable. This, at any rate, is how the Dummettian anti-realist understands the form (AE!)[Φ].

Church’s thesis is the statement that every computable function is recursive. It is generally agreed that, in the context of classical mathematics, Church’s thesis is not equivalent to any formula or scheme in the standard axiomatizations. Some deny that Church’s thesis is a mathematical matter at all (see Shapiro, 1981, 1993a). The reason for this, of course, is that computability is an informal notion. However, we just saw that in the context of Heyting semantics, computability has a definitive formulation, via the form (AE!)[Φ]. So for the intuitionist, Church’s thesis is a scheme in the language of arithmetic: (CT) ∀x∃!yΦ(x, y) → ∃e∀x∃y(T(e, x, y) & Φ(x, U(y))), where T and U are versions of the respective Kleene relations and functions that express recursiveness.4 Among those inclined toward Heyting semantics, the issue of Church’s thesis amounts to whether (CT) is an acceptable principle, and whether it should be adopted as a new axiom scheme (see McCarty, 1987). The scheme (CT) is consistent with standard intuitionistic formalisms, such as Heyting arithmetic. But (CT) is inconsistent with classical arithmetic, and with excluded middle in particular. To see this, let Ψ(x, y) be the following formula: (∃zT(x, x, z) & y = 0) ∨ (~∃zT(x, x, z) & y = 1). In words, Ψ(x, y) says that either the Turing machine with code x halts when given x as input and y = 0, or else the Turing machine with code x does not halt when given x as input and y = 1. Consider the following instance of LEM: ∃zT(x, x, z) ∨ ~∃zT(x, x, z); which says that either the Turing machine with code x halts when given input x or it does not. It easily follows from this that ∀x∃!yΨ(x, y). But it follows from the unsolvability of the halting problem that there is no recursive function that computes the y given the x. That is, we can show (even in intuitionistic arithmetic) that ~∃e∀x∃y(T(e, x, y) & Ψ(x, U(y))). So with LEM we deduce the antecedent of an instance of (CT) and refute the corresponding consequent. So this instance of (CT) is outright refutable in classical

WHY ANTI-REALISTS AND CLASSICAL MATHEMATICIANS CANNOT GET ALONG

arithmetic or, in other words, this instance of (CT) is inconsistent with the indicated instance of LEM. So no classical mathematician can accept the scheme (CT). Of course, for someone who refuses to accept Heyting semantics, the scheme (CT) does not express Church’s thesis. However, Tennant’s classical mathematician does accept Heyting semantics. So her rejection of (CT) does amount to a rejection of the intuitive, informal version of Church’s thesis. As we saw, on the Heyting interpretation of the logical terminology, the intuitive reading of Church’s thesis leads straight to (CT). To reiterate, the classical mathematician proves that ∀x∃!yΨ(x, y). The Dummettian arguments indicate that the Heyting understanding of the connectives and quantifiers recapitulates the only meaning they have. Thus, the Dummettian who finds a way to accept Tennant’s principle of determinacy as synthetic a priori – in order to maintain classical mathematics – must establish that there is a computable function that decides the halting problem. This despite the fact that no recursive function does this, and we really have no idea how to compute the function. By itself, the metaphysical principle of determinacy does not provide the requisite procedures. The mere adoption of a principle does not justify its consequences. It seems that Tennant’s classical mathematician is saddled with a transcendental, non-constructive existence argument, an anathema to the underlying constructivism. Perhaps the metaphysical principle, or the ensuing optimism, provides some assurance that the computation procedures exist. Even so, this will not do. On the Heyting interpretation of the existential quantifier, our theorist cannot assert that the requisite procedure exists unless she knows how to find it. The theme of anti-realism is to rule out unknowable procedures. The situation is quite general. Let χ(x) be any predicate that applies to natural numbers. It is a routine theorem of classical arithmetic that ∀x∃!y[(χ(x) & y = 0) ∨ (~χ(x) & y = 1)]. Under Heyting semantics, this proof amounts to a thesis that there is a computable function that decides whether χ holds. So under Heyting semantics, which is the semantics of Tennant’s classical mathematician – supposedly the only semantics that the language can have – every predicate is effectively decidable. This, I submit is a tough pill to swallow and keep down. An anti-realist who accepts Tennant’s metaphys-

61

ical principle of determinacy as a synthetic a priori truth thereby claims to know a priori that every predicate is effectively decidable.

5. We cannot run Perhaps the anti-realist should withdraw the claim that LEM is synthetic a priori. Can classical mathematics still be saved? I presume that the anti-realist must maintain that LEM is synthetic. So the natural attempt would be to claim that LEM is justified a posteriori, perhaps on some sort of holistic grounds concerning the role of classical mathematics in science. This would be a Quine/Putnam-style indispensability argument for LEM. However, the foregoing suggests that if we stick to something like the Heyting interpretation of the connectives and quantifiers, our anti-realist cannot claim to know LEM at all unless she knows that every predicate is effectively decidable. The above arguments do not depend on any specific thesis concerning the pedigree of the (supposed) knowledge of LEM. It does not matter how LEM is known, a priori or otherwise. The argument goes straight from LEM (and antirealism) to decidability. Even the human race’s excellent track record in resolving open questions in mathematics does not provide serious evidence for the effective decidability of every predicate. For a second retrenchment, our would-be classical mathematician can drop the claim that LEM is known. She might hold instead that the metaphysical principle of determinacy – and so LEM – is a working hypothesis, perhaps adopted as a regulative ideal. Classical mathematics is the systematic exploration of the consequences of this hypothesis from the true and known intuitionistic mathematics. From this perspective, to say that Φ is a classical theorem is to say that if LEM holds then Φ. In light of Heyting semantics, this last is a statement that we can systematically transform any proof of LEM into a proof of Φ. Any intuitionist would accept this much. Even this weak position is implausible, and perhaps untenable. Once again, it follows from LEM that every predicate is effectively decidable. So the working hypothesis of determinacy comes to an assumption that in principle, for any predicate χ(x), we know of an effective procedure that decides whether χ holds. So in the context of anti-realism, a hypothesis of determinacy is no more plausible than this strong statement of human

62

STEWART SHAPIRO

abilities. That is, the content of the working hypothesis amounts to the extreme optimism noted above. What is the point of even assuming such an implausible thesis concerning human abilities? Let us sum up. Define modesty to be the thesis that there may be some predicates of natural numbers that we cannot effectively decide. Modesty is just the statement that for all we know, there very well might be at least one (well-defined) predicate χ(x) such that there is no effective procedure that decides of every natural number n, where or not χ(n) holds. Modesty is just the statement that we have not established the truth of optimism, and so it is modest indeed. Church’s thesis is a sharp version of modesty, since it entails that no non-recursive predicate is effectively decidable. Tennant’s principle of determinacy underwrites LEM, and, as we have seen, LEM is inconsistent with modesty in the context of Heyting semantics. One who claims to know LEM – a priori or otherwise – thereby claims to know the truth of optimism and thus the falsity of modesty (this despite the fact that we have no clue as to how to effectively decide some predicates). One who even assumes LEM thereby assumes the truth of optimism and the falsity of modesty. The only way for a Dummettian anti-realist to endorse LEM is for the discourse to be decidable. In a rich context like that of arithmetic, this requires gross immodesty – hubris. To conclude, let us briefly introduce Dummett’s and Tennant’s philosophical opponent, the realist. This philosopher can hold that there may be unknowable truths, and that there are, or might be, predicates that humans cannot effectively decide. If so, he is modest. However, since he rejects Heyting semantics, there is nothing immodest about his adoption of LEM. Rightly or wrongly, our realist presupposes a semantics which allows that truth can outrun knowability. In claiming that LEM is true (or known), our realist is not thereby claiming that every sentence is either knowable or refutable, nor that every predicate is decidable. Again, for the realist, truth is one thing, knowability another. It is the main conclusion of Dummett’s arguments for manifestation, separability, and harmony, that this distinction is untenable. Truth just is knowability in principle. So if the classical mathematician maintains Church’s thesis, or some other semblance of modesty, he cannot buy Dummett’s arguments concerning semantics. In particular, he must reject the anti-realist meanings assigned to the logical terminology. That is, if our classical mathematician maintains modesty, he

cannot accept Heyting semantics, and cannot go along with Tennant’s grand synthesis, as friendly as that may look. The problem here is not with the metaphysical principle of determinacy. Presumably, the realist accepts that. The problem is with the combination of determinacy (or LEM) and Heyting semantics. Our conclusion cuts both ways. From Heyting semantics – the natural outcome of Dummett’s arguments for anti-realism – we see that LEM and optimism/immodesty are intimately bound together. So if the Dummettian anti-realist maintains Church’s thesis, or its formal statement (CT), or some other semblance of modesty, she cannot have any truck with LEM or any metaphysical thesis that underwrites LEM. The anti-realist who endorses modesty has a principled reason to reject (the truth of some consequences of) LEM outright, not just demur from its assertion or its status as a logical truth.5 Against Tennant, we thus cannot have our cake and eat it too, no matter how polite we are prepared to be when doing the mathematics. If one is determined to accept classical mathematics and still maintain a sense of modesty, then he must thereby reject the thesis that Heyting semantics provides the meaning of the logical operators of this classical mathematics. Consequently, he must reject Dummett’s arguments leading to antirealism, either out of hand or by finding some fault in the reasoning.6

Notes 1 There is an interesting, ongoing research project to determine how much of science can be (re)built on an intuitionistic mathematics. 2 I am indebted to Crispin Wright for suggesting that the point be put this way. 3 In the same section, however, Hilbert envisions the possibility that we may discover that a certain problem has no solution in the sense originally intended. Discovering that a given sentence is undecidable in a formal system might consist of a “solution” of it. I am indebted to Michael Detlefsen here. The connection between optimism, Heyting semantics, and classical logic is made in Posy (1984). 4 For natural numbers a, b, c, the formula T(a, b, c) is a statement that c is the code of a complete computation of the Turing machine with code a started with input b; and for any natural number b, if b is the code of a complete computation of a Turing machine, then U(b) is the output of that computation. 5 McCarty (1987) comes to a similar conclusion. 6 I gave a version of this paper at a conference on the philosophy of mathematics at the University of California at Santa Barbara in February, 2000. Thanks to the organizer, Anthony Anderson, the benefactor, Steven Humphrey, and the participants for a fruitful

WHY ANTI-REALISTS AND CLASSICAL MATHEMATICIANS CANNOT GET ALONG discussion. Thanks also to Geoffrey Hellman and Neil Tennant for much stimulating conversation on these matters. I appreciate the spirit of collegiality.

References Benacerraf, P. and Putnam, H.: 1983, Philosophy of Mathematics, second edition, Cambridge: Cambridge University Press. Bishop, E.: 1967, Foundations of Constructive Analysis, New York: McGraw-Hill. Boolos, G.: 1995, Introductory note to Gödel (1951), in Gödel (1995), 290–304. Brouwer, L. E. J.: 1912, Intuitionisme en Formalisme, Gronigen: Noordhoof; translated as ‘Intuitionism and Formalism’, in Benacerraf and Putnam (1983), 77–89. Brouwer, L. E. J.: 1948, ‘Consciousness, Philosophy and Mathematics’, in Benacerraf and Putnam (1983), 90–96. Dummett, M.: 1973, ‘The Philosophical Basis of Intuitionistic Logic’, in M. Dummett (Ed.),Truth and Other Enigmas, Cambridge, Massachusetts: Harvard University Press, 1978, pp. 215–247; reprinted in Benacerraf and Putnam (1983), pp. 97–129. Dummett, M.: 1977, Elements of Intuitionism, Oxford: Oxford University Press. Dummett, M.: 1991, The Logical Basis of Metaphysics, Cambridge, Massachusetts: Harvard University Press. Gödel, K.: 1951, ‘Some Basic Theorems on the Foundations of Mathematics and their Implications’, in Gödel (1995), pp. 304–323. Gödel, K.: 1995, Collected Works III, Oxford: Oxford University Press. Heyting, A.: 1931, ‘The Intuitionistic Foundations of Mathematics’, in Benacerraf and Putnam (1983), pp. 52–61.

63

Heyting, A.: 1956, Intuitionism, an Introduction, Amsterdam: North Holland. Hilbert, D.: 1900, ‘Mathematische Probleme’, translated in Bulletin of the American Mathematical Society 8 (1902), 437–479. Lewis, D.: 1993, ‘Mathematics is Megethology’, Philosophia Mathematica 1(3), 3–23. McCarty, C.: 1987, ‘Variations on a Thesis: Intuitionism and Computability’, Notre Dame Journal of Formal Logic 28, 536–580. Posy, C.: 1984, ‘Kant’s Mathematical Realism’, The Monist 67, 115–134. Shapiro, S.: 1981, ‘Understanding Church’s Thesis’, Journal of Philosophical Logic 10, 353–365. Shapiro, S.: 1993, ‘Anti-realism and Modality’, in J. Czermak (Ed.), Philosophy of Mathematics: Proceedings of the Fifteenth International Wittgenstein Symposium 1, Vienna: VerlagHölder-Pichler-Tempsky, pp. 269–287. Shapiro, S.: 1993a, ‘Understanding Church’s Thesis, Again’, Acta Analytica 11, 59–77. Shapiro, S.: 1998, ‘Incompleteness, Mechanism, and Optimism’, Bulletin of Symbolic Logic 4, 273–302. Tennant, N.: 1996, ‘The Law of Excluded Middle is Synthetic A Priori, If Valid’, Philosophical Topics 24, 205–229. Tennant, N.: 1997, The Taming of the True, Oxford: Oxford University Press. Wang, H.: 1974, From Mathematics to Philosophy, London: Routledge and Kegan Paul. Wang, H.: 1987, Reflections on Kurt Gödel, Cambridge, Massachusetts: The MIT Press.

The Ohio State University The University of St. Andrews U.S.A. E-mail: [email protected]