Symbolic Logic: An Accessible Introduction to Serious Mathematical Logic

In recent times, I have found myself expanding a set of notes into a full-fledged logic textbook.  This page includes the preface, along with parts corresponding to courses in sentential logic (Phil 200), and then the first and second volumes of the text (for Phil 300 and then Phil 400), along with a complete version of the text, all in the PDF format.   This is work in progress, and so subject to change.  I am happy for anyone to use this material -- I  request only that you forward me comments, positive or otherwise. 

Winter 2016:

Sentential Logic (SL): from the first parts of chapters 1 - 7 -- sufficent for Phil 200

Sentential Logic (for single sided)

Sentential Logic (for two sided)

Symbolic Logic: Volume I: all of chapters 1 - 8 -- sufficient for Phil 300

Symbolic Logic, Vol I (for single sided)

Symbolic Logic, Vol I (for two sided)

Symbolic Logic: Volume II: all of chapters 9 - 14 -- sufficient for Phil 400/metalogic and 400/incompleteness

Symbolic Logic, Vol II (for single sided)

Symbolic Logic, Vol II (for two sided)

Symbolic Logic: complete text

Symbolic Logic (for single sided)

Symbolic Logic (for two sided)

Some links from exercises in Part IV:

Ruby recursive files: recursive1   running Ruby

Turing machine files: running the turing machine simulator   state.rb   turing_machine.rb  zero.rb  suc.rb   blank.rb

(most recent version of the text)

Preface

There is, I think, a gap between what many students learn in their first course in formal logic, and what they are expected to know for their second. While courses in mathematical logic with metalogical components often cast only the barest glance at mathematical induction or even the very idea of reasoning from definitions, a first course may also leave these untreated, and fail explicitly to lay down the definitions upon which the second course is based. The aim of this text is to integrate material from these courses and, in particular, to make serious mathematical logic accessible to students I teach. The first parts introduce classical symbolic logic as appropriate for beginning students; the last parts build to Gödel’s adequacy and incompleteness results. A distinctive feature of the last section is a complete development of Gödel’s second incompleteness theorem.

Accessibility, in this case, includes components which serve to locate this text among others: First, assumptions about background knowledge are minimal. I do not assume particular content about computer science, or about mathematics much beyond high school algebra. Officially, everything is introduced from the ground up. No doubt, the material requires a certain sophistication — which one might acquire from other courses in critical reasoning, mathematics or computer science. But the requirement does not extend to particular contents from any of these areas.

Second, I aim to build skills, and to keep conceptual distance for different applications of ‘so’ relatively short. Authors of books that are completely correct and precise may assume skills and require readers to recognize connections not fully explicit. It may be that this accounts for some of the reputed difficulty of the material. The results are often elegant. But this can exclude a class of students capable of grasping and benefiting from the material, if only it is adequately explained. Thus I attempt explanations and examples to put the student at every stage in a position to understand the next. In some cases, I attempt this by introducing relatively concrete methods for reasoning. The methods are, no doubt, tedious or unnecessary for the experienced logician. However, I have found that they are valued by students, insofar as students are presented with an occasion for success. These methods are not meant to wash over or substitute for understanding details, but rather to expose and clarify them. Clarity, beauty and power come, I think, by getting at details, rather than burying or ignoring them.

Third, the discussion is ruthlessly directed at core results. Results may be rendered inaccessible to students, who have many constraints on their time and schedules, simply because the results would come up in, say, a second course rather than a first. My idea is to exclude side topics and problems, and to go directly after (what I see as) the core. One manifestation is the way definitions and results from earlier sections feed into ones that follow. Thus simple integration is a benefit. Another is the way predicate logic with identity is introduced as a whole in Part I. Though it is possible to isolate sentential logic from the first parts of chapter 2 through chapter 7, and so to use the text for separate treatments of sentential and predicate logic, the guiding idea is to avoid repetition that would be associated with independent treatments for sentential logic, or perhaps monadic predicate logic, the full predicate logic, and predicate logic with identity.

Also (though it may suggest I am not so ruthless about extraneous material as I would like to think), I try to offer some perspective about what is accomplished along the way. In addition, this text may be of particular interest to those who have, or desire, an exposure to natural deduction in formal logic. In this case, accessibility arises from the nature of the system, and association with what has come before. In the first part, I introduce both axiomatic and natural derivation systems; and in Part III, show how they are related.

There are different ways to organize a course around this text. For students who are likely to complete the whole, the ideal is to proceed sequentially through the text from beginning to end (but postponing chapter 3 until after chapter 6). Taken as wholes, Part II depends on Part I; Parts III and IV on Parts I and II. Part IV is mostly independent of Part III. I am currently working within a sequence that isolates sentential logic from quantificational logic, treating them in separate quarters, together covering all of chapters 1 - 7 (except 3). A third course picks up leftover chapters from the first two parts (3 and 8) with Part III; and a fourth the leftover chapters from the first parts with Part IV. Perhaps not the most efficient arrangement, but the best I have been able to do with shifting student populations. Other organizations are possible!

A remark about chapter 7 especially for the instructor: By a formal system for reasoning with semantic definitions, chapter 7 aims to leverage derivation skills from earlier chapters to informal reasoning with definitions. I have had a difficult time convincing instructors to try this material — and even been told flatly that these skills “cannot be taught.” In my experience, this is false (and when I have been able to convince others to try the chapter, they have quickly seen its value). Perhaps the difficulty is that it is “weird” — none of us had anything like this when we learned logic. Of course, if one is presented with students whose mathematical sophistication is sufficient for advanced work, the material is not necessary. But if, as is often the case especially for students in philosophy, one obtains one’s mathematical sophistication from courses in logic, this chapter is an important part of the bridge from earlier material to later. Additionally, the chapter is an important “take-away” even for students who will not continue to later material. The chapter closes an open question from chapter 4 — how it is possible to demonstrate quantificational validity. But further, the ability to reason closely with definitions is a skill from which students in (sentential or) predicate logic, even though they never go on to formalize another sentence or do another derivation, will benefit both in philosophy and more generally.

Another remark about the (long) sections 13.3, 13.4 and 13.5. These develop in PA the “derivability conditions” for Gödel’s second theorem. They are perhaps for enthusiasts. Still, in my experience many students are enthusiasts and, especially from an introduction, benefit by seeing how the conditions are derived. There are different ways to treat the sections. One might work through them in some detail. One might wave at results individually. And even for the short shrift often accorded the derivability conditions, there is an advantage having a sort of panorama at which one can point and say “thus it is accomplished!”

Naturally, results in this book are not innovative. If there is anything original, it is in presentation. Even here, I am greatly indebted to others, especially perhaps Bergmann, Moor and Nelson, The Logic Book, Mendelson, Introduction to Mathematical Logic, and Smith, An Introduction to Gödel’s Theorems. I thank my first logic teacher, G.J. Mattey, who communicated to me his love for the material. And I thank especially my colleagues John Mumma and Darcy Otto for many helpful comments. In addition I have received helpful feedback from Hannah Baehr and Steve Johnson, along with students in different logic classes at CSUSB. I welcome comments, and expect that your sufferings will make it better still.

This text evolved over a number of years starting modestly from notes originally provided as a supplement to other texts. It is now long (!) and perhaps best conceived in separate volumes for Parts I and II and then Parts III and IV. With the addition of Part IV it is complete for the first time in this version. (But chapter 11, which I rarely get to in teaching, remains a stub that could be developed in different directions.) Most of the text is reasonably stable, though I shall be surprised if I have not introduced errors in the last part both substantive and otherwise.

I think this is fascinating material, and consider it great reward when students respond “cool!” as they sometimes do. I hope you will have that response more than once along the way.

T.R.
Fall 2016