Peter Smith

The first main topic of this paper is a weak second-order theory that sits between firstorder Peano Arithmetic PA1 and axiomatized second-order Peano Arithmetic PA2 – namely, that much-investigated theory known in the trade as ACA0. What I’m going to argue is that ACA0, in its standard form, lacks a cogent conceptual motivation. Now, that claim – when the wraps are off – will turn out to be rather less exciting than it sounds. It isn’t that all the work that has been done on ACA0 has been hopelessly misplaced: that would be a quite absurd suggestion. The mistake, if that’s what it is, has been a relatively small one. Still, we really ought to try to put things into conceptual good order here. That’s part of what philosophers are for. Here’s the structure of my main claim. On the one hand, interesting work on ACA0 actually only uses part of the strength of the theory: or as we might put it, the interesting work is actually carried on in a cut-down theory I’ll call ACA!. This theory, I’ll be claiming, does have a good conceptual motivation – it is in fact the theory that the putative conceptual grounding for ACA0 actually underpins. On the other hand, I’ll be arguing that original-strength ACA0 inductively inflates. I mean, to put it more carefully, that anyone who accepts ACA0 as a cogent theory can have no reason not to accept a certain significantly stronger theory, with a stronger induction principle. This stronger theory is standardly known as plain ACA. So, my claim comes to this: you can either go for the cut-down theory ACA!; or you can go for the much richer theory ACA. What you can’t do is – I mean, what you can’t have a stable conceptual motivation for doing – is to rest content with the intermediate strength ACA0 in its standard presentation. Yet in much of the literature, in particular in Simpson’s encyclopedic book Subsystems of Second-Order Arithmetic (1991), neither ACA! nor full ACA gets so much as a mention, and the conceptually unstable theory ACA0 gets all the glory. Why is my claim at all interesting? For at least two reasons..

In Episode 1, we introduced the very idea of a negation-incomplete formalized theory T . We noted that if we aim to construct a theory of basic arithmetic, we’ll ideally like the theory to be able to prove all the truths expressible in the language of basic arithmetic, and hence to be negation complete. But Gödel’s First Incompleteness Theorem says, very roughly, that a nice theory T containing enough arithmetic will always be negation incomplete. Now, the Theorem comes in two flavours, depending on whether we cash out the idea of being ‘nice enough’ in terms of (i) the semantic idea of T ’s being a sound theory, or (ii) the idea of odel’s own T ’s being a consistent theory which proves enough arithmetic. And we noted that G¨.

Why these notes? After all, I’ve written An Introduction to Gödel’s Theorems. Surely that’s more than enough to be going on with? Ah, but there’s the snag. It is more than enough. In the writing, as is the way with these things, the book grew far beyond the scope of the lecture notes from which it started. And while I hope the result is still pretty accessible to someone prepared to put in the time and effort, there’s a lot more in the book than is really needed by philosophers meeting the incompleteness theorems for the first time. After all, you might want to get your heads around only those technical basics which are actually needed for understanding philosophical discussions about incompleteness. So you need a cut-down version of the book – an introduction to the Introduction! Well, isn’t that what lectures are for? Indeed. But there’s another snag. I haven’t got many lectures to play with. So either I crack on at quite a fast pace, cover those basics, but perhaps leave too many people puzzled and alarmed. Or I do relaxed talk’n’chalk, highlighting the really Big Ideas, making sure everyone is grasping them as we go along, but inevitably omit important stuff and leave quite a gap between what happens in the lectures and what happens in the book. What to do? I’m going for plan. But then I still need to do something to fill that gap between lectures and book. Hence these notes. The idea, then, is to give relaxed lectures, highlighting Big Ideas, not worrying too much about depth or fine-detail. Then after the lecture, I’ll write up notes that expand things just enough, and then give pointers to relevant chunks of IGT. The idea, however, is for the notes to be more or less stand-alone, and to tell a brief but coherent story read by themselves. So occasionally I’ll copy a paragraph or two from the book, rather than just refer to them. Warning: just occasionally in these notes, I’ll no doubt apply that good maxim ‘Where it doesn’t itch, don’t scratch’.

... and a reading knowledge of formal logical symbolism is essential too. (Philosophers often use bits of logical symbolism to clarify their arguments.) Because the artificial and simply formal languages of logic give us highly illuminating objects of comparison when we come thinking about how natural languages work. (Relevant to topics in ‘philosophical logic’ and the philosophy of language.) But mainly because it us the point of entry into the study of one of the major intellectual achievements by philosophers of the 20th – i.e. the development of mathematical logic. (Not least in Cambridge: Russell and Whitehead, Ramsey, Turing.)

Last week, we talked a bit about the Anderson-Belnap logic of entailment, as discussed in Priest’s Introduction to Non-Classical Logic. For a quite different approach to entailment, we’ll look next week at Neil Tennant’s account. Doing things rather out of order, this week I’d like to say something more basic about the problems to which both Anderson and Belnap, on the one hand, and Tennant on the other, are responding. This will give me the chance for a bit of nostalgic philosophical time-travelling, revisiting work by Casimir Lewy and Timothy Smiley from the Cambridge of fifty years ago.

In a reading group, we’ve been working through the first three parts of Field’s Saving Truth from Paradox, by the end of which he has presented his core proposals. At this point, we’ve now rather lost the will to continue – for this is an astonishingly badly written book, which makes ridiculous demands on the patience of even a sympathetic reader. It so happened that it fell to me to introduce the last two chapters in Part III, Ch. 17 in which Field rounds out his key technical construction, and Ch. 18, ‘What Has Been Done’. I talked mainly about the latter. Here, for what they are worth, are some very quickly written reflections on what has and hasn’t been achieved

In the Wednesday Logic Reading Group, where we are working through Sara Negri and Jan von Plato’s Structural Proof Theory – henceforth ‘NvP’ – I today introduced Chapter 6, ‘Structural Proof Analysis of Axiomatic Theories’. In their commendable efforts to be brief, the authors are sometimes a bit brisk about motivation. So I thought it was worth trying to stand back a bit from the details of this action-packed chapter as far as I understood it in the few hours I had to prepare, and to try to give an overall sense of the project. These are the notes I wrote for myself. As often with such middle-of-term efforts dashed off in a couple of hours, I both would have liked to do better and do more justice to what we are reading, but I also just don’t have time to do more now than make a few corrections to the first version. So the usual warning applies: caveat lector.

Preface 1 The First Theorem revisited 1.1 Notational preliminaries 1.2 Definitional preliminaries 1.3 A general version of G¨ odel’s First Theorem 1.4 Giving the First Theorem bite 1.5 Generic G¨ odel sentences and arithmetic truth 1.6 Canonical and standard G¨ odel sentences 2 The Second Theorem revisited 2.1 Definitional preliminaries 2.2 Towards G¨ odel’s Second Theorem 2.3 A general version of G¨ odel’s Second Theorem 2.4 Giving the Second Theorem bite 2.5 Comparisons 2.6 Further results about provability predicates 2.7 Back to the First Theorem 2.8 Introducing Rosserized provability predicates..

Formal logic provides us with a powerful set of techniques for criticizing some arguments and showing others to be valid. These techniques are relevant to all of us with an interest in being skilful and accurate reasoners. In this highly accessible book, Peter Smith presents a guide to the fundamental aims and basic elements of formal logic. He introduces the reader to the languages of propositional and predicate logic, and then develops formal systems for evaluating arguments translated into these languages, concentrating on the easily comprehensible 'tree' method. His discussion is richly illustrated with worked examples and exercises. A distinctive feature is that, alongside the formal work, there is illuminating philosophical commentary. This book will make an ideal text for a first logic course, and will provide a firm basis for further work in formal and philosophical logic.