## Thursday, 13 February 2014

### The deductive use of logic in mathematics (Part III of 'Axiomatizations of arithmetic...')

(This is the third part of the series of posts with sections of the paper on axiomatizations of arithmetic and the first-order/second-order divide that I am working on at the moment. Part I is here, and Part II is here.)
=============================

2. The deductive use

Hintikka describes the deductive use of logic for investigations in the foundations of mathematics in the following terms:
In order to facilitate, systematize, and criticize mathematicians’ reasoning about the structures they are interested in, logicians have isolated various valid inference patterns, systematized them, and even constructed various ways of mechanically generating an infinity of such inference patterns. I shall call this the deductive use of logic in mathematics. (Hintikka 1989, 64)
So the main difference between the descriptive and the deductive uses, as Hintikka conceives of them, seems to be that the objects of the descriptive use are the mathematical structures themselves, whereas the object of the deductive use is the mathematician’s reasoning about these very structures. This is an important distinction, but it would be a mistake to view the deductive use merely as seeking to emulate the actual reasoning practices of mathematicians. Typically, the idea is to produce a rational reconstruction that does not necessarily mirror the actual inferential steps of an ordinary mathematical proof, but which shows that the theorem in question indeed follows from the assumptions of the proof, through evidently valid inferential steps.

Frege’s Begriffsschrift project is arguably the first (and for a long time the only) example of the deductive use of logic in mathematics; one of his main goals was to create a tool to make explicit all presuppositions which would ‘sneak in unnoticed’ in ordinary mathematical proofs. Here is the famous passage from the preface of the Begriffsschrift where he presents this point:
To prevent anything intuitive from penetrating here unnoticed, I had to bend every effort to keep the chain of inferences free of gaps. In attempting to comply with this requirement in the strictest possible way I found the inadequacy of language to be an obstacle; no matter how unwieldy the expressions I was ready to accept, I was less and less able, as the relations became more and more complex, to attain the precision that my purpose required. This deficiency led me to the idea of the present ideography. Its first purpose, therefore, is to provide us with the most reliable test of the validity of a chain of inferences and to point out every presupposition that tries to sneak in unnoticed, so that its origin can be investigated. (Frege 1879/1977, 5-6, emphasis added)
Again, it is important to bear in mind that Frege’s project (and similar projects) is not that of describing the actual chains of inference of mathematicians in mathematical proofs. It is a normative project, even if he is not a revisionist who thinks that mathematicians make systematic mistakes in their practices (as Brouwer would later claim). He wants to formulate a tool that could put any given chain of inferences to test, and thus also to isolate presuppositions not made explicit in the proof. If these presuppositions happen to be true statements, then the proof is still valid, but we thereby become aware of all the premises that it in fact relies on.

For the success of this essentially epistemic project, the language in question should preferably operate on the basis of mechanical procedures, so that the test in question would always produce reliable results, i.e. ensuring that no hidden contentual considerations be incorporated into the application of rules (Sieg 1994, section 1.1). It is thus clear why Frege’s project required a deductively well-behaved system, one with a precisely formulated underlying notion of deductive consequence. Indeed, in the Grundgesetze Frege criticizes Dedekind’s lack of explicitness concerning inferential steps – incidentally, not an entirely fair criticism, given the different nature of Dedekind’s project.

It is well known that Frege’s deductive concerns were not particularly influential in the early days of formal axiomatics (and it is also well known that his own system in fact does not satisfy this desideratum entirely). In effect, in the works of pioneers such as Dedekind, Peano, Hilbert etc., a precise and purely formal notion of deductive consequence was still missing (Awodey & Reck 2002, section 3.1). It was only with Whitehead & Russell’s Principia Mathematica, published in the 1910s, that the importance of this notion started to be recognized (among other reasons, because they were the first to take Frege’s deductive project seriously). What this means for the present purposes is that Hintikka’s notion of the deductive use of logic in the foundations of mathematics is virtually entirely absent in the early days of applications of logic to mathematics, i.e. the final decades of the 19th century and the first decade of the 20th century – with the very notable exception of Frege, that is.

However, with the ‘push’ generated by the publication of Principia Mathematica, the deductive approach became increasingly pervasive in the 1910’s, reaching its pinnacle in Hilbert’s meta-mathematical program in the 1920s. Hilbert, whose earlier work in geometry represents a paradigmatic case of the descriptive use of logic, famously proposed a new approach to the foundations of mathematics in the 1920s, one in which meta-mathematical questions were to be treated as mathematical questions themselves.

Hilbert’s program was not a purely deductive program as Frege’s had been. Indeed, the general idea was to treat axiomatizations/theories as mathematical objects in themselves so as to address meta-mathematical questions, but this required that not only the axioms but also the rules of inference within the theories be fully specified. Moreover, one of the key questions motivating Hilbert’s program, the famous Entscheidungsproblem, and more generally the idea of a decision procedure for all of mathematics, has a very distinctive deductive flavor: is there a decision procedure which would allow us, for every mathematical statement, to ascertain whether it is  or it is not a mathematical theorem?

So the golden era of the deductive use of logic in the foundations of mathematics started in the 1910s, after the publication of Principia Mathematica, and culminated in the 1920s, with Hilbert’s program. Naturally, Gödel’s discovery that there can be no complete and computable axiomatization of the first-order theory of the natural numbers in the early 1930s (and later on, Turing’s and Church’s negative answers to the Entscheidungsproblem) was a real cold shower for such deductive aspirations. Indeed, the advent of model-theory in the late 1930s and 1940s can be viewed as a return to the predominance of the descriptive project at the expenses of the deductive project.

Currently, both projects survive in different guises, but it is fair to say that the general optimism regarding the reach of each of them in the early days of formal axiomatics, especially the deductive project, has somewhat diminished. Moreover, the extent to which expressiveness and tractability come apart has become even more conspicuous with the realization that decidable logical systems tend to be expressively very weak, even weaker than first-order logic (which is not decidable).

TO BE CONTINUED...

1. 2. 