## Wednesday, 12 February 2014

### The descriptive use of logic in mathematics (Part II of 'Axiomatizations of arithmetic...')

(This is the second 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 I pick up immediately where I left yesterday.)
========================================

As mentioned above, what Hintikka presents as the descriptive use of logic in mathematics was the predominant approach in the early days of formal axiomatics, in the second half of the 19th century (the notable exception being Frege, more on whom shortly). And indeed, Dedekind’s famous letter to Keferstein (published in (Van Heijenoort 1967)) is quite possibly one of the most vivid illustrations of the descriptive approach in action; because this approach was still something of a novelty at the time, Dedekind carefully explains his procedure when formulating an axiomatization for arithmetic (basically what is now known, by a twist of fate, as Peano Arithmetic).

How did my essay come to be written? Certainly not in one day; rather, it is a synthesis constructed after protracted labor, based upon a prior analysis of the sequence of natural numbers just as it presents itself, in experience, so to speak, for our consideration. What are the mutually independent fundamental properties of the sequence N, that is, those properties that are not derivable from one another but from which all others follow? (Letter to Keferstein, p. 99/100)

Thus, a pre-existing structure, the sequence of natural numbers, presents itself ‘for our consideration’, so that we can attempt to determine what its basic properties are. Dedekind then lists what appear to be the key properties of this structure, such as that it is composed of individuals called numbers, which in turn stand in a very special kind of relation to one another (the successor relation). One might think that, by offering an (apparently) exhaustive list of properties which, taken together, seem to describe the basic facts about this structure, the axiomatization would be complete also in the sense of picking out an unique referent, namely the intended structure, the sequence of the natural numbers. But Dedekind quickly adds that this is (unfortunately) not the case:

I have shown in my reply, however, that these facts are still far from being adequate for completely characterising the nature of the number sequence N. All these facts would hold also for every system S that, besides the number sequence N, contained a system T, of arbitrary additional elements t [satisfying certain conditions previously stated]. But such a system S is obviously something quite different from our number sequence N, and I could so choose it that scarcely a single theorem of arithmetic would be preserved in it. What, then, must we add to the facts above in order to cleanse our system S again of such alien intruders t as disturb every vestige of order and to restrict it to N? (Letter to Keferstein, p. 100)

In other words: while the properties he had just listed are all indeed present in the sequence N, they do not seem to exhaust the relevant properties of this structure, because they are equally true of other structures which are demonstrably very different from N. So an axiomatization guided only by these properties is not categorical because it does not uniquely refer to the intended sequence N; indeed, it also refers to structures strictly containing N but also containing additional, disruptive elements. How doe we get rid of these alien intruders?

For our purposes, it is important to notice that the properties listed by Dedekind up to this point have in common the fact that they can all be expressed by means of (what we now refer to as) purely first-order terminology. To be sure, that there may be an important distinction between first- and higher-order logics is something that became widely acknowledged only in the 1930s. Until then, first-order logic was not recognized as a privileged, particularly stable fragment of the logical system developed for the logicist project of Russell and Whitehead. So Dedekind had no reason to notice this peculiarity about these properties, or to make an effort to exclude higher-order terminology.

Dedekind then notices that solving the issue of the alien intruders t was the hardest part of his enterprise, as the problem is:

How can I, without presupposing any arithmetic knowledge, give an unambiguous conceptual foundation to the distinction between the elements n [the legitimate numbers] and the elements t [the alien intruders]? (Letter to Keferstein, p. 101)

The solution to this conundrum is offered by the technical notion of chains, which he had introduced in previous work. He explains this crucial notion in the following terms:

… an element n of S belongs to the sequence N if and only if n is an element of every part K of S that possesses the following two properties: (i) the element 1 belongs to K and (ii) the image φ(K) is a part of K. (Letter to Keferstein, p. 101, emphasis in the original)

(The function φ had been introduced previously.) Dedekind’s notion of chain can be glossed in modern terminology as “the minimal closure of a set A in a set B containing A under a function f on B (where being “minimal” is conceived of in terms of the general notion of intersection).” (Reck 2011, section 2.2) What matters for our purposes is that the notion of chain involves quantification over sets of elements n, and thus cannot be expressed solely with first-order terminology.

Dedekind correctly claims that the notion of chain offers a satisfactory solution to the problem of the alien intruders t. But as he had no reason to be parsimonious in his use of higher-order terminology, one might think that there might perhaps be other solutions to the problem of alien intruders not requiring the move to second-order quantification, which he did not consider. However, it is now known that first-order axiomatizations of arithmetic are inherently non-categorical (as per the usual Löwenheim-Skolen considerations). Second-order terminology is indeed required for an axiomatization to describe only the ‘intended structures’ – the sequence of the natural numbers and structures isomorphic to it – and not what are known as the non-standard models of arithmetic.

The need for second-order terminology to achieve categoricity in the case of axiomatizations of arithmetic is an illustration of the general point that the descriptive use of logic for mathematics, as defined by Hintikka, will generally require quite expressive logical languages. Arguably, first-order languages will systematically fail to deliver the expressive power required for the precise description of non-trivial mathematical structures, and this may be one of the causes for the (purported) inadequacy of first-order logic to account for ‘ordinary’ mathematical practice (Shapiro 1985).

TO BE CONTINUED...

Part III

Part IV

1. Catarina,
Van Heijenoort, of course, did not publish Dedekind's letter as written, but only an English translation thereof. The beautiful German original can be found in M.A. Sinaceur, L'infini et les nombres. Commentaires de R. Dedekind a "Zahlen". La coorepsonance avec Keferstein, Revue d'histoire des sciences , XXVII(1974), pp. 251-278.
On line at
http://www.persee.fr/web/revues/home/prescript/article/rhs_0151-4105_1974_num_27_3_1089

(Please note that M. A. Sinaceur should not be confused with the Dedekind expert Hourya Benis-Sinaceur ....)

2. Catarina,
You write: "an important distinction between first- and higher-order logics is something that became widely acknowledged only in the 1930s". I doubt this: became widely known only after WWII.

Have you got any quotations to support your claim?

The primacy of first order theories as we know them became entrenched with Tarski-Mostowski-Robinson, Undecidable Theories, in 1953, whereas Henkin's Completeness Theorem for second order logic w. r. t. general models was given wide exposure by the careful exposition in Church's Introduction from 1956.

1. What I had in mind was Godel's proof of the completeness of first-order logic in 1929. But 'widely acknowledged' can probably be interpreted in different was, so this is not a very felicitous formulation, I suppose.

3. Catarina, Goran is right that the distinction between first and second order logic became entrenched rather slowly. But in another sense your usage is very felicitous! What ever people made of it at the time, the separation between first and second order arithmetic is an almost immediate corollary of the Goedel completeness theorem. That is, as you point out here, categoricity fails for arithmetic if it is construed as a FO theory, but holds if it is construed as a SO theory, and all you need to show this is the completeness theorem. (Ok maybe you could have gotten this out of Lowenheim 1915 or Skolem 1922.) Prior to 1929 it is conceivable that the two logics may have been shown to be equivalent---however one might have formulated the equivalence of 2 logics in those early days.

E.g. Carnap assumed you had a completeness theorem for second order logic, an assumption Goedel destroys at the Erkenntnis conference in Konigsberg in 1930, when he announced the incompleteness theorem. What Goedel says essentially, is that because of the incompleteness theorem you cannot have a completeness theorem for SOL.

I always thought it was very interesting that Goedel announced the incompleteness theorem at that meeting that way, i.e. as a response to Carnap. Here's the full quote (G is using Carnap's language here, e.g. "monomorphic" etc):

"I would furthermore like to call attention to to a possible application of what has been proved here to the general theory of axiom systems. It concerns the concept of “decidable” and “monomorphic” . . . One would suspect that there is a close connection be- tween these two concepts, yet up to now such a connection has eluded general formulation ...In view of the developments pre- sented here it can now be shown that, for a special class of axiom systems, namely those which can be expressed in the restricted functional calculus, decidability always follows from monomor- phicity32. . . If the completeness theorem could also be proved for higher parts of logic (the extended functional calculus), then it would be shown in complete generality that decidability follows from monomorphicity. And since we know, for instance, that the Peano axiom system is monomorphic, from that the solvability of every problem of arithmetic and analysis expressible in Principia Mathematica would follow.
Such an extension of the completeness theorem is, however, im- possible, as I have recently proved; that is, there are mathemat- ical problems which, though they can be expressed in Principia Mathematica, cannot be solved by the logical devices of Principia Mathematica.33

My paper for the Goedel/Horizons volume goes into this, also Awodey, Carus and Reck's papers go through Carnap's logical work of the 1920s very carefully.

Very nice you are working on FOL vs SOL!

1. Hi Juliette, thanks! I am on holiday now, so I'm typing on my phone, but I just wanted to say that your comments are very useful. i'm still wo

2. Comment truncated... Anyway, still working on this paper, so your comments can still be incorporated.

4. I should have inserted a close quote at the end of Goedel's remark, i.e. after the phrase "…logical devices of Principia Mathematica." Also the numbers 32 and 33 refer to footnotes.

Sorry! I hope Goedel's remark is readable anyway...