Axiomatizations of arithmetic and the first-order/second-order divide

I am currently working on a short paper on axiomatizations of arithmetic and the first-order/second order divide. I usually don’t post (parts of) papers as blog posts, but it occurred to me that in this particular case, the different sections of the paper would make for more or less self-contained (hopefully interesting!) blog posts. So I’ll be posting them as I write, and I expect 5 blog posts to result (3 ready so far). As always, comments are more than welcome; in a sense, I’m hoping readers will help me improve this paper – I believe in collective, distributed cognition! So thanks in advance.

=================================

0. Introduction

It is a well-known fact that first-order Peano Arithmetic (PA1) is not categorical, i.e. it does not uniquely describe the sequence of the natural numbers that is typically viewed as the ‘intended model’ of arithmetic. Indeed, PA1 equally describes structures that strictly contain the sequence of the natural numbers but are not isomorphic to it, and these are known as the non-standard models of arithmetic. It is equally well known that second-order Peano Arithmetic (PA2) in turn, is categorical in that it is satisfied only by the intended model of arithmetic, the sequence of natural numbers, and by other models isomorphic to the intended one.

However, what PA2 offers in terms of obtaining categoricity, it takes away in terms of deductive power. Because second-order logic has an ill behaved (non-axiomatizable) underlying notion of logical consequence, any second-order theory will inherit its deductive limitations. Thus, apparently we cannot have our arithmetical cake and eat it: we can either have categoricity (with (PA2)) or a deductively stronger account of arithmetical theorems (with (PA1)), but not both. In fact, the conflict between the desiderata of expressive power and of deductive power with respect to axiomatizations of arithmetic is an instantiation of a more general phenomenon, namely the conflict between expressiveness and tractability (Levesque & Brachman 1987).

These facts have received a number of philosophical interpretations. Tennant (2000) describes it as a ‘pre-Gödelian predicament’, and argues that it represents the impossibility of the project of ‘monomathematics’. Read (1997) is less pessimistic and observes that, contrary to what many seem to think, Gödel’s incompleteness results do not represent the total failure of Frege’s logicist project because categoricity for arithmetic can be obtained with a logical (albeit second-order) axiomatization of arithmetic (as had been shown already by Dedekind). Hintikka (1989) draws on these observations to distinguish two different uses of logic for the foundations of mathematics – the descriptive use and the deductive use – and three senses of completeness: semantic completeness, deductive completeness, and descriptive completeness (categoricity).

In what follows, I take Hintikka’s distinction between descriptive and deductive uses of logic in (the foundations of) mathematics as my starting point to discuss what the impossibility of having our arithmetical cake and eating it (i.e. of combining deductive power with expressive power to characterize arithmetic with logical tools) means for the first-order logic vs. second-order logic debate. It is often argued (as discussed in (Rossberg 2004)) that the problematic status of the second-order consequence relation is sufficient to exclude second-order logic from the realm of what counts as ‘logic’. However, this criticism presupposes that the deductive use must take precedence over the descriptive use, a claim that is both historically and philosophically contentious. I argue that, if logical systems are viewed first and foremost as tools to be applied for the investigation of different subject matters, and if different applications are prima facie equally legitimate (for example, Hintikka’s descriptive and deductive uses), then the descriptive incompleteness of first-order logic with respect to arithmetic is just as serious as the deductive limitations of second-order logic (in this case, not restricted to arithmetic). These observations support a form of instrumental logical pluralism: there is no such thing as the one true logic, but only different logics appropriate for different applications.

The paper proceeds as follows. In the first two sections, I discuss Hintikka’s descriptive use and deductive uses of logic in mathematics: I illustrate the former with Dedekind’s search for a categorical characterization of arithmetic, and the latter with Frege’s search for a tool that would allow for gap-free formulations of mathematical theorems. I then elaborate on the first-order vs. second-order divide, and on the general project of using logical tools to investigate the foundations of mathematics. I conclude by offering some remarks on the so-called ‘dispute’ between first- and second-order logic and on the implications of the present analysis for debates on logical pluralism.

1. The descriptive use

Hintikka describes the descriptive use of logic for investigations on the foundations of mathematics in the following terms:

The uses of logical notions … for the purpose of capturing certain structures, viz., the different structures studied in various mathematical theories. The pursuit of this task typically leads to the formulation of axiom systems which use the logical concepts just mentioned for different mathematical theories. (Hintikka 1989, 64)

In this sense, logical notions have a descriptive use in mathematics insofar as they are used to describe certain mathematical structures such as the sequence of the natural numbers, geometric systems of points and lines etc. Indeed, most of the early uses of axiomatization in the foundations of mathematics aimed at (complete) descriptions of portions of mathematical theory by means of accurate descriptions of the underlying mathematical structures (Awodey and Reck 2002). Some examples are Dedekind and Peano on arithmetic, and Hilbert and Veblen on geometry.

In such cases, the axiomatizer starts with a specific, presumably unique mathematical structure in mind, and then attempts to describe this structure accurately and completely by means of logical notions. If such a description exhausts all of the relevant properties of the structure in question, then the axiomatization will not only describe the structure accurately, but also uniquely: it will be a description of nothing other than the intended mathematical structure in question (or structures identical to it according to the relevant parameters, e.g. isomorphism). An axiomatization that achieves this kind of completeness – which in turn yields uniqueness – is said to be categorical.

It is immediately apparent that the crucial feature of a system of logical notions for this descriptive use is expressive power: the more expressive the language is, the more fine-grained the description is likely to be, as the language will have the resources to express a greater number of the relevant properties of the structure. It is also clear that this descriptive approach goes well with (though it does not necessitate) a Platonic conception of mathematical structures, according to which they have some sort of antecedent, independent existence. The task of the mathematician is then to describe and investigate the pre-determined properties of these structures. (Naturally, how she has epistemic access to the properties of these abstract structures is a notoriously thorny problem in the epistemology of mathematics, the famous ‘Benacerraf challenge’.)

TO BE CONTINUED...

Part II

Part III

Part IV